邊界節(jié)點對無線傳感器網(wǎng)絡(luò)連通性的影響*

張 強(qiáng)，孫雨耕，劉麗萍

(天津大學(xué)電氣與自動化工程學(xué)院，天津300072)

無線傳感器網(wǎng)絡(luò)自興起以來，在理論研究和應(yīng)用技術(shù)等方面都取得了長足的進(jìn)步，隨著無線傳感器網(wǎng)絡(luò)實用化進(jìn)程的不斷推進(jìn)，最初的設(shè)想正逐步成為現(xiàn)實，在各個應(yīng)用領(lǐng)域中發(fā)揮作用。在無線傳感器網(wǎng)絡(luò)中，連通性是網(wǎng)絡(luò)進(jìn)行可靠數(shù)據(jù)傳輸?shù)幕A(chǔ)，也是網(wǎng)絡(luò)正常運行的必要條件。對于一個有限的監(jiān)測區(qū)域，處于區(qū)域邊界的節(jié)點，與處于區(qū)域內(nèi)部的節(jié)點相比，其鄰居節(jié)點數(shù)要相對較小，從而影響網(wǎng)絡(luò)的整體連通性。這種影響是由于無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域的有限性引起的，也體現(xiàn)在網(wǎng)絡(luò)覆蓋、路由、能耗等多方面，稱為無線傳感器網(wǎng)絡(luò)的邊界效應(yīng)［1］。

邊界效應(yīng)也存在于無線Ad Hoc網(wǎng)絡(luò)，早期的研究主要是針對無線Ad Hoc網(wǎng)絡(luò)，例如為了消除邊界效應(yīng)對網(wǎng)絡(luò)整體連通度的影響，Bettstetter在網(wǎng)絡(luò)仿真驗證過程中，分別采用了只考慮內(nèi)部區(qū)域節(jié)點所形成網(wǎng)絡(luò)的連通度或者用環(huán)面距離(Toroidal Distance)標(biāo)識節(jié)點間的距離等方法，得到了與理論分析相一致的仿真結(jié)果［1－4］。但是對于無線Ad Hoc網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)而言，除非當(dāng)網(wǎng)絡(luò)監(jiān)測區(qū)域的面積無限大時，網(wǎng)絡(luò)不會產(chǎn)生邊界效應(yīng)，否則網(wǎng)絡(luò)邊界是真實存在的，其產(chǎn)生的邊界效應(yīng)也是不可回避的，為此，Brust引入網(wǎng)絡(luò)密度和有效覆蓋面積的概念，分析了網(wǎng)絡(luò)仿真中的邊界效應(yīng)，并給出了一個邊界效應(yīng)修正函數(shù)［5］，但是未對網(wǎng)絡(luò)的整體連通性做進(jìn)一步的研究。此外，還有一些文獻(xiàn)對邊界效應(yīng)下的網(wǎng)絡(luò)覆蓋連通問題進(jìn)行了研究［6－10］，例如Jin對無線傳感器網(wǎng)絡(luò)邊界效應(yīng)下的m－覆蓋、n－連通問題進(jìn)行了研究，并提出了相關(guān)的路由算法［7－9］。

本文對邊界節(jié)點的有效通訊面積、鄰居節(jié)點數(shù)和網(wǎng)絡(luò)的整體連通性進(jìn)行了理論分析，而后通過仿真分析，研究了邊界節(jié)點對網(wǎng)絡(luò)連通度分布、連通度期望以及網(wǎng)絡(luò)是k點連通概率的影響。

1 網(wǎng)絡(luò)模型

本文所采用的網(wǎng)絡(luò)模型為幾何隨機(jī)圖模型G(n，rC)［11］，其中 n 為網(wǎng)絡(luò)的節(jié)點數(shù)，rC表示節(jié)點的通訊半徑。針對連通性問題的研究需要，進(jìn)一步對無線傳感器網(wǎng)絡(luò)做以下假設(shè):

①無線傳感器網(wǎng)絡(luò)節(jié)點隨機(jī)分布在的正方形監(jiān)測區(qū)域S內(nèi)，區(qū)域面積A=l×l，節(jié)點坐標(biāo)(X，Y)在S區(qū)域內(nèi)服從均勻分布，其概率密度函數(shù)為:

②節(jié)點通訊鏈路模型采用0/1模型。節(jié)點采用全向天線通訊，aik為節(jié)點i對節(jié)點k的通訊強(qiáng)度，可表示為:

③除sink節(jié)點外，其他所有節(jié)點都是同構(gòu)的。節(jié)點部署后，sink節(jié)點和其它所有節(jié)點均呈靜態(tài)。

④網(wǎng)絡(luò)的邊界區(qū)域如圖1中陰影部分所示，其面積為S(B)=l2－(l－2rC)2，位于邊界區(qū)域的節(jié)點稱為邊界節(jié)點。

圖1 無線傳感器網(wǎng)絡(luò)中的邊界區(qū)域和邊界節(jié)點

2 邊界節(jié)點的連通性分析

2．1 邊界節(jié)點的有效通訊面積

定義1 節(jié)點的有效通訊面積:節(jié)點通信區(qū)域與網(wǎng)絡(luò)監(jiān)測區(qū)域交集的面積，用Se表示。

對于內(nèi)部節(jié)點，Se(C)=πr2C;對于邊界節(jié)點，先將邊界區(qū)域劃分為兩類B1和B2，如圖2(a)所示。

圖2 邊界節(jié)點的有效通訊面積

在圖2(b)中，位于B1類邊界的節(jié)點有效通訊面積為:

對于位于B2類邊界的節(jié)點，分兩種情況討論，如圖2(c)、(d)所示。

在圖2(c)中，邊界節(jié)點的有效通訊面積為:

各類邊界節(jié)點有效通訊面積的數(shù)學(xué)期望分別為:

節(jié)點在監(jiān)測區(qū)域內(nèi)服從均勻分布，則各類邊界節(jié)點的概率分別為:

則邊界節(jié)點有效通訊面積的數(shù)學(xué)期望為:

2．2 邊界節(jié)點的鄰居節(jié)點數(shù)

對于隨機(jī)均勻分布于面積為A的區(qū)域內(nèi)的n個節(jié)點，文獻(xiàn)［3］給出了在A0區(qū)域內(nèi)恰好存在n0個節(jié)點的概率為:

因此，在邊界節(jié)點的期望有效通訊面積內(nèi)，恰好存在n0個節(jié)點的概率，也就是一個邊界節(jié)點的鄰居節(jié)點數(shù)恰好為(n0－1)的概率為:

令n0=1，則一個邊界節(jié)點成為孤立節(jié)點的概率為:

邊界節(jié)點的鄰居節(jié)點數(shù)期望為:

與邊界節(jié)點相比，因為 E［Se(C)］=πr2C，所以內(nèi)部節(jié)點的鄰居節(jié)點數(shù)期望為:

3 網(wǎng)絡(luò)連通性及仿真分析

3．1 網(wǎng)絡(luò)的連通性分析

對于整個無線傳感器網(wǎng)絡(luò)而言，節(jié)點有效通訊面積的數(shù)學(xué)期望為:

一個節(jié)點的鄰居節(jié)點數(shù)恰好為(n0－1)的概率為:

由此可以推導(dǎo)出，網(wǎng)絡(luò)的最小度δ大于等于n0的概率為:

對于網(wǎng)絡(luò)中每個節(jié)點至少存在k個相鄰節(jié)點，也就是網(wǎng)絡(luò)的最小度δ≥k的情況，由于κ(G)≤λ(G)≤δ(G)(網(wǎng)絡(luò)的點連通度小于等于邊連通度且兩者均小于等于最小度)，所以網(wǎng)絡(luò)是k點連通的概率可用下式表示:

根據(jù)文獻(xiàn)［3］的理論推導(dǎo)結(jié)果，得到當(dāng)n?1，P(δ≥k)→1 時，

3．2 仿真分析

本文選擇在100×100的正方形監(jiān)測區(qū)域內(nèi)對無線傳感器網(wǎng)絡(luò)進(jìn)行仿真。在監(jiān)測區(qū)域內(nèi)多次拋撒節(jié)點形成無線傳感器網(wǎng)絡(luò)，求出每次拋撒所形成的無線傳感器網(wǎng)絡(luò)連通度，再進(jìn)行統(tǒng)計分析，網(wǎng)絡(luò)連通度的計算和統(tǒng)計分析采用文獻(xiàn)［12］使用的方法。本文在仿真過程中將邊界節(jié)點對網(wǎng)絡(luò)連通度的影響與消除邊界效應(yīng)后的網(wǎng)絡(luò)連通度情況進(jìn)行了對比分析，通過文獻(xiàn)［3］所使用的環(huán)面距離(Toroidal Distance)來標(biāo)識上下左右邊界區(qū)域間節(jié)點的距離，以達(dá)到消除網(wǎng)絡(luò)邊界效應(yīng)的目的。

設(shè)節(jié)點通訊半徑rC=20，逐步增加網(wǎng)絡(luò)節(jié)點數(shù)量，取n=20～100，本文從以下幾個方面仿真分析了邊界節(jié)點對網(wǎng)絡(luò)連通性的影響:

(1)邊界節(jié)點對網(wǎng)絡(luò)連通度分布的影響

通過仿真，得到 n=20，40，60，80，100 的網(wǎng)絡(luò)連通度分布如圖3所示，隨著監(jiān)測區(qū)域中節(jié)點數(shù)的增加，網(wǎng)絡(luò)形成較高連通度的概率增加。但是邊界節(jié)點的存在使網(wǎng)絡(luò)形成較高連通度的概率降低，例如當(dāng)n=100，網(wǎng)絡(luò)中存在邊界節(jié)點，該網(wǎng)絡(luò)的連通度為3的概率為0．089 8，如圖3(a)所示;消除網(wǎng)絡(luò)的邊界效應(yīng)，則網(wǎng)絡(luò)的連通度為3的概率為0．321 4，如圖3(b)所示。

(2)邊界節(jié)點對網(wǎng)絡(luò)連通度期望的影響

網(wǎng)絡(luò)的連通度期望用于描述多次拋撒節(jié)點形成網(wǎng)絡(luò)的連通度平均值，邊界節(jié)點的存在使網(wǎng)絡(luò)的連通度期望值減小，例如當(dāng)n=100，存在邊界節(jié)點的網(wǎng)絡(luò)連通度期望值為1．590 8，而消除邊界效應(yīng)后的網(wǎng)絡(luò)連通度期望值為3．770 5，如圖4(a)所示。

圖3 網(wǎng)絡(luò)的連通度分布

圖4 網(wǎng)絡(luò)的連通度期望及擬合曲線

隨網(wǎng)絡(luò)節(jié)點數(shù)增加，網(wǎng)絡(luò)的連通度期望與節(jié)點數(shù)近似成線性關(guān)系(除去節(jié)點數(shù)較低時對應(yīng)的非線性部分)，如圖4(b)所示。本文對網(wǎng)絡(luò)的連通度期望曲線進(jìn)行了多項式擬合，當(dāng)網(wǎng)絡(luò)中存在邊界節(jié)點時，得到下式:

消除網(wǎng)絡(luò)的邊界效應(yīng)，可得:

(3)邊界節(jié)點對網(wǎng)絡(luò)是k點連通概率的影響

“網(wǎng)絡(luò)是k點連通的”指至少刪除k個節(jié)點才能夠是網(wǎng)絡(luò)不連通，與“網(wǎng)絡(luò)的連通度是k”概念不同。邊界節(jié)點的存在使網(wǎng)絡(luò)是k點連通的概率降低，如圖5所示。以n=100為例，消除網(wǎng)絡(luò)的邊界效應(yīng)，網(wǎng)絡(luò)為 1、2、3 點連通的概率分別為:0．998 0，0．962 1，0．846 3;而邊界節(jié)點的存在使網(wǎng)絡(luò)為 1、2、3 點連通的概率降至:0．926 1，0．562 9，0．0958 。

圖5 網(wǎng)絡(luò)是k點連通的概率

式(16)給出了邊界節(jié)點存在時，網(wǎng)絡(luò)是k點連通的概率與網(wǎng)絡(luò)最小度δ≥k的概率的近似對應(yīng)關(guān)系。以n=100為例，網(wǎng)絡(luò)為1點連通的概率為0．926 1，而網(wǎng)絡(luò)的最小度 δ≥1 的概率為0．952 1，存在一定誤差，隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加，該誤差將會減小。

4 結(jié)語

本文以節(jié)點的有效通訊面積為基礎(chǔ)，對邊界節(jié)點的連通性和網(wǎng)絡(luò)的整體連通性進(jìn)行了理論推導(dǎo)，得出邊界節(jié)點有效通訊面積、邊界節(jié)點鄰居節(jié)點數(shù)的數(shù)學(xué)期望，以及邊界節(jié)點存在的情況下，網(wǎng)絡(luò)是k點連通的概率的近似表達(dá)式。而后通過仿真研究，進(jìn)一步分析了存在邊界節(jié)點與消除邊界效應(yīng)后的網(wǎng)絡(luò)連通度分布、連通度期望以及網(wǎng)絡(luò)是k點連通的概率，從而說明了邊界節(jié)點對無線傳感器網(wǎng)絡(luò)連通性的影響，研究結(jié)果可用于指導(dǎo)無線傳感器網(wǎng)絡(luò)的連通性設(shè)計。

［1］ Bettstetter C，Krause O．On Border Effects in Modeling and Simulation of Wireless Ad Hoc Networks［C］//Proceedings of IEEE International Conferenceon Mobile and WirelessCommunication Networks(MWCN)．Recife，Brazil，2001:20 －27．

［2］ Bettstetter C．On the Connectivity of Ad Hoc Metworks［J］．Computer Journal，2004，47(4):432 －447．

［3］ Bettstetter C．On the Minimum Node Degree and Connectivity of a Wireless Multihop Network［C］//Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing(Mobi-Hoc)．Lausanne，Switzerland，2002:80 －91．

［4］ Bettstetter C，Klinglmayr J，Lettner S．On the Degree Distribution of k-Connected Random Networks［C］//Proceedings of 2010 IEEE International Conference on Communications，ICC 2010．Cape Town，South africa，2010．

［5］ Brust M R，Ribeiro C H C，F(xiàn)ilho J A B．Border Effects in the Simulation of Ad Hoc and Sensor Networks［C］//Proceedings of 11th International Conference on Computer Modelling and Simulation．UKSim，2009:180－185．

［6］ Durvy M，Dousse O，Thiran P．Border Effects，F(xiàn)airness，and Phase Transition in Large Wireless Networks［C］//Proceedings of IEEE INFOCOM．Phoenix，AZ，United states，2008:1274 －1282．

［7］ Jin Y，Jo J Y，Wang L，et al．ECCRA:An Energy-Efficient Coverage and Connectivity Preserving Routing Algorithm Under Border Effects in Wireless Sensor Networks［J］．Computer Communications，2008，31(10):2398 －2407．

［8］ Jin Y，Wang L，Jo J Y，et al．EECCR:An Energy-Efficient m-Coverage and n-Connectivity Routing Algorithm Under Border Effects in Heterogeneous Sensor Networks［J］．IEEE Transactions on Vehicular Technology，2009，58(3):1429 －1442．

［9］ Jin Y，Wang L，Yang X，et al．Analysis of Coverage Problem Under Border Effects in Wireless Sensor Networks［J］．High Technology Letters，2008，14(1):61 －66．

［10］ Wan P J，Yi C W．Coverage by Randomly Deployed Wireless Sensor Networks［J］．IEEE Transactions on Information Theory，2006，52(6):2658－2669．

［11］ Bollobás B．Random Graphs Second Edition［M］．Cambridge:Cambridge University Press，2001．

［12］張強(qiáng)，孫雨耕，房朝暉．無線傳感器網(wǎng)絡(luò)k點連通可靠性的研究［J］．傳感技術(shù)學(xué)報，2005，18(3):439 －444．