無線傳感器網絡拓撲連通性與稀疏性研究

任月清，徐立新

(北京理工大學機電學院，北京 100081)

無線傳感器網絡以其獨特的優勢非常適用于惡劣戰場環境下的信息監測，如目標追蹤、戰爭損傷評估、生化攻擊探測等。戰場環境中傳感器節點分布隨機、部署密集，形成的網絡拓撲具有稠密性和復雜性。因此，為了減少節點間通訊干擾，降低網絡能耗，需要對網絡拓撲進行優化，保證網絡在連通的前提下具有一定的稀疏性，從而簡化復雜的路由計算。目前該方面研究工作還處于起步階段，很多問題亟待解決。

近幾年，研究人員從不同角度分析了節點隨機分布的傳感器網絡的連通性與節點密度問題。文獻［1－2］中提到的拓撲控制算法都是通過調整節點發射功率，實現網絡連通，沒有分析節點密度及網絡稀疏性問題。文獻［3］提出當節點通訊半徑是其感知半徑的兩倍時，可以通過OGDC節點密度控制算法實現以最小節點數保證網絡連通，但該算法會增加網絡連邊密度，造成節點間干擾和路由的復雜。文獻［4］發現要保證網絡連通，每個節點至少要有θ(lgn)個鄰居節點與其連接。但對于規模比較大的網絡會存在大量的冗余節點，該算法沒有考慮傳輸半徑會影響節點度的問題，因此也無法從根本解決節點密度與網絡稀疏性的問題。文獻［5］中的LMA和LMN拓撲控制算法是給定節點度的上限和下限，通過節點發射功率的調整確保節點度值落在上限和下限之間。該方法在對節點連邊數進行約束的同時卻很難保證網絡的全連通。文獻［6］提出通過增加節點通信半徑可降低網絡節點密度，進而解決網絡連通性與稀疏性之間的矛盾。但提高通訊半徑會增加功耗，縮短網絡生命周期，并且文中沒有給出具體的實現方法。因此，現有的研究方法或是單純地考慮網絡覆蓋與連通問題，忽略了連邊密度對網絡性能的影響;或是通過限制節點密度或鄰居可達節點數解決網絡的稀疏性問題，但卻無法保證全網的連通。鑒于以上問題，本文將借助復雜網絡理論進一步對網絡節點密度，節點傳輸半徑，節點度等參數與網絡連通性的關系進行研究，提出一種新的拓撲優化算法，通過適當地刪除冗余連接保證網絡既連通又具有稀疏的拓撲結構。

1 網絡模型

對于無線傳感器網絡，可以用幾何連接模型描述節點間的信息傳遞。網絡中n個節點獨立且隨機地分布于指定區域，當一個節點以功率pt發送，另外一個節點以功率pr接收信號時，如果pr大于或等于接收靈敏度pr，th則兩個節點間可建立連接。假設所有節點都具有相同的pt和pr，如果節點間距離小于或等于r=(pt/pr，th)1/α則兩點間存在連邊。其中r稱為傳輸半徑，α為環境路徑損耗指數，通常取2≤α≤5。根據以上定義，無線傳感器網絡拓撲結構可用圖G=G(r，n)表示，其中n為網絡節點數，r為節點傳輸半徑。節點的鄰居個數稱為節點度用d(u)表示，當d(u)=0時表示該節點為孤立節點。網絡G的平均節點度為dmean=(1/n)∑u∈Gd(u)。

對于任意分布，設節點i部署于位置x=(x，y)處，在此前提下節點j依據概率密度函數fx(x')隨機部署。如果節點j位于以節點i為圓心，以傳輸距離r為半徑的圓內，則兩個節點間可建立連邊，如圖1所示。

圖1 網絡拓撲結構

兩節點間建立連邊的概率為［7］:

其中A(x)為當節點i在位置x處時，以該節點為圓心通訊距離r為半徑的圓內區域，fXY(x'，y')為節點分布聯合概率密度函數。通過式(1)可得節點度為d的概率為:

平均節點度為:

研究中主要針對節點均勻分布的情況進行分析，其概率密度函數可以表示為:

其中A為分布區域，式中A表示分布區域面積，在不考慮邊界效應的情況下平均節點度為:

拓撲控制的目的是使網絡拓撲滿足一定的性質，以達到良好的網絡性能，如低能耗，低干擾，高吞吐率等。事實上，對于網絡拓撲的優劣很難直接給出定量的衡量指標。因此，在對網絡拓撲進行評價時往往希望其具有良好的拓撲性質，如連通性、稀疏性、節點度的有界性等［8－9］。其中連通性是必須保證的一個基本性質，是建立網絡的基礎。在一定的區域內，當布撒的傳感器節點數量一定時，節點的傳輸半徑越大，其可達鄰居節點數越多，網絡的連通性也越好。圖2給出了在單位區域內隨機分布100個節點，傳輸半徑分別為5 m，10 m和15 m所對應的網絡拓撲。從圖中可以看出，當傳輸半徑為5 m時存在大量的孤立節點，網路不連通;當傳輸半徑提高到10 m時，孤立節點明顯減少，但孤立簇的存在同樣使得網絡不連通;當傳輸半徑繼續增加達到15 m時，網絡實現了全連通。但與此同時網絡中的通訊鏈路相應增多，這不僅會造成節點間通訊干擾增強，降低通信效率;而且會使網絡的路由選擇更加復雜，增加節點的能量消耗，導致節點過早失效，從而影響網絡的整體性能。

圖2 網絡拓撲隨傳輸半徑的變化情況

2 網絡連通相變特性

由于大多數無線傳感器網絡具有規模大、節點數目多、網絡結構復雜等特點，因此可以被視為復雜網絡［10］。該網絡系統可以視為由許多個體(節點)組成，當這些個體之間的相互作用達到某種臨界水平時，會突然地對網絡的全局特性產生某些影響。這種現象類似于物理中的超導性，當溫度達到臨界值時導體的電阻會突然消失。為了確定無線傳感器網絡的拓撲屬性是否存在同樣現象，研究中重點分析網絡連通性隨傳輸半徑的變化情況。選取單位正方形區域隨機部署100個傳感器節點，假設每個節點的具有相同的傳輸半徑。通過不斷增加傳輸半徑，形成相應的網絡拓撲，由此可計算網絡的連通概率。圖3是網絡連通概率隨傳輸半徑變化的關系曲線。由于網絡節點分布具有很大的隨機性，分析中為了確保數據的可靠，采用多次試驗的方法，圖中曲線上的每個點都是多次試驗的平均結果。

圖3 網絡連通相變特性

從試驗結果不難看出，網絡的連通概率隨著節點傳輸半徑的不斷增加會在某個臨界點處發生突變。臨界點之前網絡連通的概率很低，接近于0;臨界點之后網絡以很高的概率保持連通，并且連通概率很快趨于1。圖中整個區域可以分成三部分:區域A是不希望出現的，因為如果網絡傳輸半徑落在該區域，整個網絡基本不連通，不能進行數據傳遞;區域C是最希望得到的結果，該區域可以保證網絡以很高的概率連通;區域B稱為相變區，是網絡從不連通到連通的一個過渡區域，過渡區域的寬窄與網絡節點密度有關，節點密度越高過渡區域越窄，節點密度越低過渡區域越寬。因此，在實際應用中為了保證連通，就需要網絡的傳輸半徑大于臨界值從而落在相變區域右側。對相變特性的研究，將有利于在網絡設計初期選取合適的網絡參數，為下一步的拓撲優化奠定基礎。

3 稀疏拓撲控制

對于節點密度一定的網絡，傳輸半徑的不斷提高可以實現網絡的連通，但這樣所帶來的問題有兩個:一方面由于節點的電源有限，不斷增加發射功率會使節點能耗增加，促使節點由于能源耗盡而過早失效，影響網絡的連通;另外，當網絡的傳輸半徑不斷增加時，節點間傳輸干擾也會相應增強。因此，網絡的連通性與結構的稀疏性之間相互矛盾，需要在二者間找到最佳平衡點［11－12］，確保網絡性能的最優。

如果想單一地通過功率調節實現網絡連通性與稀疏性的控制，會很困難。因此，本文提出了稀疏網絡拓撲優化算法，該方法首先通過節點功率控制初步形成具有一定冗余的連通網絡，再對網絡中的冗余連邊進行適當刪減從而簡化網絡拓撲。算法的主要目標是對度值較大節點的可達鄰居數進行約束，而選擇哪些連邊進行刪除是問題的關鍵，這就要求對節點在信息傳遞過程中的重要程度進行有效地評價。通常可用度來描述網絡節點的重要程度，度值越大說明節點越重要。對于數據轉發的無線傳感器網絡來說，考慮某一節點對其它節點的影響力更為重要。節點介數測量的就是該點在多大程度上控制其它節點之間的聯系。

3.1 拓撲優化算法

(1)首先，根據已知的設置參數分析網絡連通概率的相變特性，得到相應的相變曲線。在相變區域右側選取適當的傳輸半徑，并初步形成網絡拓撲，保證網絡既連通又存在適當的鏈路冗余。

(2)在已有網絡基礎上，選取部分節點并對其連邊進行適當刪減:

①每輪選取一個節點作為拓撲優化對象，節點i被選中的概率與其節點度成正比，度越大表明節點的連邊中存在的冗余連接越多，因此節點被選中的概率也就越大。

②選定節點i后，需要確定與該節點相連的所有鄰居節點，將其記為集合V={v|vij=1}，并在集合V內選取ρd個節點(其中ρ為刪邊比例，d為節點i的度)。集合V內的節點被選中的概率與節點介數有關，介數越小節點被選中的概率越大。因為，介數小表明該節點在信息傳遞過程中起到的作用不大，如果在下一步中將其與i之間的連邊刪除對整個網絡的影響會很小。

③確定節點i及其在V內的某一個鄰居節點后，判斷該節點對間的連接是否唯一。如果唯一就放棄該鄰居節點返回上一步在集合V中重新選取，如果不唯一就刪除該節點對間的連接。

(3)返回第2步，在除了已經被優化處理的節點范圍內重新選擇節點，重復上述過程，直到網路連邊密度達到預先設定的要求。

3.2 實驗仿真

圖4 初始網絡節點度分布

實驗中將200個傳感器節點隨機分布于A=100 m×100 m的正方形區域內。根據以上參數，對網絡連通的相變特性進行分析，發現為了保證網絡連通應選取R=15 m。圖4為初始網絡節點度分布，從圖中可以看出網絡中節點度值大于等于12的占54%，這樣由于大量節點的度值很大，會造成能耗增加，從而降低網絡壽命。圖5為初始網絡拓撲，網絡中連邊數為1 179，連邊密度較高。圖6為對節點連邊進行約束后的稀疏拓撲，網絡連邊數為656，連邊密度明顯下降。表1為拓撲優化前后網絡主要測度的對比。從結果可以看出網絡連邊密度降低了44%，而網絡的平均最短路徑只增加了15%。優化后的網絡拓撲既簡化了結構又保證了連通，將有利于路由的簡化和網絡生存周期的延長［14］。

圖5 初始網絡拓撲

圖6 刪邊處理后稀疏網絡拓撲

表1 網絡測度對比

4 結論

本文對無線傳感器網絡拓撲的連通性和稀疏性進行了研究，分析了網絡連通概率隨節點傳輸半徑的變化情況。結果表明存在臨界傳輸半徑使網絡的連通概率在其周圍發生0－1相變，當節點傳輸半徑大于臨界值時網絡會以很高的概率保持連通，由此可以確定保證網絡連通的最小傳輸半徑。對網絡連通相變特性的研究有助于在網絡設計初期選擇合適的參數以保證網絡既連通又工作在低功耗區域。此外，在初始連通網絡拓撲的基礎上，文中以度和介數作為節點重要度的綜合衡量指標，提出了稀疏拓撲優化算法，該算法通過對網絡冗余鏈路進行適當地刪減，降低了連邊密度。在保證連通的情況下實現了網絡結構的簡化，這將有利于降低節點間通訊干擾，延長網絡壽命。

［1］張學，陸桑璐，陳貴海，等.無線傳感器網絡的拓撲控制［J］.軟件學報，2007，18(4):943－954.

［2］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［3］Zhang Honghai，Hou Jennifer C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.Ad Hoc ＆ Sensor Wireless Networks，2005，1(1):89－124.

［4］Xue Feng，Kumar P.The number of neighbors needed for connectivity of wireless networks.

［5］Wireless Networks，2004，10(2):169－181.

［6］Kubisch M，Karl H，Wolisz A，et al.Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks［C］//Proc.of the Wireless Communications and Networking Conference(WCNC 2003)，New Orleans，LA.2003，558－563.

［7］陳立軍，毛鶯池，陳道蓄，等.平均度約束的無線傳感器網絡拓撲控制［J］.計算機學報，2007，30(9):1544－1549.

［8］Christian Bettstetter.On the Connectivity of Ad Hoc Networks［J］.The Computer Journal，2004，47(4):432－447.

［9］劉愛平，劉忠，羅亞松.一種水下無線傳感器網絡的連通性覆蓋算法［J］.傳感技術學報，2009，22(1):116－120.

［10］張碩，蒲菊華，劉玉恒，等.無線傳感器網絡覆蓋質量問題［J］.北京航空航天大學學報，2009，35(5):631－635.

［11］Newman M，Strogatz S，Watts D.Random Graphs with Arbitrary Degree Distributions and Their Applications［J］.Physics Reviews E，2001，64(2):26－118.

［12］向滿天，史浩山，李立.無線傳感器網絡的連通覆蓋臨界條件分析［J］.傳感技術學報，2008，21(11):1887－1891.

［13］Santi P.The Critical Transmitting Range for Connectivityin Mobile Ad Hoc Networks［J］.IEEE Transaction on Mobile Computing，2005，4(3):310－317.

［14］唐晉韜，王挺.復雜社會網絡的介數性質近似計算方法研究［J］.計算機工程與科學，2008，30(12):9－14.

［15］劉玉英，史旺旺.一種基于遺傳算法的無線傳感器網絡節點優化方法［J］.傳感技術學報，2009，22(6):869－872.