基于動態搜索區域的無線傳感器網絡小世界特性構建方案

謝啟輝 黃 杰

(東南大學信息科學與工程學院，南京210096)

無線傳感器網絡(wireless sensor networks，WSNs)是一種大規模的自組織網絡，它由大量的成本低、體積小、功耗低、能量有限的節點在預定區域內隨機布撒而成.WSNs廣泛地用于環境監測、軍事作戰、森林火災預警、農業、衛生醫療、航天、城市管理等領域，并取得了很好的效果.但是，由于WSNs的節點能量有限，使得能耗問題成為WSNs發展的瓶頸，如何優化傳感器節點能耗以延長WSNs的壽命是WSNs亟需解決的問題.

文獻［1］提出了社會學領域的“六度分離理論”.文獻［2-3］研究了小世界網絡的群體動力學，對小世界網絡進行了理論上的研究，分別提出了隨機重連的WS(Watts and Strogatz)小世界模型和隨機加邊的NW(Newman and Watts)小世界模型.文獻［4］討論了捷徑對無線網絡的影響，指出只需添加少量的隨機鏈路，并且這些鏈路的長度(以跳為單位)只需達到網絡直徑的0.25～0.4(假設網絡任意2個節點通信所需的跳數構成一個集合，網絡直徑就等于這個集合中的最大值)，就可以構造出網絡的小世界特性.

在WSNs中，構造小世界特性主要是通過添加邏輯鏈路即捷徑來實現的［4-8］.添加捷徑方式可以分為隨機重連和隨機加邊［9］.文獻［10］提出了數據騾子方案.文獻［11-12］提出了全新的構建WSNs小世界特性的 DAS(directed angulation towards the sink)方案和SSD(sink node as source/destination)方案.文獻［12］對DAS方案進行了修正并提出了on-line DAS方案.DAS模型首次為WSNs網絡從理論上提出了一種具有可操作性的捷徑添加方法.

本文針對DAS方案存在的缺點，提出一種利用菱形搜索區域構建具有小世界特性的無線傳感器網絡的方案，并對該方案進行了性能分析.

1 DZ方案

無線傳感網絡中，主要存在sink和sensor 2種節點.sensor節點用來收集信息，sink節點用來向sensor節點發送命令信息，并將各個sensor節點收集的數據信息融合匯總后，以有線或無線的方式將處理后的信息發送給客戶機.但是，要在無線傳感器網絡中構建小世界特性，必須要求所有的sensor節點輸出功率可以通過軟件編程調整，增大其通信半徑，以便用于構建捷徑的sensor節點具有更大的通信半徑(要比未用于構建捷徑的普通sensor節點的通信半徑大)，從而保證能夠實現捷徑端點間的通信.

在1 000 m×1 000 m的范圍內隨機布撒1 000個節點，按照文獻［12］設置參數:p=0.08，r=70 m，R=800 m，α=π/18，仿真得到 DAS方案的網絡拓撲圖(見圖1).從DAS方案搜索捷徑端點的方式來看，任何節點進行捷徑搜索時，Zs區域(以sink為中心300 m為半徑的扇形區域，其中300 m是來源于仿真結果的假設條件)內的節點都要被搜索一遍，這樣，就會導致區域Zs內的節點以較高的概率被選為捷徑端點.由于這些節點最容易因能量耗盡而成為孤立節點，被選為捷徑端點后，更增加了這些節點的能耗，導致其能量更早耗盡，使網絡壽命(出現第一個能量耗盡的節點所用的時間)縮短，大大降低了以DAS方案為理論基礎的online DAS方案的實用性.因此，為了延長網絡的壽命，就必須減小區域Zs內的節點成為捷徑端點的概率，為此本文提出了一種可以動態改變捷徑端點搜索區域的菱形區域(diamond zone，DZ)方案.

圖1 DAS方案的網絡拓撲圖

與DAS方案類似，假設節點布撒區域為一個規則長方形區域，唯一的1個sink節點部署在布撒區域的左下角，其他sensor節點隨機布撒.DZ方案的實現步驟如下:

①確定節點i的捷徑端點搜索區域.所有節點都知道sink節點坐標為(0，0)，節點i已知本節點和節點j的坐標，節點i坐標為(x(i)，y(i))，節點j坐標為(x(j)，y(j)).選定節點i為捷徑的一端，以節點i與sink節點的連線為菱形的一條對角線L1，則L1的方程為y=m1x+c1;以過節點i的一條垂直線為另一對角線L2，則L2的方程為y=m2x+c2.選取sink節點所在的位置作為菱形的一個頂點，頂角為α，則由以上條件可以確定一個菱形區域，此區域即可作為節點i的捷徑端點搜索區域，用來搜索與節點i構成捷徑的另外一個端點.如圖2所示.其中，m1=y(i)/x(i)，m2= － x(i)/y(i)，c2=(x2(i)+y2(i))/y(i).

②候選捷徑端點判定.假設節點i和sink節點連線為L1，節點j和菱形的端點sink節點的連線為L3，直線方程為y=m3x+c3;節點j和菱形在L1上的另一頂點的連線為L4，直線方程為y=m4x+c4.L1和 L3的夾角為 γ，L1和 L4的夾角為 β.候選端點判斷準則:如果滿足tan β＜tan(α/2)且 tan γ＜tan(α/2)，則判定節點j為候選捷徑端點.其中

圖2 DZ方案原理圖

③捷徑端點判定.節點i根據隨機產生的0～1之間的隨機數Q及指定的概率常數p(概率常數p用來作為隨機數Q的一個比較對象，來判斷是否將節點j選為捷徑的另一端點).如果隨機數Q＜p，則將節點j選為捷徑的另一端點，至此停止搜索;反之，則執行② 和③，繼續判斷下一個候選節點，直到找到第一個滿足Q＜p的節點，才停止搜索，轉入為第i+1個節點添加捷徑;如果所有節點都不滿足Q＜p，則轉入為第i+1個節點添加捷徑.

根據概率常數p，將每個節點按照上述步驟輪詢一遍，可構建出WSNs的小世界特性.

添加捷徑后，sensor節點分為2類.原始節點的通信半徑為r，表示為空心圓點;候選捷徑端點的節點表示為實心圓點，如圖2所示.如果被選為捷徑端點，則其通信半徑為R(R?r).DZ方案為節點i添加捷徑的流程如下(ZD是為節點i構造的菱形區域):

該搜索方案的優點是:搜索區域的面積大小隨著節點i到sink節點的距離的增大而增大，這樣，在離sink節點較近的Zs區域具有較小的搜索面積，并且這些搜索區域的位置隨著節點的改變而變動.由于區域Zs內的節點相對于區域外的節點離sink節點比較近，搜索區域的變小會使Zs內的節點成為捷徑另一端點的概率減小，從而保證了這些節點保存較多的能量，延長這些節點的存活時間.這樣，既可以防止網絡中Zs內的節點過早將能量耗盡而成為孤立節點，又可以縮短節點間的通信距離.同時，DZ方案添加捷徑后可以保證WSNs網絡具有小世界特性.

2 DZ方案的評估與優化

2.1 小世界特性的評估

在1 000 m×1 000 m的范圍內隨機布撒1 000個節點，布撒后的節點均勻分布，節點的組網半徑r=50 m，捷徑端點的通信半徑R=800 m，捷徑端點的搜索角度為α=π/18，按照這些參數，對DZ方案進行了仿真分析，結果如圖3所示.

圖3(a)為度分布曲線，其中，捷徑添加概率p=0.001，p(k)為度分布，k為度值.由仿真結果可知，度分布曲線符合泊松分布曲線的趨勢，滿足小世界特性對度分布的要求.

圖3(b)是捷徑添加概率-歸一化平均最短路徑曲線，L(p)/L(0)為歸一化平均最短路徑，C(p)/C(0)為歸一化聚類系數.由仿真結果可知，構造小世界特性以后，WSNs網絡的平均最短路徑長度迅速下降，但網絡的聚類系數下降緩慢，能夠保證在平均最短路徑長度迅速減小時，保持大的聚類系數，使整體和局部都保持很好的連通性，滿足小世界特性的要求.

圖3 DZ方案小世界特性仿真分析(α=π/18)

2.2 2種方案的對比分析

通過以上仿真證明了利用DZ方案可以在無線傳感器網絡中構建出小世界特性，為了將DZ方案和DAS方案的小世界特性進行對比，針對不同的p值和α值利用2種方案構建小世界特性，并通過對網絡聚類系數及其歸一化值的對比，證明在部分鏈路失效的情況下，DZ方案較DAS方案有更好的抗毀性及小世界特性.

2.2.1 固定α值和改變p值

設α=π/18，r=70 m，R=800 m，p從0～1依次遞增的情況下，利用2種方案構建小世界特性，得到網絡聚類系數的仿真對比如圖4所示.從圖4(a)仿真結果可以看出，隨著p值的增加，DZ方案構建的小世界特性的歸一化聚類系數值要比DAS方案的歸一化聚類系數值大，能夠保持一個較好的小世界特性.

從圖4(b)和表1可以看出，對應不同的p值，DZ方案構建的小世界特性的網絡聚類系數比DAS方案的要大.由于聚類系數反映了網絡的局部連通性，聚類系數越大，網絡的局部連通性就越好.所以，通過添加捷徑構造的具有小世界特性的無線傳感器網，DZ方案較DAS方案具有更好的局部連通性.

圖4 2種方案仿真對比(p值改變)

表1 2種方案p值不同時對應的C(p)值

較好的局部連通性有利于提高網絡的抗毀性，局部連通性越好，表明各個節點的一跳鄰居節點間的實際通信鏈路越多，如此就可以保證節點和一跳鄰居節點間有多條通信鏈路.當部分鏈路失效時，可以通過其他鏈路進行通信，從而有助于提高網絡的抗毀性.所以，通過添加捷徑構造的具有小世界特性的無線傳感器網，DZ方案較DAS方案有更好的抗毀性.

2.2.2 固定p值和改變α值

設p=0.01，r=70 m，R=800 m，α從π/180～π/2遞增情況下，利用2種方案構建小世界特性，得到網絡聚類系數的仿真對比如圖5所示.

圖5 2種方案對比分析(α值改變)

隨著α值的不斷增加，圖5(a)反映了DZ方案構建網絡的歸一化聚類系數要比DAS方案構建網絡的好，具有較好的小世界特性.圖5(b)和表2反映了DZ方案構建的網絡比DAS方案構建的網絡具有更好的局部連通性.結果表明，在部分鏈路失效時，DZ方案比DAS方案有更好的抗毀性.

表2 2種方案α值不同時對應的C(p)值

2.3 節能并延長網絡生命周期的評估

與圖1構建捷徑的條件相同，圖6是DZ方案構建捷徑后的網絡拓撲結構.圖1和圖6在區域Zs內，當捷徑添加概率p一定時(p=0.08)，圖6中的捷徑端點數目明顯比圖1中減少了很多，意味著區域Zs內的節點被選為捷徑端點的概率減小，即可以節省Zs內節點的平均耗能，從而延長網絡的壽命.

圖6 DZ方案的網絡拓撲圖

但是，由于DZ方案搜索捷徑的區域相對于DAS方案有所減少，在為節點i搜索另一個捷徑端點時，就需要搜索更多的節點，這樣使得捷徑構建時節點的能耗增加.假設構建捷徑時DAS方案和DZ方案每個節點的平均耗能分別為ec-DAS和ec-DZ，捷徑節點每接收并發送一次數據的平均能耗為e(即每減少一次數據中繼的平均節能)，那么如果要證明DZ方案確實比DAS方案有效，就必須滿足w＞ec－DZ－ec-DAS(w為捷徑節點中繼數據的次數)，即Zs區域內的節點w次中繼數據節省的能量大于搜索捷徑端點增加的能量(ec-DZ－ec-DAS)，從而在節能的前提下提高網絡的壽命.下面采用極限化搜索區域的方法證明不等式w＞ec-DZ－ec-DAS在一定條件下成立.

假設2種方案的捷徑端點的搜索區域極限化為整個節點撒布區域，下面以DAS方案為例，假設網絡中除節點i以外的其他節點都滿足tan β＜tan(α/2)，則此時每個節點構建捷徑消耗的能量為ec-DAS的最大值，記為max{ec-DAS}.假設網絡中布撒N個節點，由DZ方案的描述可知，每個節點要判斷另一個端點是否可以和其組成捷徑，所需判斷次數n的取值范圍為1≤n≤N－1，若節點每做一次判斷消耗的能量為E，則節點i搜索到捷徑的另一端點所消耗能量nE的概率為(1－p)n－1p(1≤n≤N－1).因此，可以得到 max{ec-DAS}的期望

式(1)×(1－p)可得

由式(1)和(2)可得

由于DZ方案的判斷準則比DAS的多進行了一次tan β＜tan(α/2)判斷，所以DZ方案的每個節點每進行一輪捷徑構建的能量消耗約為2E，同理可得DZ方案每個節點構建捷徑消耗的能量最大值為2E(max{ec-DAS}).

所以，ec-DAS∈(0，E(max{ec-DAS}))，ec-DZ∈(0，2E(max{ec-DAS})).由此可得

而e=2Eelec+EA，所以要保證DZ方案既節能又比DAS方案的壽命長，需要滿足

式中，Eelec為節點發送/接收單位bit數據的電子能量消耗;EA為節點發送單位bit數據的功率放大能量消耗［13-14］.

所以，在w滿足式(5)時，即

DZ方案優于DAS方案，既節省了能量，又延長了網絡的生命周期.

3 結語

分析了DAS方案的性能，并針對其缺陷提出了DZ方案，使捷徑端點搜索區域動態化，解決了DAS方案中臨近sink節點的區域Zs內的節點能量過度消耗問題.通過仿真，驗證了DZ方案的小世界特性，保證了網絡較強的抗毀能力.然后，理論證明了在w滿足一定條件的情況下，DZ方案較DAS方案既節能又能延長網絡壽命.從而，找到了一種較DAS方案更加優越的小世界網絡構建方案，提供了一種更好的理論依據，以改善網絡拓撲，延長網絡壽命.

References)

［1］Watts D J，Strogatz S H.Collective dynamics of“small-world” networks［J］. Nature，1998，393(6684):440-442.

［2］Milgram S.The small world problem［J］.Psychology Today，1967，1(1):61-67.

［3］Newman M E J，Watts D J.Renormalization group analysis of the small-world network model［J］.Physics Letters A，1999，263(4):341-346.

［4］Helmy A.Small worlds in wireless networks［J］.IEEE Communications Letters，2003，7(10):490-492.

［5］Luo X，Yu H.Constructing wireless sensor network model based on small world concept［C］//2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE).Chengdu，China，2010:501-505.

［6］Hawick K，James H.Small world effect in wireless agent sensor networks［J］.International Journal of Wireless and Mobile Computing，2010，4(3):155-164.

［7］鄭耿忠，劉三陽，齊小剛.基于小世界網絡模型的無線傳感器網絡拓撲研究綜述［J］.控制與決策，2010，25(12):1761-1768.Zheng Gengzhong，Liu Sanyang，Qi Xiaogang.Survey on topoloy of wireless sensor networks based on small world network model［J］.Control and Decision，2010，25(12):1761-1768.(in Chinese)

［8］Chinnappen-Rimer S，Hancke G P.Modelling a wireless sensor network as a small world network［C］//Proceedings of the 2009 International Conference on Wireless Networks and Information Systems.Shanghai，China，2009:7-10.

［9］王波，王萬良，楊旭華.WS與NW兩種小世界模型的建模及仿真研究［J］.浙江工業大學學報，2009，37(2):179-182，189.Wang Bo，Wang Wanliang，Yang Xuhua.Research of modeling and simulation on WS and NW small-world network model［J］.Journal of Zhejiang University of Technology，2009，37(2):179-182，189.(in Chinese)

［10］Jiang Chang-Jie，Chen Chien，Chang Je-Wei，et al.Construct small worlds in wireless networks using data mules［C］//Proceedings of IEEE International Conference on Sensor Networks，Ubiquitous，and Trustworthy Computing.Taichung，China，2008:28-35.

［11］Guidoni Daniel L，Mini Raquel A F，Loureiro Antonio A F.On the design of heterogeneous sensor networks based on small world concepts［C］//Proceedings of the 11th ACM International Conference on Modeling，Analysis，and Simulation of Wireless and Mobile Systems.Vancouver，Canada，2008:309-314.

［12］Guidoni Daniel L，Mini Raquel A F，Loureiro Antonio A F.On the design of resilient heterogeneous wireless sensor networks based on small world concepts［J］.Computer Networks，2010，54(8):1266-1281.

［13］Qin W，Hempstead M，Yang M.A realistic power consumption model for wireless sensor network devices［C］//2006 3rd Annual IEEE Communications Society.Reston，VA，USA，2006，1:286-295.

［14］Han B，Zhang D Z，Yang T.Energy consumption analysis and energy management strategy for sensor node［C］//International Conference on Information and Automation.Changsha，China，2008，6:211-214.