基于多簇點簡化的K容錯能量均衡拓撲控制方案

摘 要：針對異構監測傳感器網絡結構，設計了一個容錯拓撲控制方案，在可以減少網絡冗余的同時，兼顧了網絡的穩定性，并且保證生成拓撲具有最小的能量消耗。該方案首先將異構監測傳感器網絡簡化為同構傳感器網絡以簡化計算，然后根據節點的位置信息，建立各監測節點到簇節點的能量消耗最小，并且可以保證K容錯的K連通子圖。該方案在保證傳感器網絡K連通的前提下，可以最大限度減少傳感器網絡中的冗余路徑，且可以較好地均衡無線傳感器網絡能耗，延長網絡生命周期。

關鍵詞：異構無線傳感器網絡； 容錯拓撲控制； 能量均衡； 多簇點簡化

中圖分類號：TN929-34 文獻標識碼：A

文章編號：1004-373X(2011)17-0160-03

The K Tolerant Topology Control Method Based on Cluster Nodes Simplify Algorithm

XU Li， JU Yong-feng， LI Xue

(Chang’an University， Xi’an 710064， China)

Abstract： The topology control algorithm can simplify the redundant network， but almost all the existing algorithms neglect the stability of the wireless sensor network when simplifying the network. A fault tolerant topology control method is put forward in this paper. At first， this method transformed the heterogeneous wireless sensor networks to the homogeneous sensor networks with the cluster nodes simplify algorithm. Then， K-connected disjoint paths between the sink node and the surveillance nodes were built. This topology method not only reduced the redundancy paths effectively， but also balanced the energy consumption and lengthened the service time of wireless sensor network.

Keywords： heterogeneous wireless sensor network; tolerant topology control; energy consumption balanced; cluster nodes simplify

0 引 言

在無線傳感器網絡拓撲控制算法的研究中，利用簡化冗余路徑可以降低通信干擾，減少能量消耗，并且延長網絡生存期。但是，以路徑簡化為主要方法的拓撲控制［1-3］必定帶來網絡的健壯性下降。因此，在無線傳感器網絡拓撲控制研究中，需要考慮具有容錯特性的拓撲控制問題。如何建立能夠在當K－1個節點失效時，仍然具有連通性的無線傳感器網絡拓撲結構，是近年來研究的一個熱點問題。

近年來，很多學者開展了關于容錯拓撲近似算法的研究。如維持網絡K連通的全局近似算法FGSS和局部近似算法FLSS ［4］。但是由于這兩種算法不停地對比網絡路徑和判斷網絡是否達到K連通，開銷較大。文獻［5-6］以同構網絡為對象，提出了CBTC(α)算法。該算法中當α=2π/3K條件滿足時，可使原網絡的生成子圖保持K連通性。文獻［7］對隨機分布無線傳感器網絡節點的發射半徑與形成K連通圖的概率關系進行了分析，并提出Yp，K結構能夠使生成K連通子圖保持原拓撲的K連通性。文獻［8］提出了集中式和分布式算法K-UPVCS，但是該算法產生的拓撲結構極易產生回路而造成網絡不能夠連通。

本文在異構無線傳感器網絡模型上，提出了一種基于多簇點簡化的K容錯能量均衡拓撲控制方案。該方案在保證傳感器網絡K連通的前提下，可最大限度減少傳感器網絡中的冗余路徑，且可以較好地均衡無線傳感器的網絡能耗。

1 異構無線傳感器網絡模型

定義異構無線傳感器網絡G(V，)，V表示傳感器網絡中的節點集合，表示節點之間的通信路徑集合。傳感器網絡中包括三類節點：監測節點、接力節點和簇節點。設該傳感器網絡中，有N個用于信息監測的傳感器節點Vs，該類節點用于采集監測區域內的信息，并將信息發送到鄰居節點，且承擔轉發其他節點數據的任務；為了使監測區域內保持網絡連通，布署了R個用于數據接力節點Vr，接力節點負責信息的轉發。監測節點采集到的數據經多跳轉發最終傳送到簇節點Vc，簇節點一方面接收簇內的信息，同時參與簇之間的信息轉發，設簇節點個數為M。在該無線傳感器網絡模型中，有V=Vs∪Vr∪Vc。

2 基于多簇點簡化的K容錯能量均衡拓撲控制方案

本文提出了一個K容錯能量均衡拓撲控制方案。首先，為了簡化運算，該方案將多簇點異構傳感器網絡簡化為單簇點網絡，簡化后的網絡連通性與簡化前相同，且路徑保持能量最小；然后，在簡化后的網絡結構上，提出了一個K-MST算法，根據節點的位置信息，建立各監測節點到簇節點的最小能耗的K連通網絡。

2.1 異構傳感器網絡多簇點簡化

首先對異構傳感器網絡模型進行化簡。已知一個多簇點網絡G(V，)，包括N個監測節點和M個簇節點，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。如果1≤i≤N，則節點ni為監測節點;當N

式中：

(ni，nj)表示在節點ni的最大發射范圍Rmax(ni)內，該節點到鄰居節點的路徑;dist(ni，nj)是節點ni和nj之間的歐氏距離。由節點能量消耗模型可以算出路徑(ni，nj)上數據傳輸需消耗節點能量值cost(ni，nj)。異構傳感器網絡多簇點簡化到單簇點的步驟描述如下：

步驟1：簡化節點V→Vr，使Vr={n1，n2，…，nN，nN+1}，即將M個簇節點簡化為1個節點nN+1，記為簇節點nroot，監測節點不變。

步驟2：簡化路徑→r，減化過程分為兩個步驟。

(1) 保留N個監測節點之間的所有路徑；

(2) 當監測節點ni和簇節點nj間只存在一條路徑ni→nj(N+1≤j≤N+M)，令nrootnj且(ni，nroot)(ni，nj)；當監測節點ni和多個簇節點間存在路徑時，為了保證網絡能量消耗最小，則保留該節點到簇節點的最小路徑min(cost(ni，nj))，且使該簇節點變為nroot。

在簡化監測節點與簇節點路徑時，若監測節點和多個簇節點間存在路徑時，則保留監測節點到簇節點的最小路徑。由此可見，如果網絡原拓撲G(V，)是K連通的，則簡化后的拓撲仍為K連通且是能量消耗最小的單簇點拓撲結構。

2.2 K-MST拓撲控制算法

K-MST拓撲控制算法中，有如下定義：

定義1：定義節點ni的鄰居節點為{nj|nj∈V，j≠i}；

定義2：規定網絡中的邊有惟一權值。給定兩條邊(u1，v1)∈E和(u2，v2)∈E，dist(#8226;，#8226;)表示兩個節點間的歐氏距離，則邊的權值函數w:E→R滿足：

w(u1，v1)>w(u2，v2)d(u1，v1)>d(u2，v2)

or (d(u1，v1)=d(u2，v2)max{id(u1)，id(v1)}>max{id(u2)，id(v2)}

or ((d(u1，v1)=d(u2，v2)max{id(u1)，id(v1)}=max{id(u2)，id(v2)}

min{id(u1)，id(v1)}>max{id(u2)，id(v2)})

id(u1)表示節點u的序號，可以取其ID號或者MAC地址。這樣可以保證在圖Gr中的權值惟一，即使是權值相同的邊(u，v)和(v，u)。

在異構監測無線傳感器網絡圖G(V，)中，任意監測節點與簇節點間生成K條不相交路徑的算法分四步進行。

步驟1：將多簇點網絡簡化為單簇點網絡，即G(V，)→Gr(Vr，r)。

步驟2：求網絡Gr(Vr，r)的最小生成樹E1→，生成各監測節點至簇節點的能量消耗最小路徑，將這些路徑作為網絡信息采集和傳輸的主路徑，整個網絡能量消耗最小。

步驟3：將主路徑斷開，在r－1條路徑中求最小生成樹E2→，E1→+E2→可保證節點有兩條路徑和簇點連通。

步驟4：重復步驟3，生成k直至網絡K連通，則保證網絡的K連通子圖為Gr′(Vr，1+2+…+k)。

3 實驗結果和性能分析

構建1 000 m×1 000 m無線傳感器網絡仿真區域，網絡中隨機布置監測節點70~140個不等，令網絡中監測節點最大發射半徑為400 m，取簇節點個數N=3，首先對該網絡進行多簇點簡化，然后分別采用YG6，3算法、FLSS3算法以及本文提出的K-MST算法（K=3）進行保證每個節點至簇節點有3條不相關路徑的拓撲控制，對每種算法分別進行50次仿真，將所得的節點平均度數和未進行拓撲控制節點平均度數進行比較，如圖1所示。

從圖1可以看出，隨著網絡規模增大，未進行拓撲控制的網絡節點平均度數由11.4增加到23.37，且增長速度很快。采用三種拓撲控制算法均將節點的度數進行了有效的控制，將平均度數減小到了16以下，這三種算法中，本文提出的K-MST算法將節點平均度數保證在2.8~2.94之間，比其他兩種算法更多地減少了路徑的冗余，較小的網絡冗余減少了數據傳輸過程中的數據沖突能耗，可延長能量有限的無線傳感器網絡工作壽命，又可較好地保證網絡的連通性。

采用YG6，3算法、FLSS3算法以及3-MST算法分別進行50次仿真，將生成拓撲結構中平均鏈路長度和未進行拓撲控制的平均鏈路長度進行比較，如圖2所示。

從圖2可以看出，由于網絡規模增大，采用三種拓撲控制算法所得的網絡平均鏈路長度均呈下降趨勢，采用3-MST算法得到的平均鏈路長度最小。這意味著在采用3-MST算法生成拓撲的路徑上進行數據傳輸，比另外兩種算法可以消耗更少的能量，從而延長網絡壽命。

4 結 論

針對異構監測傳感器網絡結構，設計了一個優化的拓撲控制方案，在減少網絡冗余的同時兼顧了網絡的容

錯性，并且保證生成拓撲可以有效延長網絡生存周期。該拓撲控制方案在保證傳感器網絡K連通的前提下，可以最大限度減少傳感器網絡中的冗余路徑，可以較好地均衡無線傳感器網絡能耗，延長網絡生命周期。

參 考 文 獻

［1］王衛亞，徐麗.計算機網絡：原理、應用和實現［M］.北京：清華大學出版社，2007.

［2］卿斯漢，董占球.計算機網絡安全［M］.北京：清華大學出版社，2004.

［3］KUBISCH M， KARL H， WOLISZ A， et al. Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks [C]// Proceeding of IEEE Wireless Communications Conference. [S.l.]: IEEE， 2003: 558-563.

［4］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.

［5］LI N， HOU J C. FLSS: A fault-tolerant topology control algorithm for wireless networks [C]// Proceeding of the 10th International Conference on Mobile Computing and Networking. [S.l.]: IEEE， 2004: 275-286.

［6］RAMANATHAN R， REQINA R H. Topology control of wireless networks using transmit power adjustment [C]// Proceeding of IEEE INFOCOM. [S.l.]: IEEE， 2000， 2: 404-413.

［7］WATTENHOFER R， LI L， BAHL P， et al. Distributed Topology control for power operation in multihop wireless ad-hoc networks[C]// Proc. of the 20th Annual Joint Conf. of the IEEE Computer and Communications Societies. Washington: IEEE Computer Society， 2001: 1388-1397.

［8］LI L， HALPERN J Y， BAHL P， et al. Analysis of the Topology control algorithm for wireless multihop networks [C]// ACM Proc. of the 20th Annual Symp. on Principles of Distributed Computing. New York: ACM Press，2001: 264-273.

作者簡介：

徐 麗 女，1977年出生，博士研究生， 講師。主要研究方向為計算機網絡信息技術、軟件開發。