岳菊梅1，闫永义1，李俊1，王 维2
(1．西安电子科技大学理学院 陕西西安 710071；
2．西安电子科技大学计算机学院 陕西西安 710071)
1 引 言
2002年以前，大多数拓扑控制算法都是基于UDG(unitdisk graph)模型：两个移动节点可以通信，如果他们的Eu-clidean距离不大于一个阈值，并且基于这样的假设：所有节点的最大发射功率均相同(即homogenous net)。然而，在实际应用中，节点的最大发射功率会因各种原因而变化，如节点的机械误差，电子误差等。2003年Kuhn和Zollinger把U13(3模型推广到更接近实际的模型QUDG(quasi unit diskgraph)[1]。本文基于更一般的模型MG(mutual inclusiongraph)：2个节点可以通信，只有当他们位于彼此的发射范围，即节点u，v之间存在物理链接当且仅当‖uv‖≤min(ru，rv)。如图1所示，存在uv链接而不存在uw和uχ链接。显然，UDG是MG的一个特例，且MG不依赖于ho-mogenous net的假设，而使用于更一般的网络：不同节点具有不同的最大发射范围(即heterogeneous net)。
目前，拓扑控制算法可以分为2类：分簇算法和功率控制，分簇算法中较为成功的有STEM[2]，SPAN[3]，GAF[4]，ASCENT[5]等。较为成熟的功率控制有Asym-metric link[6]，XTCE[7]，Cone-Basedr[8]，邻近图算法等,经典的邻近图算法有RNG[9]，GG[10]，YG[11]，θ-graph[12]等，本文基于MG模型，提出一种新的邻近图算法MEP(MG) (Minimum Energy Path Graph)。
该算法保证了邻居间的链接都是最小能耗链接，且具有1一spanner特性。
2预备知识与设计思路
2．1预备知识
无线通信的能量消耗与通信距离的关系：E＝kdn，2＜n＜<4。E是能耗，k是系统常量，d是通信距离，n的取值与很多因素有关，例如传感器节点部署贴近地面时，障碍物多干扰大，n取值就大；天线质量对信号发射质量的影响也很大。考虑诸多因素，通常取n＝3，即通信能耗与通信距离的3次方成正比，随着通信距离的增加，能耗将急剧增加。而传感器节点的能量消耗主要是通信能耗，节点传输1b的信息100m需要的能量大约相当于执行3 000条计算指令所消耗的能量[13]。可见，通信距离的把握，对网络生存时间的影响很大。
(2)能耗扩展因子(the energy stretch factor)
H＝(V，E＇)是赋权图G＝(V，E)的t－spanner，如果对任意u，v∈V，有dH，(u，v)≤tdG(u ，v)。t称为H的stretch factor或spanning ratio。如果G中的权是两点的Euclidean距离，t叫作长度扩展因子(length stretch fac-tor)；如果G中的权是两点之间通信所需要的功率，t叫作功率扩展因子(power stretch factor)。
同样，如果G中的权是两点之间通信的能量消耗，t就叫作能耗扩展因子(energy stretch factor)。其中，dG(u，v)表示图G中连接u，v路的长，即该条路所包含边的条数。
(3)邻近图
图可以用G＝(V，E)的形式表示，其中V表示图中顶点的集合，E代表图中边的集合。E中的元素可以表示为l=(u，v)，其中u，v∈V。所谓由一个图G＝(V，E)导出的邻近图G＇＝(V，E＇)是指：对于任意一个节点v∈V，给定其邻居判别条件q，E中满足q的边(u，v)属于E＇[13]。
(4)最大功率图：所有节点都使用最大功率发射时所形成的拓扑结构图。
(5)基于邻近图的功率控制算法求出最大功率图G的邻近图G＇，然后G＇中每个节点以自己所邻接的最远通信节点来确定发射功率。
(6)对称拓扑
如果拓扑结构中的任意节点u保持一个链接uv，那么v也维持一个链接vu，即u，v之间可以双向通信。
2．2 设计思路
经典邻近图算法(RNG，GG，YG，DEL，θ－graph等)在选择邻居节点时，没有考虑能耗问题．笔者猜想，能否设计一种选择邻居的标准，使选择的邻居间的链接都是最小能耗链接。笔者按照这种思路，给出了下面的MEP(MG)算法。这里的(MG)是指基于MG模型提出的算法。
3 MEP(MG)算法
3．1 定义(MEP(MG)算法)
3．2 定理
MEP(MG)中的邻居链接都是最小能耗路。
3．3 引理
如果MG连通，在MEP(MG)算法中，若u不选v作为邻居，则存在另外一点w，使得u，v作为w的邻居。
证明：若u不选v作为邻居，由3．1节定义节知，此时存在点侧，使得 这里的o代表Ouv。证明在w执行完算法后，必选择u，v作为邻居，只需证下列条件成立：
其中，o1代表Owv，o2代表Owu，设出点w，Owv的坐标，同定理3．2易证上述条件(1)，(2)成立。
3．4 定理
MEP(MG)连通，如果MG连通。
证明：由于MG连通，只需证明对MG中的任意两点u，v，在MEP(MG)中存在一条连接u，v的路即可，下面用数学归纳法证明。
4 算法实现
5算法特性分析
5．1 MEP(MG)有能耗扩展因子1
然由3．2节定理和预备知识2．1．2节可知，MG中任意2点vi，vj之间的最小能耗路仍保留于MEP(MG)，亦即MEP(MG)的能耗扩展因子是1。
5．2 MEP(MG)算法是分布式算法
由算法实现4可知，算法是在网络中的每个节点上执行，且每个节点只广播2次，一次是广播自己的ID和位置，一次是通知所选的邻居节点添加链接。算法仅利用局部信息来选择邻居，没有用到任何全局信息．
5．3 MEP(MG)是对称结构
由于MEP(MG)是基于MG模型建立的，由MG模型的对称性可保证MEP(MG)的对称性。
6 结 语
本文简要分析了当前WSN拓扑控制算法的进展与分类，分析比较了拓扑控制所依赖的几种模型：UDG，QUDG，MG，以及2种网络类型：homogenous和heterogeneous，在此基础上，针对设计一种选择邻居的标准，使选择的邻居间的链接都是最小能耗链接问题，给出了MEP(MG)算法。该算法保证了所选邻居问的链接都是最小能耗路以及MEP(MG)的连通性，且具有1-spanner特性。虽然算法要求知道节点的位置信息(需GPS辅助)，但不必要求知道节点的确切位置信息(可以由定位技术实现)。而另一方面，算法特性的好坏确实依赖于定位的精度，另外值得一提的是，该算法是否度有界，有待进一步研究与完善。
来源：中电网--《现代电子技术》 |
