辛強偉，房鼎益

西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710127

隨機部署的無線傳感器網(wǎng)絡(luò)的負(fù)載平衡

辛強偉，房鼎益

西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710127

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）的節(jié)點處理能力有限，當(dāng)數(shù)據(jù)量較大時，單個節(jié)點或者單一路徑無法承擔(dān)負(fù)載，因而需要WSN具有良好的負(fù)載平衡。在一些實際應(yīng)用中出現(xiàn)了對少數(shù)節(jié)點的過度使用和依賴，而大多數(shù)節(jié)點是空閑狀態(tài)，這種狀況容易導(dǎo)致?lián)砣?。此外，?jié)點自身既感知數(shù)據(jù)，又要作為路由中繼，由于距離Sink近的節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)量多于距離Sink遠(yuǎn)的節(jié)點，故擁塞較易出現(xiàn)在Sink附近。實現(xiàn)負(fù)載平衡有利于WSN減輕網(wǎng)絡(luò)擁塞、降低丟包率以及增加網(wǎng)絡(luò)生存時間。

關(guān)于負(fù)載平衡，文獻(xiàn)[1]提出了兩種有效的安排算法以達(dá)到負(fù)載平衡，設(shè)計了相應(yīng)的協(xié)議。文獻(xiàn)[2]提出基于子節(jié)點數(shù)目的傳輸調(diào)度方法，以確保每個節(jié)點發(fā)送到Sink的數(shù)據(jù)量相同。文獻(xiàn)[3]中當(dāng)每個簇不多于兩個簇頭時，提出的方法可以顯著減少最大發(fā)送節(jié)點數(shù)目以及平均發(fā)送節(jié)點數(shù)目。文獻(xiàn)[4]指出很少的一部分節(jié)點承擔(dān)整個WSN的大部分通信量，部分節(jié)點由于鄰居節(jié)點較多而承擔(dān)了過大負(fù)載。將數(shù)據(jù)流均衡地劃分給多條鏈路以實現(xiàn)多路徑傳輸是一種實現(xiàn)負(fù)載平衡的有效方法。文獻(xiàn)[5]運用多路徑的路由方式，選擇鏈路質(zhì)量較好的路徑以減少使用鏈路質(zhì)量不好的路徑。文獻(xiàn)[6]運用多路徑以達(dá)到負(fù)載均衡，具體方法是根據(jù)節(jié)點的能量以不同的概率選擇路徑，從而使能耗均衡。文獻(xiàn)[7]提出了負(fù)載平衡樹算法，將數(shù)據(jù)流均衡地分配給路由樹的不同分支。對于Sink位置的優(yōu)化選擇，需要其附近節(jié)點具備多路徑的分流條件。文獻(xiàn)[8]提出部署多個Sink以分散數(shù)據(jù)量，從而避免在Sink周圍出現(xiàn)過熱的節(jié)點。本文研究節(jié)點隨機部署這種情況，Sink位置在節(jié)點部署區(qū)域之內(nèi)或周邊的任意位置。

另外還有一些別的方法：文獻(xiàn)[9]引入幾何法定人數(shù)系統(tǒng)來體現(xiàn)內(nèi)網(wǎng)數(shù)據(jù)存儲的思想，系統(tǒng)可以較好改善負(fù)載平衡并可保持有競爭力的能量效率。文獻(xiàn)[10]把節(jié)點嵌入3維凸多面體，用離散流開發(fā)了一個分布式算法完成嵌入，采用貪婪路由達(dá)到負(fù)載平衡。文獻(xiàn)[11]指出節(jié)點的部署必須擁有能夠處理最高網(wǎng)絡(luò)負(fù)載的活動時間。文獻(xiàn)[12]將負(fù)載平衡和功率控制結(jié)合起來，以使節(jié)點能耗均衡，從而最大化網(wǎng)絡(luò)生存時間。文獻(xiàn)[13]建立虛擬骨干網(wǎng)，將連通支配集的大小和負(fù)載平衡同時考慮。文獻(xiàn)[14]提出了優(yōu)化分簇來避免簇規(guī)模過大而導(dǎo)致負(fù)載不平衡，從而平衡能耗并提升網(wǎng)絡(luò)生存時間。文獻(xiàn)[15]在減少總的部署節(jié)點的前提下提出了新的算法以實現(xiàn)負(fù)載平衡。上述工作沒有從結(jié)構(gòu)的角度研究在隨機部署節(jié)點時的負(fù)載平衡，由于WSN隨機部署的環(huán)境復(fù)雜多樣，如山地叢林等野外環(huán)境，繁復(fù)的路由算法和復(fù)雜的功率控制算法的作用在這樣的環(huán)境下往往得不到有效的發(fā)揮。采用增大節(jié)點密度和統(tǒng)一變化節(jié)點通信半徑這樣的基礎(chǔ)方法反而更易適應(yīng)WSN隨機部署的復(fù)雜多樣的環(huán)境。然而增大節(jié)點密度和統(tǒng)一變化節(jié)點通信半徑對于隨機部署情況下負(fù)載平衡的具體影響以及兩者的區(qū)別，尚未得到明確研究。且以往關(guān)于負(fù)載平衡的研究的前提是已經(jīng)確定了Sink的位置，而本文的前提是Sink位置不確定，即Sink可位于任意位置。

本文不考慮具體的路由和調(diào)度算法，對節(jié)點隨機部署在一區(qū)域內(nèi)所形成的結(jié)構(gòu)進行統(tǒng)計分析，從結(jié)構(gòu)方面研究負(fù)載平衡。這一研究可以為將節(jié)點隨機部署在一區(qū)域內(nèi)且Sink位置可任意選取的WSN的負(fù)載平衡的更為科學(xué)的路由和調(diào)度算法的設(shè)計提供參考。

2 節(jié)點隨機部署的特點分析

2.1 相關(guān)符號及定義

N：節(jié)點數(shù)目。

R：節(jié)點通信半徑。

k：度，表示鄰居節(jié)點的數(shù)目。

S：部署區(qū)域的面積。

d：部署節(jié)點的密度。

L：負(fù)載。

定義1（負(fù)載）負(fù)載L為在時間間隔T內(nèi)節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包以及發(fā)送自身數(shù)據(jù)包的總和。

定義2（同級節(jié)點）到Sink跳數(shù)相同的節(jié)點。

定義3（負(fù)載平衡）假設(shè)WSN的節(jié)點數(shù)量為N，每個節(jié)點自身產(chǎn)生的數(shù)據(jù)量相同，通過多跳的方式傳輸數(shù)據(jù)，若距Sink某相同跳數(shù)的同級節(jié)點有h個，L1，L2，…，Lh表示這h個節(jié)點的負(fù)載，負(fù)載平衡即L1≈L2≈…≈Lh。

2.2 隨機大規(guī)模部署帶來的均勻化趨勢

假設(shè)把部署區(qū)域劃分為m個子區(qū)域，即S=S1+ S2+…+Sm，且每個子區(qū)域的面積都為S/m，因為是隨機部署，每個子區(qū)域在每隨機部署1個節(jié)點時的概率都是相同的，假定概率為P(Xi)，d=N/S，每部署1個節(jié)點都是獨立的，可用一組相互獨立隨機變量 X1，X2，…，XN表示，則當(dāng) N→∞，ds1≈ds2≈…≈dsm，這說明隨機大規(guī)模部署會帶來節(jié)點分布的均勻化趨勢。

2.3 邊緣效應(yīng)

由于邊界的存在，靠近邊界和遠(yuǎn)離邊界的傳感節(jié)點的覆蓋面積是不同的。以典型的矩形區(qū)域為例，一個節(jié)點覆蓋區(qū)域為πR2。如果是隨機部署在邊緣上的節(jié)點，則其覆蓋區(qū)域為。如果是隨機部署在四個頂點上的節(jié)點，則其覆蓋區(qū)域為。

假定節(jié)點部署的位置距離邊緣的距離為e，若0≤ e＜R，則其覆蓋面積為；若 e≥R ，則其覆蓋面積為πR2。因此節(jié)點的位置距離邊緣的距離在R以內(nèi)，其鄰居節(jié)點數(shù)目以較大概率為節(jié)點的位置距離邊緣的距離在R以外的倍。

因此，隨機部署使得節(jié)點的分布呈現(xiàn)均勻化趨勢，但邊緣效應(yīng)導(dǎo)致了鄰居節(jié)點數(shù)目分布的不均勻。

3 節(jié)點隨機部署情況下的負(fù)載平衡

3.1 節(jié)點隨機部署時所具有的規(guī)律

本文采用Matlab模擬在一個500×500的區(qū)域隨機部署節(jié)點。仿真發(fā)現(xiàn)隨機部署傳感節(jié)點在一定區(qū)域里的WSN的鄰居節(jié)點數(shù)目的分布近似服從正態(tài)分布。

根據(jù)正態(tài)分布曲線的性質(zhì)，在[μ-σ，μ+σ]區(qū)間的鄰居節(jié)點數(shù)有68.25%；在 [μ-2σ，μ+2σ]區(qū)間的鄰居節(jié)點數(shù)有85.45%；在 [μ-3σ，μ+3σ]區(qū)間的鄰居節(jié)點數(shù)有99.73%；而鄰居節(jié)點數(shù)在(μ±3σ)范圍以外的不到0.3%。

假設(shè)H0為鄰居節(jié)點數(shù)目服從正態(tài)分布；H1為鄰居節(jié)點數(shù)目不服從正態(tài)分布。Xj表示實驗中得到的鄰居節(jié)點數(shù)目，實驗中得到μ和σ。

接受假設(shè)H0，即大規(guī)模隨機部署傳感節(jié)點在一定區(qū)域里的WSN的鄰居節(jié)點數(shù)目的分布近似服從正態(tài)分布。

令 X表示鄰居節(jié)點的數(shù)目，正態(tài)分布的密度函數(shù)是：

期望為：

3.2 方差與負(fù)載平衡

方差用來度量隨機變量和其數(shù)學(xué)期望之間的偏離程度。D(X)小，表示集中；D(X)大，表示分散。

性質(zhì)方差D(X)越小，X的分布就越集中。

證明當(dāng)D(X)=0，若ε表示任意小，則

根據(jù)切比雪夫不等式有：

因此可見方差D(X)越小，X的分布就越集中。

隨著節(jié)點數(shù)目的增加和通信距離的增大正態(tài)曲線呈現(xiàn)扁平化趨勢。σ越小表明節(jié)點的鄰居節(jié)點數(shù)目集中，σ越大表明節(jié)點的鄰居節(jié)點數(shù)目分散。從圖1可見D(X)對正態(tài)曲線的影響：σ越小，正態(tài)曲線越陡峭；σ越大，正態(tài)曲線越扁平。扁平化意味著負(fù)載分化越嚴(yán)重，正態(tài)曲線越陡峭表示W(wǎng)SN負(fù)載較平衡。

通過以上的分析可知減小D(X)可以提高WSN負(fù)載平衡。本文用MATLAB仿真來驗證WSN負(fù)載平衡問題相關(guān)結(jié)論。

圖1 正態(tài)分布密度曲線比較示意圖

3.3 四種情況的分析

3.3.1 四種情況

本文對4種情況進行了討論，分別是節(jié)點稀疏時小的通信半徑，節(jié)點稀疏時大的通信半徑，節(jié)點稠密時小的通信半徑，節(jié)點稠密時大的通信半徑。節(jié)點稀疏時部署的節(jié)點數(shù)為100，節(jié)點通信半徑為25和75。節(jié)點稠密時部署的節(jié)點數(shù)為300，節(jié)點通信半徑為25和75。

（1）節(jié)點稀疏，小的通信半徑，如圖2。

（2）節(jié)點稀疏，大的通信半徑，如圖3。

（3）節(jié)點密集，小的通信半徑，如圖4。

（4）節(jié)點密集，大的通信半徑，如圖5。

圖2和圖4顯示網(wǎng)絡(luò)中含有鄰居節(jié)點數(shù)為0的節(jié)點，表明這時網(wǎng)絡(luò)是不連通的。連通是首要問題，連通之后的負(fù)載平衡問題才具有意義。鄰居節(jié)點數(shù)為0的節(jié)點數(shù)目隨著部署節(jié)點的增多或者節(jié)點通信半徑的增大而減少，從而網(wǎng)絡(luò)連通狀況得到改善。

圖2 N=100，R=25

圖3 N=100，R=75

圖4 N=300，R=25

圖5 N=300，R=75

3.3.2 四種情況的比較

圖6～圖9是將圖2～圖5的正態(tài)數(shù)據(jù)寫入正態(tài)分布密度曲線以進行比較。圖6和圖7是節(jié)點的通信半徑增大至3倍。圖8和圖9是隨機部署節(jié)點的密度增大至3倍。

通過50次實驗，數(shù)據(jù)是50次實驗的平均值，取至小數(shù)點后兩位。

（1）節(jié)點稀疏時通信半徑3倍時的關(guān)系：

N=100時，R=75是R=25的E(X)的6.44倍，D(X)的7.67倍。

（2）節(jié)點稠密時通信半徑3倍時的關(guān)系：

N=300時，R=75是 R=25的 E(X)的7.96倍，D(X)的16.16倍。

（3）小的通信半徑節(jié)點密度3倍時的關(guān)系：

R=25時，N=300是 N=100的 E(X)的2.59倍，D(X)的2.33倍。

（4）大的通信半徑節(jié)點密度3倍時的關(guān)系：

R=75時，N=300是 N=100的 E(X)的3.19倍，D(X)的4.92倍。

E(X)的變化：

圖6 N=100，R=25和R=75比較

圖7 N=300，R=25和R=75比較

圖8 R=25，N=100和N=300比較

隨著N的增大，D(X)的變化是非線性的。

用Δk來表示W(wǎng)SN中節(jié)點最大度和最小度的差值，即

其中 kmin≥1。

D(X)增大，會使分散程度加重，即會使Δk增大，因而D(X)增大不利于WSN隨機部署情況下的負(fù)載平衡。

隨著N增大或者R增大，邊緣效應(yīng)越明顯，從而使D(X)增大，即鄰居節(jié)點數(shù)目的分布隨著節(jié)點數(shù)目的增大或者通信半徑的增大而分散程度加重。E(X)的變化是線性的，D(X)的變化是非線性的，當(dāng)N增大或者R增大時WSN的負(fù)載不平衡非線性增大。通過仿真實驗發(fā)現(xiàn)：同樣的倍數(shù)關(guān)系的增長，節(jié)點通信半徑的增大比節(jié)點數(shù)目的增大造成的鄰居節(jié)點數(shù)目的分化作用要明顯得多，通信半徑的增大更易造成WSN隨機部署情況下的負(fù)載不平衡。

3.4 進一步的討論

從二維平面到三維立體空間的推廣有利于更貼近實際情況。在三維空間V中，節(jié)點的通信范圍是以坐標(biāo)(x，y，z)為球心、以 R為半徑的圓球。若點 q∈V，設(shè)覆蓋度為W，覆蓋度指覆蓋了點q的節(jié)點數(shù)目，則在三維空間V中的覆蓋為：

圖9 R=75，N=100和N=300比較

Gt為接收機天線增益，Gr為發(fā)射機天線增益。無線信號在空間傳播中的損耗為：

Loss為傳輸損耗，D為距離，f為工作頻率。距離的增大，會使無線信號在空間傳播中的損耗最大，并且RSSI會減小。此外在實際情況中三維立體空間往往存在障礙物的遮擋，比如樹木的遮擋，無線信號在空間傳播中的損耗進一步增大，如果諸如物體遮擋等因素的影響表示為 PL，則

三維空間可以投影到二維平面，假設(shè)三維空間中的一點坐標(biāo)為(ax，ay，az)，若采用正交投影的方法將該點投影到二維平面，假設(shè)其在二維平面上的坐標(biāo)為(bx，by)，則

在WSN的隨機部署中，如山地起伏不平的地形、樹木的遮擋都會引起節(jié)點間通信距離以及無線信號空間傳播損耗的增大。在二維平面上兩節(jié)點的位置分別為(xi，yi)、(xj，yj)，則兩節(jié)點間的距離為：

在三維立體空間兩節(jié)點的位置分別為(xi，yi，zi)、(xj，yj，zj)，則兩節(jié)點間的距離為：

距離的變化影響到了無線信號的傳播，無線信號空間RSSI理論值為：

其中向量t為偏移量，向量u為縮放因子。用矩陣表示為：

因此采用正交投影的方法影響二維平面完全反映三維空間的因素是偏移量和縮放因子，但二維平面還是可以在一定程度上反映三維立體的特點。故對于在二維平面得出的結(jié)果，在三維空間可以得到與二維平面類似的結(jié)論。

4 結(jié)論

本文在不考慮具體的調(diào)度和路由算法的情況下，從結(jié)構(gòu)的角度來研究節(jié)點隨機部署且Sink位置任意選取時WSN的負(fù)載平衡，以便明晰在隨機部署時所形成的結(jié)構(gòu)對WSN負(fù)載平衡的影響。通過分析發(fā)現(xiàn)邊緣效應(yīng)對隨機部署有著重要影響。仿真發(fā)現(xiàn)隨機部署時鄰居節(jié)點數(shù)目近似于正態(tài)分布，且部署密度的增大比節(jié)點通信半徑的增大更有利于隨機部署情況下WSN的負(fù)載平衡。

[1]Xiong Shuguang，Li Jianzhong，Li Mo，et al.Multiple task scheduling for low-duty-cycled wireless sensor networks[C]//Proc of IEEE INFOCOM，2011：1323-1331.

[2]Cheng T E，Ruzena B.Congestion control and fairness for many-to-one routing in sensor networks[C]//Proc of ACM SENSYS，2004：148-161.

[3]Zhao Miao，Yang Yuanyuan.A framework for mobile data gathering with load balanced clustering and MIMO uploading[C]//Proc of IEEE INFOCOM，2011：2759-2767.

[4]Liu Yunhao，He Yuan，Li Mo，et al.Does wireless sensor network scale?a measurement study on green orbs[C]// Proc of IEEE INFOCOM，2011：873-881.

[5]Zhou Yangfan，Michael R L.PORT：a price-oriented reliable transport protocol for wireless sensor networks[C]// Proc of IEEE ISSRE，2005：117-126.

[6]Rahul C S，Jan M R.Energy aware routing for low energy ad hoc sensor networks[C]//Proc of IEEE WCNC，2002：350-355.

[7]Chen T S，Tsai H W，Chu C P.Gathering load balaneed treeprotocol for wireless sensor networks[C]//Procof IEEE SENSORNETS，2006：8-13.

[8]Hull B，Jamiwson K，Balakrishnan H.Bandwidth management in wireless sensor networks[C]//Proc of ACM SENSYS，2003：306-307.

[9]Luo Jun，He Ying.GeoQuorum：load balancing and energy efficientdata accessin wirelesssensornetworks[C]// Proc of IEEE INFOCOM，2011：616-620.

[10]Yu Xiaokang，Ban Xiaomeng，Zeng Wei，et al.Spherical representation and polyhedron routing for load balancing in wireless sensor networks[C]//Proc of IEEE INFOCOM，2011：621-625.

[11]Tijs V D，Koen L.An adaptive energy-efficient MAC protocol forwirelesssensornetworks[C]//Proc ofACM SENSYS，2003：171-180.

[12]Rahim K，Riadh D，André-Luc B.Load balancing techniques for lifetime maximizing in wireless sensor networks[J].Ad Hoc Networks，2013，11（8）：2172-2186.

[13]He Jing，Ji Shouling，Pan Yi，et al.Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks[J].Theoretical Computer Science，2013，507：2-16.

[14]Anju S，Kingsly S R.A secured load balanced clustering algorithm for wireless sensor network[J].International Journal of Research in Computer and Communication Technology，2014，3（4）：517-520.

[15]Chatterjee P，Das N.Coverage constrained non-uniform node deployment in wireless sensor networks for load balancing[C]//Proc of IEEE AIMoC，2014.

XIN Qiangwei,FANG Dingyi

School of Information Science and Technology,Northwest University,Xi’an 710127,China

This paper uses topology to study load balance of wireless sensor networks when sensors are deployed in large scale area randomly.Through the statistical analysis of the number of neighbor nodes of wireless sensor network to study the influence of data flow load balance,the number of neighbor node follows approximately normal distribution when sensors are deployed in large scale area randomly.Its origin lies in the edge effect.Simulation results show that the increase of node communication radius is more difficult to load balance than the increase of deployment density.

wireless sensor networks;load balance;deploy randomly;neighbor node

從結(jié)構(gòu)的角度來研究在大規(guī)模隨機部署時所形成的無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)流負(fù)載平衡。通過統(tǒng)計分析鄰居節(jié)點數(shù)目來分析其對無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)流負(fù)載平衡的影響，發(fā)現(xiàn)在大規(guī)模隨機部署時節(jié)點的鄰居節(jié)點數(shù)目近似服從正態(tài)分布，其成因在于邊緣效應(yīng)。仿真實驗發(fā)現(xiàn)節(jié)點通信半徑的增大比部署密度的增大更不利于負(fù)載平衡。

無線傳感器網(wǎng)絡(luò)；負(fù)載平衡；隨機部署；鄰居節(jié)點

A

TP393

10.3778/j.issn.1002-8331.1404-0272

XIN Qiangwei,FANG Dingyi.Load balance of wireless sensor network with deploying randomly.Computer Engineering and Applications,2014,50（23）：16-20.

國家科技支撐項目（No.2013BAK01B02，No.2013BAK01B05）；國家自然科學(xué)基金（No.61070176，No.61202393）；陜西省科技廳國際合作項目（No.2013KW01-02）。

辛強偉（1980—），男，博士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)的容錯和拓?fù)淇刂?；房鼎益?959—），男，通訊作者，教授，博士生導(dǎo)師，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)、軟件安全和信息安全。E-mail：qiangweifendou@163.com

2014-04-17

2014-06-17

1002-8331（2014）23-0016-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-07-01,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0272.html