張 強，孫雨耕，劉麗萍

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

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

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

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

1 網絡模型

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

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

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

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

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

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

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

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

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

對于內部節(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ù)學期望分別為:

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

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

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

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

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

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

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

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

3 網絡連通性及仿真分析

3．1 網絡的連通性分析

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

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

由此可以推導出，網絡的最小度δ大于等于n0的概率為:

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

根據(jù)文獻［3］的理論推導結果，得到當n?1，P(δ≥k)→1 時，

3．2 仿真分析

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

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

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

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

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

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

圖3 網絡的連通度分布

圖4 網絡的連通度期望及擬合曲線

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

消除網絡的邊界效應，可得:

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

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

圖5 網絡是k點連通的概率

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

4 結語

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

［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］張強，孫雨耕，房朝暉．無線傳感器網絡k點連通可靠性的研究［J］．傳感技術學報，2005，18(3):439 －444．