容错能量均衡WSN拓扑控制方案研究

徐 丽，巨永锋

（1.长安大学 信息工程学院，陕西 西安 710064；2.长安大学 电子与控制学院，陕西 西安 710064）

在无线传感器网络（Wireless Sensor Net，WSN）拓扑控制算法的研究中，简化联通路径冗余可以降低通信干扰，减少能量消耗、并且延长网络生存期，保证WSN的服务质量（Quality of Service，QoS）水平。但是，简单的对节点间的联通路径进行简化作为主要方法，势必造成拓扑控制[1]带来整个网络的鲁棒性下降。因此，在WSN拓扑控制问题的研究中，需要考虑具有容错特性的拓扑控制问题、兼顾鲁棒性及QoS，如何建立能够在当K－3个节点（K＜N，N为总的节点数量）失效时，仍然具有连通性的WSN拓扑结构，并维持原有的鲁棒性是近几年来研究的一个热点问题。

近年来，很多学者开展了关于容错拓扑算法、控制的研究。如维持网络K连通的全局近似算法FGSS和局部近似算法FLSS[2]。由于这两种拓扑算法不间断对网络路径进行遍历和判断网络是否达到K连通，故此资源开销较大。文献[3]，[4]以同构网络为对象，提出了CBTC（α）算法，该算法中当 α=2π/3k条件满足时，可使原网络的生成子图保持K连通性，文献[5]中对随机分布WSN节点的发射半径与形成K连通图的概率关系进行了分析，并提出Yp，K结构能够使生成K连通子图保持原拓扑的K连通性，文献[6]～[8]中提出了集中式和分布式算法K－UPVCS，但是上述算法产生的拓扑结构极易产生回路而造成网络不能够连通。

论文在WSN拓扑模型上，提出了一种基于多簇点简化的K容错能量均衡拓扑控制方案。该方案在保证传感器网络K连通的前提下，可最大限度减少传感器网络中的冗余路径，且可以较好地均衡WSN能耗。

1 WSN模型

在大多数的WSN中，构成网络需要多种功能的传感器节点，故此会产生不同功能的节点，这些不同的节点构成异构的 WSN。 定义异构 WSNG（V，），V表示传感器网络中的节点集合，表示节点之间的通信路径集合。WSN中包括三类节点：监测节点、接力节点和簇节点。如图1设该传感器网络中，有N个用于信息监测的传感器节点Vs，该类节点用于采集监测区域内的信息并将信息发送到邻居节点，且承担转发其它节点数据的任务；为了使监测区域内保持网络连通，布署于了R个用于数据接力节点Vr，接力节点负责信息的转发。监测节点采集到的数据经多跳转发最终传送到簇节点Vc，簇节点一方面接收簇内的信息，同时参与簇之间的信息转发，设簇节点个数为M。在该WSN模型中，有V=Vs∪Vr∪Vc。

图1 WSN中包括的三类节点Fig.1 Three categories included in WSN nodes

2 基于多簇点简化的K容错能量均衡拓扑控制方案

在本方案中提出了一个K容错能量均衡拓扑控制方案，首先，为了简化运算，该方案将多簇点异构传感器网络简化为单簇点网络，简化后的网络连通性与简化前相同，且路径保持能量最小；然后，在简化后的网络结构上，提出了一个K－MST算法，根据节点的位置信息，建立各监测节点到簇节点的最小能耗的K连通网络。

2.1 异构WSN多簇点简化

在一个WSN中会存在不同的节点，需要对这些异构的节点进行化简，便于方案的设计。对异构WSN网络模型化简进行规范。已知一个多簇点网络G（V，），包括N个监测节点和M 个簇节点，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。 如果 1≤i≤N，则节点ni为监测节点，当N＜i≤N+M时，ni为簇节点。

异构WSN多簇点简化到简单簇点的步骤描述如下：

步骤 1：简化节点 V→Vr，使 Vr={n1，n2，…nN，nN+1}，即将 M 个簇节点简化为1个节点nN+1，记为簇节点nroot，监测节点不变。

1）保留N个监测节点之间的所有路径；

2）当监测节点ni和簇节点nj间只存在一条路径ni→nj（N+1≤j≤N+M），令 nroot⇐nj且（ni，nroot）⇐（ni，nj）；当监测节点ni和多个簇节点间存在路径时，为了保证网络能量消耗最小，则保留该节点到簇节点的最小路径 min（cos t（ni，nj）），且使该簇节点变为nroot。

在简化监测节点与簇节点路径时，若监测节点和多个簇节点间存在路径时，则保留监测节点到簇节点的最小路径。由此可见，如果网络原如拓扑G（V，）是K连通的，则简化后的拓扑仍为K连通且是能量消耗最小单簇点拓扑结构。

2.2 K-MST拓扑控制算法

K－MST拓扑控制算法中，有如下定义：

定义 2.1：定义节点的邻居节点为{nj|nj∈s，j≠i}；

定义2.2：规定网络中的边有唯一权值。给定两条边（u1，v1）∈E 和（u2，u2）∈E，dist表示两个节点间的欧氏距离，则边的权值函数w:E→R满足：

id（u1）表示节点u的序号，可以取其ID号或者MAC地址。这样可以保证在图Gr中的权值唯一，即使是权值相同的边（u，v）和（v，u）。

步骤 2：求网络 Gr（Vr，）的最小生成树，生成各监测节点至簇节点的能量消耗最小路径，将这些路径作为网络信息采集和传输的主路径，整个网络能量消耗最小。

3 实验结果和性能分析

在1 200 m×1 200 m范围构建WSN区域仿真，采用ZigBee标准设计节点通讯，网络中随机布置监测节点60～140个不等，令网络中监测节点最大发射半径为60 m，取簇节点个数N=3，首先对该网络进行多簇点简化，然后分别采用YG6，3算法、FLSS3算法以及本文提出的 K－MST 算法 （k=3）进行保证每个节点至簇节点有3条不相关路径的拓扑控制，对每种算法分别进行60次仿真，将所得的节点平均度数和未进行拓扑控制节点平均度数进行比较。如图2所示。

图2 不同算法生成拓扑结构中节点平均度Fig.2 Node average degree of different algorithm generation topology

从图2可以看出，随着网络规模增大，未进行拓扑控制的网络节点平均度数由10.3增加到22.57，且增长速度很快。采用3种拓扑控制算法均将节点的度数进行了有效的控制，将平均度数减小到了15以下，这3种算法中，文中提出的KMST算法将节点平均度数保证在2.76～2.92之间，比其它的两种算法更多地减少了路径的冗余，较小的网络冗余减少了数据传输过程中的数据冲突能耗，减少不断唤醒节点的次数及工作时长，可延长WSN定能量状态下的工作寿命，又可较好地保证网络的连通性。

采用 YG6，3算法、FLSS3算法以及 3－MST 算法分别进行60次仿真，将生成拓扑结构中平均链路长度和未进行拓扑控制的平均链路长度进行比较。如图3所示。

图3 不同算法生成拓扑结构中节点平均链路长度Fig.3 Node average length of the link of different algorithm generation topology

从图3可以看出，由于网络规模增大，无论是在网络中采用3种拓扑控制算法、还是没有经过算法网络平均链路长度都将均呈下降趋势，但是经过算法处理的趋势更为明显，其中采用3－MST算法得到的平均链路长度最小。这意味着在采用3－MST算法生成拓扑的路径上进行数据传输，比另外两种算法可以消耗更少的能量，从而延长网络寿命、提高网络的鲁棒性。

4 结 论

针对异构监测WSN结构，设计了一个优化的拓扑控制方案，此方案在保证传感器网络K连通的前提下，可以最大限度减少传感器网络中的冗余路径，可以较好地均衡WSN能耗，延长网络生命周期。在减少网络冗余的同时兼顾了网络的容错性，并且保证生成拓扑的网络鲁棒性。此外方案生成的结构兼有节省节点布设的工程量及使用节点的数量等特点。由于WSN在传统的大型区域的感知方面有较好的应用空间，故此对于此类异构的WSN值得深入研究。

[1]Kubisch M，Karl H，Wolisz A，et al.Distributed algorithms for transmission power control in wireless sensor networks[C]//In Proceeding of IEEE Wireless Communications and Networking Conference，2003:558－563.

[2]Deb B， Bhatangar S， Nath B.A topology discovery algorithm for sensor networks with applications to network management[R].DCS Technical Report DCS-TR-441，Rutgers University，2001.

[3]Li N，Hou J C.FLSS:A fault-tolerant topology control algorithm for wireless networks[C]//In Proceeding of the 10th Annual International Conference on Mobile Computing and Networking，2004:275－286.

[4]Ramanathan R，Reqina R H.Topology control of multihop wireless networks using transmit power adjustment[C]//In Proceeding of IEEE INFOCOM，2000（2）:404－443.

[5]Wattenhofer R， Li L， Bahl P， et al.Distributed topology control for power efficient operation in multihop wireless adhoc networks[C]//In:Sengupta B，Kermani P，Lee D，eds.Proc.of the 20th Annual Joint Conf.of the IEEE Computer and Communications Societies.Washington:IEEE Computer Society，2001:1388－1397.

[6]Li L，Halpern JY，Bahl P，et al.Analysis of the cone-based distributed topology control algorithm for wireless multihop networks[C]//In:Kshemkalyani A，Shavit N，eds.ACM Proc.of the 20th Annual Symp.On Principles of Distributed Computing.New York:ACM Press，2004:264－273.

[7]Hajiaghayi M， Immorlica N， Mirrokni V S.Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks[C]//In Proc.ACM Internatinal Conference on Mobile Computing and Networking，2000:300－312.

[8]Yao A.On constructing minimum spanning trees in K-dimensional spaces and related problems[J].SIAM Journal on Computing，1982，11（4）:721－736.