基于復(fù)雜網(wǎng)絡(luò)理論的無(wú)線傳感器網(wǎng)絡(luò)的連通性

耿 鵬，柳 艷

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

?

基于復(fù)雜網(wǎng)絡(luò)理論的無(wú)線傳感器網(wǎng)絡(luò)的連通性

耿 鵬，柳 艷

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

針對(duì)當(dāng)前沒(méi)有將復(fù)雜網(wǎng)絡(luò)中的特征量綜合應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)之中的問(wèn)題，提出了基于復(fù)雜網(wǎng)絡(luò)理論的無(wú)線傳感器網(wǎng)絡(luò)連通性分析方法。該方法利用特征量對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行拓?fù)湫再|(zhì)研究，分析了隨機(jī)撒點(diǎn)下的網(wǎng)絡(luò)由一個(gè)連通巨片與若干少量的孤立節(jié)點(diǎn)和孤立片組成的特點(diǎn)。通過(guò)仿真研究了連通率隨通信半徑變化的規(guī)律，以及節(jié)點(diǎn)密度與連通性之間的關(guān)系。指出了網(wǎng)絡(luò)連通率會(huì)在臨界區(qū)間內(nèi)迅速上升直至達(dá)到基本全連通，并在給定區(qū)域條件下確定了臨界區(qū)間的具體值。基于平均度對(duì)連通性與覆蓋率進(jìn)行了仿真分析，給出了簡(jiǎn)化無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的建議。

無(wú)線傳感器網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)；連通性；覆蓋率

0 引言

無(wú)線傳感器網(wǎng)絡(luò)[1](WSN, Wireless Sensor Networks)在軍事、國(guó)家安全、工業(yè)控制、特殊環(huán)境監(jiān)控以及氣候變化預(yù)測(cè)等各個(gè)領(lǐng)域有著廣闊的應(yīng)用前景。隨著物聯(lián)網(wǎng)[2](IoT, Internet of Things)技術(shù)的不斷快速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)作為其終端支撐技術(shù)，對(duì)物體智能化、網(wǎng)絡(luò)化的推進(jìn)起著關(guān)鍵作用。與此同時(shí)，無(wú)線傳感器網(wǎng)絡(luò)規(guī)模越來(lái)也大，逐漸呈現(xiàn)出與簡(jiǎn)單網(wǎng)絡(luò)不同的統(tǒng)計(jì)特性[3]。這種大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的特性可以用復(fù)雜網(wǎng)絡(luò)[4-5](CN: Complex Networks)理論加以研究。在無(wú)線傳感器網(wǎng)絡(luò)的各方面研究中，拓?fù)淇刂剖瞧浜诵膯?wèn)題之一，它對(duì)于延長(zhǎng)網(wǎng)絡(luò)生命周期、減少通信干擾、提高路由和MAC協(xié)議效率等方面具有重要意義[6]。拓?fù)淇刂频哪康脑谟诮⒁粋€(gè)利用盡量少的活躍節(jié)點(diǎn)實(shí)現(xiàn)主要網(wǎng)絡(luò)連通及區(qū)域覆蓋的拓?fù)浣Y(jié)構(gòu)[7-8]。

目前基于連通性與覆蓋率的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)溲芯空蔀橹匾较?。文獻(xiàn)[9]討論了網(wǎng)絡(luò)連通性與覆蓋率之間的關(guān)系，提出了基于地理信息的節(jié)點(diǎn)密度控制算法(OGDC, Optimal Geographical Density Control)。文獻(xiàn)[10]提出了一種網(wǎng)絡(luò)平均度約束的活躍節(jié)點(diǎn)選擇算法，該算法的計(jì)算需要花費(fèi)較長(zhǎng)時(shí)間。文獻(xiàn)[11]提出了考慮能效性與數(shù)據(jù)準(zhǔn)確到達(dá)性的拓?fù)淇刂扑惴?。文獻(xiàn)[12-14]利用圖論思想討論了網(wǎng)絡(luò)的連通性問(wèn)題，利用幾個(gè)階段來(lái)不斷修剪連通支配集，以期達(dá)到簡(jiǎn)化的網(wǎng)絡(luò)結(jié)構(gòu)。上述文獻(xiàn)均沒(méi)有將復(fù)雜網(wǎng)絡(luò)中的特征量綜合應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)之中。本文針對(duì)此問(wèn)題，將鄰接矩陣(Adjacency Matrix)、節(jié)點(diǎn)度(Node Degree)和路徑長(zhǎng)度(Path Length)等概念引入到無(wú)線傳感器網(wǎng)絡(luò)的分析之中，提出了基于復(fù)雜網(wǎng)絡(luò)理論的無(wú)線傳感器網(wǎng)絡(luò)連通性分析方法。

1 WSN的復(fù)雜網(wǎng)絡(luò)抽象

復(fù)雜網(wǎng)絡(luò)理論被廣泛應(yīng)用在Internet、電力與交通網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和科研教育網(wǎng)絡(luò)等方面[15]。隨著無(wú)線傳感器網(wǎng)絡(luò)的大規(guī)模化與復(fù)雜化發(fā)展，復(fù)雜網(wǎng)絡(luò)中的特征值也可以用來(lái)描述無(wú)線傳感器網(wǎng)絡(luò)。

1.1 圖與鄰接矩陣

(1)

顯然，對(duì)任意的節(jié)點(diǎn)i和節(jié)點(diǎn)j，有aij=aji，對(duì)于網(wǎng)絡(luò)的連接邊數(shù)，只需要統(tǒng)計(jì)矩陣A的上三角或下三角部分值為1的數(shù)量即可，所以連接邊數(shù)

(2)

1.2 節(jié)點(diǎn)度

節(jié)點(diǎn)度定義為與某節(jié)點(diǎn)直接相連的邊的數(shù)目，節(jié)點(diǎn)i的度記為ki，對(duì)基于簡(jiǎn)單圖的無(wú)線傳感器網(wǎng)絡(luò)而言，節(jié)點(diǎn)度描述的是與該節(jié)點(diǎn)相連的鄰居節(jié)點(diǎn)數(shù)目。網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值叫做網(wǎng)絡(luò)平均度(Average Degree)，記為〈k〉，根據(jù)鄰接矩陣的概念，對(duì)于具有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，有

(3)

(4)

2 基于復(fù)雜網(wǎng)絡(luò)的WSN連通性

無(wú)線傳感器網(wǎng)絡(luò)之所以稱之為網(wǎng)絡(luò)，就是其中的節(jié)點(diǎn)是連通的，網(wǎng)絡(luò)的連通性與節(jié)點(diǎn)密度、節(jié)點(diǎn)通信半徑以及各節(jié)點(diǎn)之間存在的路徑均相關(guān)。

2.1 路徑與連通性

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

(5)

如果某區(qū)域中的每?jī)蓚€(gè)節(jié)點(diǎn)之間均存在路徑，則稱此區(qū)域是連通的，稱為連通片(Connected Component)。無(wú)線傳感器網(wǎng)絡(luò)是由多個(gè)連通片組成的，但我們總希望大多數(shù)節(jié)點(diǎn)是連通的，這樣便形成了連通巨片(Giant Connected Component)。如果綜合考慮了節(jié)點(diǎn)通信半徑、節(jié)點(diǎn)數(shù)量與探測(cè)目標(biāo)區(qū)域大小之間的關(guān)系，在隨機(jī)撒點(diǎn)的條件下，無(wú)線傳感器網(wǎng)絡(luò)往往由一個(gè)連通巨片與若干少量的孤立節(jié)點(diǎn)和孤立片組成，如圖1所示。

圖1 隨機(jī)撒點(diǎn)下的網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1 Network structure by random deploying

無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)是感知信息總是由普通節(jié)點(diǎn)向sink節(jié)點(diǎn)匯集，可以形象的看作是從樹(shù)葉向樹(shù)根匯集。則最簡(jiǎn)單的樹(shù)可以從sink節(jié)點(diǎn)開(kāi)始，查找其鄰居節(jié)點(diǎn)，再查找鄰居的鄰居(之前已找到的節(jié)點(diǎn)排除在外)，依次下去，就可以得到包含sink節(jié)點(diǎn)的樹(shù)，并且可以計(jì)算每個(gè)節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的路徑長(zhǎng)度。這種算法被叫做廣度優(yōu)先搜索算法(Breadth-first Search Algorithm)[16]。假設(shè)sink節(jié)點(diǎn)位于被測(cè)區(qū)域中心位置，一種利用此算法生成的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淙鐖D2所示?？梢钥闯?，此算法在保證節(jié)點(diǎn)全連通的情況下，對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行了較大簡(jiǎn)化。

圖2 廣度優(yōu)先搜索算法生成樹(shù)狀圖Fig.2 Generate tree by Breadth-first Search Algorithm

2.2 通信半徑與連通性

對(duì)于給定區(qū)域、給定節(jié)點(diǎn)數(shù)量的無(wú)線傳感器網(wǎng)絡(luò)而言，要想提高網(wǎng)絡(luò)連通性，最直接的辦法就是提高節(jié)點(diǎn)通信半徑，但通信半徑的提高無(wú)疑意味著網(wǎng)絡(luò)能耗的增加。無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量往往受限，所以討論當(dāng)通信半徑增加到多少時(shí)，能夠使得網(wǎng)絡(luò)基本連通是有必要的。仿真基于Java平臺(tái)，給定1 000×1 000 m2的區(qū)域，隨機(jī)撒點(diǎn)800個(gè)節(jié)點(diǎn)，通信半徑從10 m開(kāi)始，依次遞增10 m，直到節(jié)點(diǎn)達(dá)到全連通時(shí)結(jié)束遞增。經(jīng)過(guò)10次實(shí)驗(yàn)取平均值，可以得到圖3的仿真結(jié)果。

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

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

圖4 節(jié)點(diǎn)密度與連通性Fig.4 Node density and connectivity

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

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

表1 連通性與覆蓋率數(shù)據(jù)表

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

根據(jù)上述實(shí)驗(yàn)，可將連通率與覆蓋率均達(dá)到95%作為前提條件(保證網(wǎng)絡(luò)的巨片覆蓋特性)，隨機(jī)將節(jié)點(diǎn)度大于網(wǎng)絡(luò)平均度的節(jié)點(diǎn)切換到睡眠狀態(tài)(若檢測(cè)到某節(jié)點(diǎn)的睡眠破壞了連通率或覆蓋率，則取消睡眠)，網(wǎng)絡(luò)運(yùn)行過(guò)程中，當(dāng)連通率或覆蓋率降低時(shí)，再隨機(jī)恢復(fù)處于睡眠狀態(tài)的節(jié)點(diǎn)，這樣便可節(jié)約網(wǎng)絡(luò)能量，提高生命周期。

4 結(jié)論

本文提出了基于復(fù)雜網(wǎng)絡(luò)理論的無(wú)線傳感器網(wǎng)絡(luò)連通性分析方法。該方法利用復(fù)雜網(wǎng)絡(luò)的特征量對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行拓?fù)湫再|(zhì)研究，分析了隨機(jī)撒點(diǎn)下的網(wǎng)絡(luò)由一個(gè)連通巨片與若干少量的孤立節(jié)點(diǎn)和孤立片組成的特點(diǎn)。通過(guò)仿真研究了連通率隨通信半徑變化的規(guī)律，以及節(jié)點(diǎn)密度與連通性之間的關(guān)系，指出了網(wǎng)絡(luò)連通率會(huì)在臨界區(qū)間內(nèi)迅速上升直至達(dá)到基本全連通，并在給定區(qū)域條件下確定了臨界區(qū)間的具體值?；谄骄葘?duì)連通性與覆蓋率進(jìn)行了仿真分析，給出了簡(jiǎn)化無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的建議。下一步的研究重點(diǎn)是在保證連通率與覆蓋率的前提條件下，設(shè)計(jì)具體的減少活動(dòng)節(jié)點(diǎn)的方案，以保證網(wǎng)絡(luò)的整體性能。

[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]羅自強(qiáng), 李德毅. 無(wú)線傳感器網(wǎng)絡(luò)的概率統(tǒng)計(jì)分析[J]. 探測(cè)與控制學(xué)報(bào), 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]張學(xué), 陸桑璐, 陳貴海. 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J]. 軟件學(xué)報(bào), 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]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[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

南京工程學(xué)院校級(jí)科研基金項(xiàng)目資助(QKJB201405)

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

TP393

A

1008-1194(2016)05-0123-05