徐 麗，巨永鋒

（1.長安大學 信息工程學院，陜西 西安 710064；2.長安大學 電子與控制學院，陜西 西安 710064）

在無線傳感器網(wǎng)絡（Wireless Sensor Net，WSN）拓撲控制算法的研究中，簡化聯(lián)通路徑冗余可以降低通信干擾，減少能量消耗、并且延長網(wǎng)絡生存期，保證WSN的服務質量（Quality of Service，QoS）水平。但是，簡單的對節(jié)點間的聯(lián)通路徑進行簡化作為主要方法，勢必造成拓撲控制[1]帶來整個網(wǎng)絡的魯棒性下降。因此，在WSN拓撲控制問題的研究中，需要考慮具有容錯特性的拓撲控制問題、兼顧魯棒性及QoS，如何建立能夠在當K－3個節(jié)點（K＜N，N為總的節(jié)點數(shù)量）失效時，仍然具有連通性的WSN拓撲結構，并維持原有的魯棒性是近幾年來研究的一個熱點問題。

近年來，很多學者開展了關于容錯拓撲算法、控制的研究。如維持網(wǎng)絡K連通的全局近似算法FGSS和局部近似算法FLSS[2]。由于這兩種拓撲算法不間斷對網(wǎng)絡路徑進行遍歷和判斷網(wǎng)絡是否達到K連通，故此資源開銷較大。文獻[3]，[4]以同構網(wǎng)絡為對象，提出了CBTC（α）算法，該算法中當 α=2π/3k條件滿足時，可使原網(wǎng)絡的生成子圖保持K連通性，文獻[5]中對隨機分布WSN節(jié)點的發(fā)射半徑與形成K連通圖的概率關系進行了分析，并提出Yp，K結構能夠使生成K連通子圖保持原拓撲的K連通性，文獻[6]～[8]中提出了集中式和分布式算法K－UPVCS，但是上述算法產(chǎn)生的拓撲結構極易產(chǎn)生回路而造成網(wǎng)絡不能夠連通。

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

1 WSN模型

在大多數(shù)的WSN中，構成網(wǎng)絡需要多種功能的傳感器節(jié)點，故此會產(chǎn)生不同功能的節(jié)點，這些不同的節(jié)點構成異構的 WSN。 定義異構 WSNG（V，），V表示傳感器網(wǎng)絡中的節(jié)點集合，表示節(jié)點之間的通信路徑集合。WSN中包括三類節(jié)點：監(jiān)測節(jié)點、接力節(jié)點和簇節(jié)點。如圖1設該傳感器網(wǎng)絡中，有N個用于信息監(jiān)測的傳感器節(jié)點Vs，該類節(jié)點用于采集監(jiān)測區(qū)域內的信息并將信息發(fā)送到鄰居節(jié)點，且承擔轉發(fā)其它節(jié)點數(shù)據(jù)的任務；為了使監(jiān)測區(qū)域內保持網(wǎng)絡連通，布署于了R個用于數(shù)據(jù)接力節(jié)點Vr，接力節(jié)點負責信息的轉發(fā)。監(jiān)測節(jié)點采集到的數(shù)據(jù)經(jīng)多跳轉發(fā)最終傳送到簇節(jié)點Vc，簇節(jié)點一方面接收簇內的信息，同時參與簇之間的信息轉發(fā)，設簇節(jié)點個數(shù)為M。在該WSN模型中，有V=Vs∪Vr∪Vc。

圖1 WSN中包括的三類節(jié)點Fig.1 Three categories included in WSN nodes

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

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

2.1 異構WSN多簇點簡化

在一個WSN中會存在不同的節(jié)點，需要對這些異構的節(jié)點進行化簡，便于方案的設計。對異構WSN網(wǎng)絡模型化簡進行規(guī)范。已知一個多簇點網(wǎng)絡G（V，），包括N個監(jiān)測節(jié)點和M 個簇節(jié)點，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。 如果 1≤i≤N，則節(jié)點ni為監(jiān)測節(jié)點，當N＜i≤N+M時，ni為簇節(jié)點。

異構WSN多簇點簡化到簡單簇點的步驟描述如下：

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

1）保留N個監(jiān)測節(jié)點之間的所有路徑；

2）當監(jiān)測節(jié)點ni和簇節(jié)點nj間只存在一條路徑ni→nj（N+1≤j≤N+M），令 nroot?nj且（ni，nroot）?（ni，nj）；當監(jiān)測節(jié)點ni和多個簇節(jié)點間存在路徑時，為了保證網(wǎng)絡能量消耗最小，則保留該節(jié)點到簇節(jié)點的最小路徑 min（cos t（ni，nj）），且使該簇節(jié)點變?yōu)閚root。

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

2.2 K-MST拓撲控制算法

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

定義 2.1：定義節(jié)點的鄰居節(jié)點為{nj|nj∈s，j≠i}；

定義2.2：規(guī)定網(wǎng)絡中的邊有唯一權值。給定兩條邊（u1，v1）∈E 和（u2，u2）∈E，dist表示兩個節(jié)點間的歐氏距離，則邊的權值函數(shù)w:E→R滿足：

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

步驟 2：求網(wǎng)絡 Gr（Vr，）的最小生成樹，生成各監(jiān)測節(jié)點至簇節(jié)點的能量消耗最小路徑，將這些路徑作為網(wǎng)絡信息采集和傳輸?shù)闹髀窂?，整個網(wǎng)絡能量消耗最小。

3 實驗結果和性能分析

在1 200 m×1 200 m范圍構建WSN區(qū)域仿真，采用ZigBee標準設計節(jié)點通訊，網(wǎng)絡中隨機布置監(jiān)測節(jié)點60～140個不等，令網(wǎng)絡中監(jiān)測節(jié)點最大發(fā)射半徑為60 m，取簇節(jié)點個數(shù)N=3，首先對該網(wǎng)絡進行多簇點簡化，然后分別采用YG6，3算法、FLSS3算法以及本文提出的 K－MST 算法 （k=3）進行保證每個節(jié)點至簇節(jié)點有3條不相關路徑的拓撲控制，對每種算法分別進行60次仿真，將所得的節(jié)點平均度數(shù)和未進行拓撲控制節(jié)點平均度數(shù)進行比較。如圖2所示。

圖2 不同算法生成拓撲結構中節(jié)點平均度Fig.2 Node average degree of different algorithm generation topology

從圖2可以看出，隨著網(wǎng)絡規(guī)模增大，未進行拓撲控制的網(wǎng)絡節(jié)點平均度數(shù)由10.3增加到22.57，且增長速度很快。采用3種拓撲控制算法均將節(jié)點的度數(shù)進行了有效的控制，將平均度數(shù)減小到了15以下，這3種算法中，文中提出的KMST算法將節(jié)點平均度數(shù)保證在2.76～2.92之間，比其它的兩種算法更多地減少了路徑的冗余，較小的網(wǎng)絡冗余減少了數(shù)據(jù)傳輸過程中的數(shù)據(jù)沖突能耗，減少不斷喚醒節(jié)點的次數(shù)及工作時長，可延長WSN定能量狀態(tài)下的工作壽命，又可較好地保證網(wǎng)絡的連通性。

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

圖3 不同算法生成拓撲結構中節(jié)點平均鏈路長度Fig.3 Node average length of the link of different algorithm generation topology

從圖3可以看出，由于網(wǎng)絡規(guī)模增大，無論是在網(wǎng)絡中采用3種拓撲控制算法、還是沒有經(jīng)過算法網(wǎng)絡平均鏈路長度都將均呈下降趨勢，但是經(jīng)過算法處理的趨勢更為明顯，其中采用3－MST算法得到的平均鏈路長度最小。這意味著在采用3－MST算法生成拓撲的路徑上進行數(shù)據(jù)傳輸，比另外兩種算法可以消耗更少的能量，從而延長網(wǎng)絡壽命、提高網(wǎng)絡的魯棒性。

4 結 論

針對異構監(jiān)測WSN結構，設計了一個優(yōu)化的拓撲控制方案，此方案在保證傳感器網(wǎng)絡K連通的前提下，可以最大限度減少傳感器網(wǎng)絡中的冗余路徑，可以較好地均衡WSN能耗，延長網(wǎng)絡生命周期。在減少網(wǎng)絡冗余的同時兼顧了網(wǎng)絡的容錯性，并且保證生成拓撲的網(wǎng)絡魯棒性。此外方案生成的結構兼有節(jié)省節(jié)點布設的工程量及使用節(jié)點的數(shù)量等特點。由于WSN在傳統(tǒng)的大型區(qū)域的感知方面有較好的應用空間，故此對于此類異構的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.