基于能量与功率控制的TopDisc拓扑算法研究

谢 昕，张 恒，于忠平，周 娟

(华东交通大学信息工程学院，江西南昌330013)

在无线传感器网络中体系结构，网络拓扑控制[1-5]具有十分重要的意义。设计良好的拓扑控制结构能够提高路由协议和MAC协议的效率，为数据融合、时间同步、目标定位等很多方面提供基础，有利于延长整个网络的生存时间。

传感器网络中的拓扑控制按照研究方向可以分为两类:节点功率控制和层次型拓扑控制组织[6-9]。其中，节点功率控制中的本地平均算法(LMA[10])通过动态调整节点的发射功率来形成拓扑结构;其主要思想是通过定期广播一个包含自己ID的LifeMsg消息，并为邻居节点设置一个上下限，当邻居数小于下限时，就增大发射功率;当大于上限时，就减弱发射功率。LMA算法也存在一些问题，它缺少严格的理论推导，在邻居节点的判断条件上没有严格的说明。层次型拓扑控制方面的TopDisc[11-12]算法是由Deb等人提出的一种基于图论中最小支配集问题的经典算法。TopDisc算法利用颜色来描述节点状态，解决骨干网拓扑结构的形成问题。TopDisc算法中提出两种节点标记方法，分别为三色算法和四色算法。这两种方法的区别在于，四色算法中，节点多了一种深灰色状态的节点，从而使得两种算法在形成簇后的结构有所不同。四色算法能形成比三色算法更少的簇，且簇与簇之间的交叠更少;但四色算法相对于三色算法可能会形成一些孤独的黑色节点，它不覆盖灰色节点。两种算法的核心思想都是:利用颜色标记理论找到簇头节点;利用与传输距离成反比的延时，使得一个黑色节点(簇头节点)覆盖更大的范围。该算法可以在节点密集的传感器网络中快速的形成分簇结构，并在簇于簇之间建立树型关系。但是由于这种算法构建成的层次型网络的灵活性不强，重复执行算法的开销过大，且该算法没有考虑到节点的剩余能量问题。

本文主要思想是在TopDisc算法的基础上，通过引入能量、功率控制机制，动态地改变节点发射功率，形成一种不等规模的簇型结构，减少簇与簇之间的交叠范围，从而使得簇间工作更加独立，减少了簇间的相互干扰。

1 网络模型定义

1.1 节点定义

定义1 所有节点都有唯一的编号，即ID信息。

定义2 整个网络中存在一个sink节点，该节点的数据处理和通信能力高于其他节点。有较强的数据收集和节点检测、查询能力，且该节点有持续的能源供给，并可以把数据传输到外部网络。

定义3 假设节点能够知道自己本身的位置，且位置固定。在数据传输时，附带自己的位置信息，使它的邻居节点和簇头节点都知道它的位置。

定义4 节点除了进行本簇内的数据收集和数据传输外，在必要时候，还必须兼顾簇间数据传输任务。

定义5 除sink节点外，所有节点的初始能量相同，设为Emax，传输中消耗的能量和所传输的字节成正比，和传输的距离也成正比。耗能公式为E(d)=kαdn

(1)

其中，k为常数，α代表传输的字节大小，n满足关系2＜n＜4，n的取值与很多因素有关，如地理情况，信号干扰等，考虑到这些因素，通常n的取值为3;d代表两节点间的距离。

定义6 传感器节点具有功率控制能力，假设节点的功率控制范围是[0，F]，F为最大发射功率，所有节点开始都在最大发射功率F下工作，此时的发射半径为R。

定义7 所有节点都知道自身的当前剩余能量，记为:En。在进行数据传输时，附带其剩余能量信息，是簇头节点知道它的剩余能量。

定义8 给传感器节点设置一个能量阀值E min，当传感器节点的能量低于这个阀值时，传感器不能被选为簇头节点，但可以传输数据，直到节点能量耗尽。

定义9 传感器节点状态分为5个状态，分别为睡眠、空闲、监听、发送和接受状态。其中规定睡眠状态不消耗能量，其余状态在单位时间内都消耗一定的能量。

1.2 网络定义

定义1 无线传感器网络可抽象为一个无向图G{V，E}，V代表顶点，即无线传感器节点的集合;E代表边，即相邻节点之间链路的集合。可描述为

其中，我们设C为所有的簇头节点集合，Vi代表节点i的邻居信息，i∈C。

定义2 在整个网络的生存期来说，因簇头的选举和功率控制机制导致的网络拓扑结构变化所消耗的能量，可以忽略不记。

2 基于能量与功率控制的改进算法

2.1 簇头节点与簇内节点

网络起始阶段，所有节点都标记为白色节点，都处于活动状态，由sink节点发起TopDisc算法的三色算法。此阶段因为是开始阶段，所有节点的能量都相同，不必考虑能量问题，其过程和三色算法一样。当一个节点被选为簇头节点时，该节点记录下此时的自身能量信息Enc。三色算法执行完之后，所有簇内节点向簇首节点发送带有与簇首节点距离长度的消息，消息发送完成后无任务的灰色节点立即进入睡眠状态，设定时间ts1和ts2，并在时间ts1过后醒来监听簇首节点消息，并向簇首节点发送带有自身剩余能量的信息，时间ts2后又进入睡眠状态，如果在ts2超时前簇首节点有消息任务需要其传送，立即变为活动节点。当簇内进行簇头选举时，节点被选举为簇头节点的概率为

其中:l为常数，En和Emax分别为节点的当前剩余能量和节点的初始最大能量。

2.2 簇的形成与更新

簇内节点经过第一轮三色算法后，形成了网络的初始拓扑结构(见图1)。从图1中可以看出，簇间的交叠范围比较大，增加了簇间传递数据冲突的发生概率，干扰了簇间数据的有效传递。

为了降低簇间传递数据发生冲突的概率，引入了节点功率控制机制，动态的调节节点的发射功率，其主要思想为:因为簇头节点都知道簇内节点的具体位置，所以簇头节点可以通过控制发射功率的大小来改变自身的发射半径，达到减少簇间交叠范围的作用。节点的功率控制范围是[0，F]。如图2所示，Dab表示节点a到节点b的距离，Dbc表示节点b到节点c的距离，因为Dab＞Dbc，所以我们选择调节节点c的发射功率，发射功率调节满足下面公式

其中:m为常数，m的取值在[0，1]之间，取值根据实际情况而定;R为最大发射半径。图3为图2经过功率控制机制后的更新图。

从图3可以看出，簇间的交叠减少，他们之间包含的灰色节点也相应的减少。通过节点功率控制机制，我们得到图1更新后的网络拓扑结构，如图4。

从图4可以看出，簇间的交叠和簇间包含的灰色节点减少的更加明显，从而大大降低了簇间通信发生冲突的概率。

2.3 簇的维护

网络拓扑结构稳定之后，为确保簇间通信有效的维持下去，还要对拓扑结构进行维护，起维护过程包括两个方面。

第一:当簇头节点的当前能量满足(6)式时，要选择新的簇头节点。其中:En代表节点的当前剩余能量;Enc代表节点被选为簇头时，记录下来的能量。

图1 网络初始拓扑结构

图2 无功率机制

图3 通过功率机制

图4 更新后网络拓扑结构

第二:新的簇头节点的选择需要满足时延机制。时延机制可表示为(7)式，其中:C1和C2代表常数;dy表示该节点到当前簇头节点的距离;Ey表示该节点当前自身的剩余能量。

通过时延机制选出新的簇头节点，并通过功率控制机制，更新网络拓扑结构，最终回到网络拓扑稳定阶段。

3 算法仿真及结果分析

本文用MATLAB作为仿真平台，在200m×200m的区域内，随机地散布了200个传感器节点，规定每个传感器初始能量都为1。在工作半小时后，随机地抽取其中100个节点，并记录下剩余能量值。图5为两种算法剩余能量的比较图，从图5中可以看出，改进后算法的能量分布更加的均匀，原因是节点被轮流选为簇头节点。TopDisc算法没有考虑到节点的剩余能量问题，所以出现了部分节点死亡;改进后算法的节点剩余能量远远大于原TopDisc算法，主要原因是通过了功率控制机制，间接地降低了节点的发射功率大小，节省了节点的多余能量开销。

图5 改进后算法与原TopDisc算法剩余能量比较

图6 改进后算法与原TopDisc算法生命周期比较

图6为两种算法的生命周期的比较，改进后算法因为节点轮流的来做簇头节点，且通过功率控制机制对节点的发射功率进行控制，生命周期有显著地提高，直到2 000秒才出现死亡节点;相对于原TopDisc算法，没有出现在同一时刻，节点的急剧死亡，节点数量的变化比较平稳;而原TopDisc算法，随着时间的推移，节点死亡的速度也加快。

4 结束语

本文在TopDisc三色算法基础上，提出一种基于能量与功率控制的拓扑算法。通过实验仿真发现，改进后的算法在节点能耗的控制上，具有明显的效果，减少了簇间的交叠范围，使得簇间通信更加独立，降低了簇间通信发生冲突的概率，提高了整个网络的生命周期。本文侧重于改进算法的理论研究，但在实际应用中可能还会遇到很多的问题，下一步的研究重点将放到实际应用中，从而完善算法在实际应用的不足。

[1] 张学，陆桑璐，陈贵海，等.无线传感器网络的拓扑控制[J].软件学报，2007，18(4):943-954.

[2] 杨贺，张树东，孙利民.无线传感器网络的拓扑控制[J].计算机科学，2007，34(1):36-38.

[3] LIL，HALPERN JY，BAHL P.Analysis of a cone-based distributed topology control algorithm forwirelessmu lti-hop networks[C].In:Proc ACM Sym p on Principles of Distributed Computing(PODC)，Acm，Newport，RI，2001:264-273.

[4] AMISA D，PRAKASH R，VUONGTHP.MaxMin d-cluster formation inwirelessad hoc Networks[C].In:Proc IEEEConfon Computer Communications(INFOCOM)，IEEE.1999:32-41.

[5] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京:清华大学出版社，2005.

[6] 陈力军，毛莺池，陈道蓄，等.平均度约束的无线传感器网络拓扑控制[J].计算机学报，2007，30(9):1 044-1 050.

[7] WEIY，HEIDEMANN J，ESTRIN D.An energy-efficientMAC protocol forwireless sensornetworks[J].Scientific Research Publishing，2008(1):59-69.

[8] 唐小军，曹长修，谭燕.无线传感器网络基于能量效率的分布式拓扑控制[J].计算机应用，2007，27(6):207-209.

[9] ZHU J，ZHAOH，XU JQ.An energy balanced reliable routingmetric in WSNs[J].Scientific Research Publishing，2009(1):22-26.

[10] KUBISCH M，KARLH，WOLISZ A.Distributed algorithms for transmission power controlinwireless sensornetworks[C].IEEEWCNC 2003，New Orleans，Louisiana，IEEE，2003:16-20.

[11] DEB B，BHATNAGARS，NATH B.A topology discovery algorithm for sensor networkswith applications to network management[J].DCSTechnical Report DCS-TR-411，Rutgers University，2001(5):26-30.

[12] CHANDRA R，FETZERC，HOGSTEDTK.Adaptive topology discovery in hybridwireless networks[C].Proceedingsin Informatics，1st International Conference on Ad-hoc Networks andWireless，Toronto，2002:356-359.