基于復雜網絡理論的無線傳感器網絡的連通性

耿 鵬，柳 艷

(南京工程學院，江蘇 南京 211167)

?

基于復雜網絡理論的無線傳感器網絡的連通性

耿 鵬，柳 艷

(南京工程學院，江蘇 南京 211167)

針對當前沒有將復雜網絡中的特征量綜合應用到無線傳感器網絡之中的問題，提出了基于復雜網絡理論的無線傳感器網絡連通性分析方法。該方法利用特征量對無線傳感器網絡進行拓撲性質研究，分析了隨機撒點下的網絡由一個連通巨片與若干少量的孤立節點和孤立片組成的特點。通過仿真研究了連通率隨通信半徑變化的規律，以及節點密度與連通性之間的關系。指出了網絡連通率會在臨界區間內迅速上升直至達到基本全連通，并在給定區域條件下確定了臨界區間的具體值?；谄骄葘B通性與覆蓋率進行了仿真分析，給出了簡化無線傳感器網絡拓撲結構的建議。

無線傳感器網絡；復雜網絡；連通性；覆蓋率

0 引言

無線傳感器網絡[1](WSN, Wireless Sensor Networks)在軍事、國家安全、工業控制、特殊環境監控以及氣候變化預測等各個領域有著廣闊的應用前景。隨著物聯網[2](IoT, Internet of Things)技術的不斷快速發展，無線傳感器網絡作為其終端支撐技術，對物體智能化、網絡化的推進起著關鍵作用。與此同時，無線傳感器網絡規模越來也大，逐漸呈現出與簡單網絡不同的統計特性[3]。這種大規模無線傳感器網絡的特性可以用復雜網絡[4-5](CN: Complex Networks)理論加以研究。在無線傳感器網絡的各方面研究中，拓撲控制是其核心問題之一，它對于延長網絡生命周期、減少通信干擾、提高路由和MAC協議效率等方面具有重要意義[6]。拓撲控制的目的在于建立一個利用盡量少的活躍節點實現主要網絡連通及區域覆蓋的拓撲結構[7-8]。

目前基于連通性與覆蓋率的無線傳感器網絡拓撲研究正成為重要方向。文獻[9]討論了網絡連通性與覆蓋率之間的關系，提出了基于地理信息的節點密度控制算法(OGDC, Optimal Geographical Density Control)。文獻[10]提出了一種網絡平均度約束的活躍節點選擇算法，該算法的計算需要花費較長時間。文獻[11]提出了考慮能效性與數據準確到達性的拓撲控制算法。文獻[12-14]利用圖論思想討論了網絡的連通性問題，利用幾個階段來不斷修剪連通支配集，以期達到簡化的網絡結構。上述文獻均沒有將復雜網絡中的特征量綜合應用到無線傳感器網絡之中。本文針對此問題，將鄰接矩陣(Adjacency Matrix)、節點度(Node Degree)和路徑長度(Path Length)等概念引入到無線傳感器網絡的分析之中，提出了基于復雜網絡理論的無線傳感器網絡連通性分析方法。

1 WSN的復雜網絡抽象

復雜網絡理論被廣泛應用在Internet、電力與交通網絡、社會網絡、生物網絡和科研教育網絡等方面[15]。隨著無線傳感器網絡的大規?；c復雜化發展，復雜網絡中的特征值也可以用來描述無線傳感器網絡。

1.1 圖與鄰接矩陣

(1)

顯然，對任意的節點i和節點j，有aij=aji，對于網絡的連接邊數，只需要統計矩陣A的上三角或下三角部分值為1的數量即可，所以連接邊數

(2)

1.2 節點度

節點度定義為與某節點直接相連的邊的數目，節點i的度記為ki，對基于簡單圖的無線傳感器網絡而言，節點度描述的是與該節點相連的鄰居節點數目。網絡中所有節點度的平均值叫做網絡平均度(Average Degree)，記為〈k〉，根據鄰接矩陣的概念，對于具有N個節點的網絡，有

(3)

(4)

2 基于復雜網絡的WSN連通性

無線傳感器網絡之所以稱之為網絡，就是其中的節點是連通的，網絡的連通性與節點密度、節點通信半徑以及各節點之間存在的路徑均相關。

2.1 路徑與連通性

在集合V中，若存在一個節點序列v=v1,v2, …,vk，其中每對相鄰的節點(即vi與vi+1)之間均存在連接邊，則稱v為v1到vk的一條路徑。無線傳感器網絡中兩個節點i與j之間的路徑長度定義為此路徑所包含的最少連接邊數，記作dij。對具有N個節點的網絡，平均路徑長度(Average Path Length)描述為：

(5)

如果某區域中的每兩個節點之間均存在路徑，則稱此區域是連通的，稱為連通片(Connected Component)。無線傳感器網絡是由多個連通片組成的，但我們總希望大多數節點是連通的，這樣便形成了連通巨片(Giant Connected Component)。如果綜合考慮了節點通信半徑、節點數量與探測目標區域大小之間的關系，在隨機撒點的條件下，無線傳感器網絡往往由一個連通巨片與若干少量的孤立節點和孤立片組成，如圖1所示。

圖1 隨機撒點下的網絡結構圖Fig.1 Network structure by random deploying

無線傳感器網絡的特點是感知信息總是由普通節點向sink節點匯集，可以形象的看作是從樹葉向樹根匯集。則最簡單的樹可以從sink節點開始，查找其鄰居節點，再查找鄰居的鄰居(之前已找到的節點排除在外)，依次下去，就可以得到包含sink節點的樹，并且可以計算每個節點與sink節點之間的路徑長度。這種算法被叫做廣度優先搜索算法(Breadth-first Search Algorithm)[16]。假設sink節點位于被測區域中心位置，一種利用此算法生成的無線傳感器網絡拓撲如圖2所示?？梢钥闯?，此算法在保證節點全連通的情況下，對拓撲結構進行了較大簡化。

圖2 廣度優先搜索算法生成樹狀圖Fig.2 Generate tree by Breadth-first Search Algorithm

2.2 通信半徑與連通性

對于給定區域、給定節點數量的無線傳感器網絡而言，要想提高網絡連通性，最直接的辦法就是提高節點通信半徑，但通信半徑的提高無疑意味著網絡能耗的增加。無線傳感器網絡中的節點能量往往受限，所以討論當通信半徑增加到多少時，能夠使得網絡基本連通是有必要的。仿真基于Java平臺，給定1 000×1 000 m2的區域，隨機撒點800個節點，通信半徑從10 m開始，依次遞增10 m，直到節點達到全連通時結束遞增。經過10次實驗取平均值，可以得到圖3的仿真結果。

圖3 連通率隨通信半徑變化圖Fig.3 The connectivity rate varies with the communication radius

從仿真結果可以看出，當通信半徑在10 m到50 m時，網絡連通率基本為0，而當通信半徑繼續增加時，連通率發生突變，并且隨著通信半徑的增加而迅速上升，在80 m處可達到95%以上的基本全連通。因此，在本實驗條件下，可以把(50, 80)看作臨界區間，網絡連通率會在臨界區間內迅速上升直至達到基本全連通。顯然，臨界區間的具體值與節點密度相關。如果定義無線傳感器網絡節點密度為節點數與所探測對象面積的比值，則可以繼續分析節點密度與臨界區間的關系。在上述實驗基礎上，將節點數從100到2 000進行增加，再次仿真得到如圖4所示的節點密度與臨界區上下限的關系。從仿真圖中可以看出，隨著節點密度的增加，達到基本全連通所需的通信半徑越來越小，臨界區間也變得越來越窄。當節點密度大于1.3‰時，臨界區間上限與下限的差值穩定在20 m，可以將此值作為在保證連通性的情況下獲得較低經濟成本的參考值。

圖4 節點密度與連通性Fig.4 Node density and connectivity

3 基于平均度的連通性與覆蓋率仿真分析

無線傳感器網絡的某個節點的度描述的是與該節點相連的鄰居節點數目。顯然對整個網絡而言，網絡平均度越高，連通性越好。假設探測對象、節點通信半徑和節點數量一定，那么平均度越高，則意味著網絡中的節點集中度越高。在此情況下，雖然網絡連通性得到了保證，但覆蓋率卻會由于節點的過于集中而降低。在實際應用中，往往通過適當降低連通巨片的平均度來精簡網絡活動節點數量，以獲得更高的能量利用率和更長的生命周期。因此分析平均度與連通性及覆蓋率之間的關系，可以直觀地知道應該將平均度降低多少，才不會對網絡連通性和覆蓋率造成較大影響。本文將通過仿真分析的方法來討論此問題，仿真參數仍然按照2.2節進行設置，假設節點通信半徑與感知半徑相等，經過10次實驗取平均值，可以得到如表1和圖5的仿真結果。可以看出，使得連通率與覆蓋率均達到95%以上所對應的節點通信半徑為80 m，網絡平均度約為15。

表1 連通性與覆蓋率數據表

圖5 連通性與覆蓋率仿真圖Fig.5 Connectivity and coverage simulation

根據上述實驗，可將連通率與覆蓋率均達到95%作為前提條件(保證網絡的巨片覆蓋特性)，隨機將節點度大于網絡平均度的節點切換到睡眠狀態(若檢測到某節點的睡眠破壞了連通率或覆蓋率，則取消睡眠)，網絡運行過程中，當連通率或覆蓋率降低時，再隨機恢復處于睡眠狀態的節點，這樣便可節約網絡能量，提高生命周期。

4 結論

本文提出了基于復雜網絡理論的無線傳感器網絡連通性分析方法。該方法利用復雜網絡的特征量對無線傳感器網絡進行拓撲性質研究，分析了隨機撒點下的網絡由一個連通巨片與若干少量的孤立節點和孤立片組成的特點。通過仿真研究了連通率隨通信半徑變化的規律，以及節點密度與連通性之間的關系，指出了網絡連通率會在臨界區間內迅速上升直至達到基本全連通，并在給定區域條件下確定了臨界區間的具體值?；谄骄葘B通性與覆蓋率進行了仿真分析，給出了簡化無線傳感器網絡拓撲結構的建議。下一步的研究重點是在保證連通率與覆蓋率的前提條件下，設計具體的減少活動節點的方案，以保證網絡的整體性能。

[1]Manges W. It’s Time for Sensors to Go Wireless[J]. Sensors Magazine， 1999:4-6.

[2]Internet of Things[EB/OL]. http://en.wikipedia.org/wiki/Internet of Things.

[3]羅自強, 李德毅. 無線傳感器網絡的概率統計分析[J]. 探測與控制學報, 2007, 29(2): 16-19.

[4]Albert R, Barabasi A L. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002,74(1):47-97.

[5]Boccaletti S, Latora V, Moreno Y, et al. Complex networks:structure and dynamics[J]. Physics Reports,2006,424(4-5):175-308.

[6]張學, 陸桑璐, 陳貴海. 無線傳感器網絡的拓撲控制[J]. 軟件學報, 2007, 18(4): 943-954.

[7]Winghtman P, Labrador M. Atarraya: A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Networks[C]// Proceedings of the 2nd Internotional Conference on Simulation Tods and Techniques for Communications, Networks and Systerms. ICST SIMUTools, 2009.

[8]Zhu Chuan, Zheng Chunlin, Shu Lei, et al. A survey on coverage and connectivity issues in wireless sensor networks[J]. Journal of Network and Computer Applications, 2012, 35(2):619-632.

[9]ZHANG H, HOU JC. Maintaining sensing coverage and connectivity in large sensor networks[J]. Wireless Ad Hoc and Sensor Networks, 2005, 1(1): 89-123.

[10]Ji Shouling, Fan Pingzhi, Pan Yi, et al. Constructing a load-balanced virtual backbone in Wireless Sensor Networks[C]// Proceedings of International Conference on Computing Networking and Communications. Maui, Hawaii, USA, 2012:147-163.

[11]Mohamed Hefeeda, Hossein Ahmadi. Energy Efficient Protocol for Deterministic and Probabilistic Coverage in Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(5):579-593.

[12]Yu JG, Deng X, Yu DX, et al. CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks[J]. AEU-INTERNATIONAL JOURNAL OF ELECTRONICS AND COMMUNICATIONS, 2013, 67 (11): 937-946.

[13]Ammari Habib M, Sajal K Das. Centralized and Clustered k-Coverage Protocols for Wireless Sensor Networks[J]. IEEE Transactions on Computers, 2012, 61(1):118-133.

[14]Habib M Ammari. On the problem of k-coverage in mission-oriented mobile wireless sensor networks[J]. COMPUTER NETWORKS, 2012, 56(7): 1935-1950.

[15]汪小帆, 李翔, 陳關榮. 網絡科學導論[M]. 北京：高等教育出版社, 2012: 1-21.

[16]Vahid Khalilpour Akram, Orhan Dagdeviren. Breadth-First Search-Based Single-Phase Algorithms for Bridge Detection in Wireless Sensor Networks[J].Sensors, 2013(13): 8786-8813.

Connectivity of Wireless Sensor Complex Networks

GENG Peng, LIU Yan

(Nanjing Institute of Technology, Nanjing 211167, China)

Aiming at the problem that the feature amount of complex networks are not applied to wireless sensor networks, a method for analyzing the connectivity of wireless sensor networks based on complex network theory was presented in this paper. The topological property of the wireless sensor networks is studied based on the feature amount. When sensors were random deployed, we considered the network was composed by giant connected component, a few isolated nodes and isolated sheet. Through simulation, the relationship between the change of the connectivity and the radius of the communication and the relationship between the density of nodes and the connectivity of the nodes were studied. The network connectivity rate rose rapidly until the critical interval was reached, and the value of the critical interval was determined by the given region. A simulation about connectivity and coverage based on the average degree was analyzed.

wireless sensor networks; complex networks; connectivity; coverage

2016-05-04

南京工程學院校級科研基金項目資助(QKJB201405)

耿鵬(1979—)，男，湖北鐘祥人，講師，研究方向：無線傳感器網絡，復雜網絡，嵌入式系統。E-mail:huayiliu2000@126.com。

TP393

A

1008-1194(2016)05-0123-05