基于小世界模型的無線傳感器網(wǎng)絡(luò)層次型路由算法

韋世紅，唐起超

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)(*通信作者電子郵箱2075721094@qq.com)

基于小世界模型的無線傳感器網(wǎng)絡(luò)層次型路由算法

韋世紅，唐起超*

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)(*通信作者電子郵箱2075721094@qq.com)

層次型路由算法是無線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)領(lǐng)域。針對(duì)傳感器節(jié)點(diǎn)能量受限問題，提出一種基于小世界模型的無線傳感器網(wǎng)絡(luò)層次型路由算法(HASWNM)。通過添加高性能節(jié)點(diǎn)以及在簇頭間添加捷徑的方法，使得無線傳感器網(wǎng)絡(luò)(WSN)體現(xiàn)出小世界網(wǎng)絡(luò)特性。由于能量消耗主要集中在數(shù)據(jù)發(fā)送階段，因此該算法在簇間中繼選擇時(shí)考慮了簇頭自身的能量問題。此外，根據(jù)簇頭節(jié)點(diǎn)距離基站的位置遠(yuǎn)近，確定不同的自適應(yīng)搜索區(qū)域。實(shí)驗(yàn)結(jié)果證明，當(dāng)高性能節(jié)點(diǎn)個(gè)數(shù)為100時(shí)，網(wǎng)絡(luò)中可以呈現(xiàn)出小世界特性。與CSWN、TSWN、DASM相比，該算法第一個(gè)節(jié)點(diǎn)的死亡輪數(shù)分別延遲了6%，6%，29%，每一輪網(wǎng)絡(luò)中的平均能量消耗分別減少了5%，12%，17%。因此，該算法構(gòu)造的無線傳感器網(wǎng)絡(luò)具有小世界特性，并且能量消耗較低。

無線傳感器網(wǎng)絡(luò)；聚類系數(shù)；平均路徑長度；能量損耗

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

小世界網(wǎng)絡(luò)的本質(zhì)特征是具有小的平均路徑長度和大的聚類系數(shù)[1]，將復(fù)雜網(wǎng)絡(luò)的小世界現(xiàn)象引入無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)的研究，對(duì)分析WSN的拓?fù)浣Y(jié)構(gòu)、發(fā)現(xiàn)WSN中隱藏的規(guī)律以及預(yù)測WSN的行為具有十分重要的理論意義。

1)平均路徑長度：平均路徑長度定義為所有節(jié)點(diǎn)間通信距離的平均值。計(jì)算公式如式(1)所示：

(1)

其中：N表示的是傳感器節(jié)點(diǎn)的數(shù)量，dij表示的是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的通信距離實(shí)際存在的邊條數(shù)。

對(duì)小世界WSN平均路徑長度的計(jì)算，目前還沒有非常精確的解析表達(dá)式，如果小世界WSN通過“隨機(jī)化重連”構(gòu)成，則平均路徑長度如式(2)所示：

(2)

其中：N表示的是傳感器節(jié)點(diǎn)個(gè)數(shù)，K表示的是節(jié)點(diǎn)度數(shù)，p為重連概率，f(x)表示的是普適標(biāo)度函數(shù)。

普適標(biāo)度函數(shù)f(x)基于平均場方法給出：

(3)

當(dāng)節(jié)點(diǎn)的平均度固定時(shí)，平均路徑長度的增加速度與N的對(duì)數(shù)成正比。表明基于小世界的無線傳感器網(wǎng)絡(luò)其平均路徑長度較小，且對(duì)于隨機(jī)故障具有較強(qiáng)的魯棒性。

2).聚類系數(shù)C：聚類系數(shù)描述了節(jié)點(diǎn)i與其直接相連的鄰居節(jié)點(diǎn)的連接關(guān)系，如式(4)所示：

Ci=3NΔ(i)/N3(i)

(4)

其中：NΔ(i)表示的是該網(wǎng)絡(luò)中包含節(jié)點(diǎn)i的三角形總數(shù)，N3(i)表示包含節(jié)點(diǎn)i的三元組總數(shù)。

對(duì)部分聚類系數(shù)較小的邊進(jìn)行一些必要的選擇性刪改，可提高網(wǎng)絡(luò)整體的平均聚類系數(shù)，從而達(dá)到簡化拓?fù)浣Y(jié)構(gòu)、優(yōu)化路徑選擇的效果。

廣大學(xué)者提出了很多無線傳感器網(wǎng)絡(luò)小世界特性的構(gòu)造方法。文獻(xiàn)[2]提出了基于NW(Newman-Watts)小世界WSN的構(gòu)造方法，但是網(wǎng)絡(luò)的抗毀性較差，性能低，造價(jià)昂貴。文獻(xiàn)[3]提出了基于匯聚節(jié)點(diǎn)(sink node)構(gòu)造小世界WSN，抗毀性較差，適用于小規(guī)模的網(wǎng)絡(luò)。文獻(xiàn)[4]提出了基于拓?fù)鋬?yōu)化的小世界WSN構(gòu)造，該算法形成了一種靜態(tài)拓?fù)?，抗毀性適中，網(wǎng)絡(luò)規(guī)模適中。

針對(duì)現(xiàn)有算法的不足以及經(jīng)驗(yàn)，本文提出了一種基于小世界特性的無線傳感網(wǎng)層次型路由算法(Hierarchical routing Algorithm for wireless sensor networks based on Small World Network Model, HASWNM)，通過添加高性能節(jié)點(diǎn)以及在簇頭間添加捷徑的方法，使得無線傳感器網(wǎng)絡(luò)體現(xiàn)出小世界特性。該算法在簇間中繼選擇時(shí)候考慮了簇頭自身的能量問題，達(dá)到了很好的節(jié)能效果。

2 本文算法

2.1 系統(tǒng)模型

1)N個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在M×M的正方形監(jiān)控區(qū)域內(nèi)，傳感器節(jié)點(diǎn)分為普通節(jié)點(diǎn)和高性能節(jié)點(diǎn)。節(jié)點(diǎn)通過ID(Identification)進(jìn)行標(biāo)識(shí)，并且存儲(chǔ)、計(jì)算能量受限。

2)傳感器節(jié)點(diǎn)一旦被部署，則一直處于靜止?fàn)顟B(tài)。

3)sink節(jié)點(diǎn)存儲(chǔ)、計(jì)算能量不受限，并且sink節(jié)點(diǎn)是固定的。

4)假設(shè)節(jié)點(diǎn)i的通信半徑為Rc(i)，節(jié)點(diǎn)j的通信半徑為Rc(j)，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離為dij，那么節(jié)點(diǎn)i和節(jié)j能夠直接通信的充要條件[5]是Rc(i)≤dij∧Rc(j)≤dij。

2.2 基本概念

定義1 兩個(gè)高性能節(jié)點(diǎn)之間的鏈接成為捷徑[6]。

定義2 高性能節(jié)點(diǎn)間的鏈接概率用p表示。

定義3 假設(shè)普通節(jié)點(diǎn)的通信半徑為RL，高性能節(jié)點(diǎn)的通信半徑為RH，在實(shí)驗(yàn)的過程中保證RH?RL。

2.3 算法描述

算法是以輪數(shù)為單位，每一輪主要分為簇的劃分以及簇頭的選擇，簇頭的選擇根據(jù)數(shù)據(jù)傳輸?shù)目煽啃?；選擇出來的簇頭節(jié)點(diǎn)同時(shí)進(jìn)行鏈路構(gòu)建，包括候選捷徑端點(diǎn)的確定以及捷徑端點(diǎn)的確定；最后完成數(shù)據(jù)的通信過程。具體的流程如圖1所示。

圖1 算法流程

1)對(duì)監(jiān)控區(qū)域進(jìn)行隨機(jī)撒點(diǎn)，主要分為兩類傳感器節(jié)點(diǎn)，具有高能量的傳感器節(jié)點(diǎn)(High-energy sensor node, H-sensor)和具有低能量的傳感器節(jié)點(diǎn)(Low-energy sensor node, L-sensor)。其中，高性能節(jié)點(diǎn)的個(gè)數(shù)應(yīng)該大于等于簇頭節(jié)點(diǎn)的數(shù)目，其余的是低能量的普通節(jié)點(diǎn)，這樣做的好處就是盡可能地保證每個(gè)簇內(nèi)都具有高性能節(jié)點(diǎn)。擁有高能量的傳感器節(jié)點(diǎn)具有較大的通信半徑RH，擁有低能量的傳感器節(jié)點(diǎn)具有較小的通信半徑RL。

2)簇的建立階段分為鄰居發(fā)現(xiàn)階段、控制數(shù)據(jù)廣播以及網(wǎng)絡(luò)配置。在鄰居發(fā)現(xiàn)階段，所有的傳感器節(jié)點(diǎn)廣播一個(gè)帶有自己ID號(hào)的hello包，收到hello包的傳感器節(jié)點(diǎn)會(huì)更新自己的鄰居表和接收信號(hào)強(qiáng)度(Receive Signal Strength Indicator, RSSI)?？刂茢?shù)據(jù)廣播，該算法使用泛洪的方法傳輸控制數(shù)據(jù)到基站，每個(gè)傳感器節(jié)點(diǎn)的控制信息包括自身的ID號(hào)、剩余能量和它的鄰居表數(shù)據(jù)。中繼節(jié)點(diǎn)接收到數(shù)據(jù)包會(huì)繼續(xù)廣播直到數(shù)據(jù)包傳輸?shù)交緸橹?。網(wǎng)絡(luò)配置階段，當(dāng)基站收到網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)的控制包時(shí)，基站開始配置網(wǎng)絡(luò)。配置廣播，當(dāng)基站完成網(wǎng)絡(luò)配置，以泛洪的方式向所有的傳感器節(jié)點(diǎn)廣播網(wǎng)絡(luò)配置，對(duì)子區(qū)域進(jìn)行劃分。每個(gè)傳感器節(jié)點(diǎn)根據(jù)接收的消息確定要加入的簇。每個(gè)子區(qū)域的傳感器節(jié)點(diǎn)構(gòu)建單鏈路，并根據(jù)成簇的可靠性進(jìn)行簇頭節(jié)點(diǎn)的選舉。

仿真的過程中，位于監(jiān)控區(qū)域左下角位置的匯聚節(jié)點(diǎn)，根據(jù)距離匯聚節(jié)點(diǎn)的距離將監(jiān)控區(qū)域劃分為不同的環(huán)形等級(jí)，然后將每一層的面積平均化，得到每個(gè)簇的大小區(qū)域。規(guī)定距離基站越近的環(huán)形等級(jí)越低，分別為0,1…,i，如圖2所示。環(huán)形等級(jí)level計(jì)算公式為：

level=i,i*d0≤r≤(i+1)*d0

(5)

其中：r表示的是環(huán)形的半徑大小，d0表示的是自由空間傳播模型和多徑衰減模型的臨界距離，i表示的是環(huán)形等級(jí)的數(shù)值大小。

圖2 環(huán)形等級(jí)示意圖

圖3 簇內(nèi)數(shù)據(jù)融合的示意圖

如圖3所示，在一個(gè)簇內(nèi)有N個(gè)傳感器節(jié)點(diǎn)，按照經(jīng)典的PEGASIS(Power-Efficient Gathering in Sensor Information System)算法形成單鏈路，如果簇頭節(jié)點(diǎn)C4左邊鏈路有m個(gè)傳感器節(jié)點(diǎn)，那么C4右邊鏈路就有N-1-m個(gè)傳感器節(jié)點(diǎn)。任何復(fù)雜的系統(tǒng)都可以通過并聯(lián)與串聯(lián)模塊的組合來描述[7]。如圖4可靠性模型(Reliability Block Diagram, RBD)所示，整個(gè)簇的數(shù)據(jù)傳輸可靠性Rcluster表示為：

(6)

其中：RCH表示的是簇頭節(jié)點(diǎn)的數(shù)據(jù)可靠性，RCMi表示的是普通傳感器節(jié)點(diǎn)的數(shù)據(jù)可靠性。

節(jié)點(diǎn)i的數(shù)據(jù)可靠性定義為：

RCMi=Ere(i)/Einit(i)

(7)

其中：Ere(i)表示的是節(jié)點(diǎn)i的剩余能量，Einit(i)表示的是節(jié)點(diǎn)i的初始能量。

圖4 RBD模型示意圖

3)確定簇頭節(jié)點(diǎn)i的自適應(yīng)搜索區(qū)域。

(8)

其中：dmax表示的是頭節(jié)點(diǎn)集合中距離基站的最遠(yuǎn)距離，dis表示的是當(dāng)前的簇頭節(jié)點(diǎn)距離基站的距離，dmin表示的是簇頭節(jié)點(diǎn)集合中距離基站的最近距離，θinit表示的是距離基站最遠(yuǎn)的簇頭的搜索角度。

圖5 節(jié)點(diǎn)i的自適應(yīng)搜索區(qū)域

本算法通過搜索角度控制簇頭的搜索區(qū)域。距離基站最遠(yuǎn)的簇頭節(jié)點(diǎn)的搜索區(qū)域?yàn)棣萯nit，其余簇頭節(jié)點(diǎn)的搜索角度隨著dis的變化而變化，距離基站越近，簇頭節(jié)點(diǎn)的搜索區(qū)域越大，則可以作為下一跳的節(jié)點(diǎn)的選擇性就越多，從而避免個(gè)別節(jié)點(diǎn)點(diǎn)介數(shù)過高的情況，一定程度上緩解了“熱點(diǎn)”問題的產(chǎn)生，延長了網(wǎng)絡(luò)壽命。

根據(jù)文獻(xiàn)[11]，無線傳感器網(wǎng)絡(luò)可以方便地表述為圖G=〈V,E〉，其中，V代表圖中頂點(diǎn)的集合，E代表圖中邊的集合，用Gd(a,b)表示節(jié)點(diǎn)a和節(jié)點(diǎn)b的最短距離，a∈V∧b∈V，σab代表節(jié)點(diǎn)a和節(jié)點(diǎn)b之間的最短路徑數(shù)目，a∈V∧b∈V，σab(z)代表節(jié)點(diǎn)a到節(jié)點(diǎn)b經(jīng)過節(jié)點(diǎn)z的路徑數(shù)目，z∈V。節(jié)點(diǎn)z的點(diǎn)介數(shù)BC(z)定義為：

(9)

4)候選捷徑端點(diǎn)的確定。

如果該簇頭在當(dāng)前θ的搜索區(qū)域范圍內(nèi)沒有發(fā)現(xiàn)候選捷徑端點(diǎn)的存在，那么該簇頭節(jié)點(diǎn)會(huì)繼續(xù)擴(kuò)大搜索范圍，直至找到候選捷徑端點(diǎn)。如果當(dāng)θ達(dá)到360°時(shí)，該簇頭仍然沒有找到候選捷徑端點(diǎn)，則選擇距離該節(jié)點(diǎn)最近的簇頭節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。如果該節(jié)點(diǎn)找不到離自己最近的簇頭節(jié)點(diǎn)，那么會(huì)選擇鄰近區(qū)域的普通節(jié)點(diǎn)作為中繼節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。

5)捷徑端點(diǎn)的確定。

捷徑端點(diǎn)的確定如圖6流程所示，由于在部署傳感器節(jié)點(diǎn)的時(shí)候采取的是隨機(jī)撒點(diǎn)的方式，所以會(huì)導(dǎo)致選擇出來的簇頭節(jié)點(diǎn)不一定是H-sensor節(jié)點(diǎn)。如果該簇頭節(jié)點(diǎn)i是L-sensor，則節(jié)點(diǎn)i選取離節(jié)點(diǎn)j距離最近的節(jié)點(diǎn)作為節(jié)點(diǎn)j的下一跳節(jié)點(diǎn)。如果是該簇頭節(jié)點(diǎn)i是H-sensor節(jié)點(diǎn)，比較該節(jié)點(diǎn)的本輪剩余能量Ei和網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的平均剩余能量Eave，Eave的表達(dá)式如式(10)所示:

(10)

其中：m簇頭節(jié)點(diǎn)的數(shù)目，Eres(i)表示的是節(jié)點(diǎn)i當(dāng)前的剩余能量。

如果節(jié)點(diǎn)Eres(i)>Eave，則節(jié)點(diǎn)i選擇距離基站最近的候選捷徑端點(diǎn)作為下一跳節(jié)點(diǎn)。如果Eres(i)

圖6 捷徑端點(diǎn)確定的流程

圖7是 HASWNM算法生成的拓?fù)浣Y(jié)構(gòu)圖。傳感器節(jié)點(diǎn)主要分為4類：當(dāng)選為簇頭的高性能節(jié)點(diǎn)；作為簇成員的高性能節(jié)點(diǎn)；當(dāng)選為簇頭的低性能節(jié)點(diǎn)；作為簇成員的低性能節(jié)點(diǎn)。簇間的通信采用了大量的捷徑鏈路。每個(gè)簇頭在中繼節(jié)點(diǎn)的選擇方法上呈現(xiàn)出差異性。

圖7 算法拓?fù)浣Y(jié)構(gòu)示意圖

6)數(shù)據(jù)傳輸階段。

當(dāng)基站接收到所有簇頭傳送過來的數(shù)據(jù)包時(shí)，即完成了一輪的通信。進(jìn)入下一輪的數(shù)據(jù)采集。

2.4 算法復(fù)雜度分析

假設(shè)監(jiān)控區(qū)域內(nèi)有N個(gè)傳感器節(jié)點(diǎn)，其中有m個(gè)簇頭，那么普通節(jié)點(diǎn)的個(gè)數(shù)為N-m，每個(gè)簇內(nèi)的節(jié)點(diǎn)個(gè)數(shù)平均為N/m。簇的建立階段分為鄰居發(fā)現(xiàn)階段、控制數(shù)據(jù)廣播以及網(wǎng)絡(luò)配置。在鄰居發(fā)現(xiàn)階段，所有的傳感器節(jié)點(diǎn)廣播一個(gè)帶有自己ID號(hào)的hello包，共有N個(gè)數(shù)據(jù)包。在控制數(shù)據(jù)廣播階段，每個(gè)傳感器節(jié)點(diǎn)的控制信息包括自身的ID號(hào)、剩余能量和它的鄰居表數(shù)據(jù)通過泛洪的方式傳送給基站，共有N個(gè)數(shù)據(jù)包?；臼盏剿械臄?shù)據(jù)包信息之后，在網(wǎng)絡(luò)配置階段，會(huì)以泛洪的方式發(fā)送一個(gè)數(shù)據(jù)包，使得網(wǎng)絡(luò)節(jié)點(diǎn)了解網(wǎng)絡(luò)整體的情況。

3 仿真結(jié)果與分析

3.1 實(shí)驗(yàn)場景設(shè)置

根據(jù)參考文獻(xiàn)[3]，在實(shí)驗(yàn)仿真時(shí)，簇?cái)?shù)K取值按照K=πR2/r2。其中，R表示的是高性能節(jié)點(diǎn)的通信半徑，r表示的是低性能節(jié)點(diǎn)的通信半徑。

實(shí)驗(yàn)驗(yàn)證借助Matlab平臺(tái)，仿真實(shí)驗(yàn)的具體參數(shù)設(shè)置如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

仿真的大致流程為：

1)隨機(jī)部署1 000個(gè)傳感器節(jié)點(diǎn)，初始化網(wǎng)絡(luò)，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)為(xi,yi)，ID號(hào)為idi，并進(jìn)行簇的劃分。每個(gè)簇內(nèi)按照數(shù)據(jù)傳輸?shù)目煽啃赃x取出簇頭節(jié)點(diǎn)，并對(duì)簇頭節(jié)點(diǎn)打上標(biāo)記flag。

3)當(dāng)基站收到了所有簇頭的數(shù)據(jù)包后，一輪傳輸結(jié)束，進(jìn)入到下一輪數(shù)據(jù)收集的準(zhǔn)備階段。

3.2 仿真結(jié)果分析

實(shí)驗(yàn)1 能量消耗和高性能節(jié)點(diǎn)數(shù)目關(guān)系實(shí)驗(yàn)。

從圖8中可以看出，HASWNM只是對(duì)簇頭節(jié)點(diǎn)尋找相應(yīng)的捷徑端點(diǎn)，當(dāng)網(wǎng)絡(luò)中的高性能節(jié)點(diǎn)的數(shù)目不是很多的時(shí)候，由于高性能節(jié)點(diǎn)分布不均勻，可能會(huì)導(dǎo)致能量消耗比較快一點(diǎn)。但是隨著高性能傳感器節(jié)點(diǎn)個(gè)數(shù)的增加，基本能夠保持每個(gè)簇內(nèi)都有高性能節(jié)點(diǎn)，這樣導(dǎo)致能量消耗比較低，所以能耗基本呈現(xiàn)出一個(gè)下降的趨勢(shì)。DASM(Directed Angulation towards the Sink node Model)中，高性能節(jié)點(diǎn)在固定的搜索區(qū)域內(nèi)搜索捷徑端點(diǎn)，TSWN(Tree-based Small World Network)將自適應(yīng)搜索區(qū)域內(nèi)的所有高性能節(jié)點(diǎn)加入到捷徑的創(chuàng)建中，當(dāng)有多個(gè)高性能節(jié)點(diǎn)時(shí)，隨機(jī)選擇加入捷徑，因此，故在初始時(shí)，兩種模型的高性能節(jié)點(diǎn)利用率相對(duì)CSWN(topology Control based on Small World Network)、HASWNM高，其能耗會(huì)更加均衡，網(wǎng)絡(luò)能量消耗相對(duì)較低。

圖8 能量消耗和高性能節(jié)點(diǎn)數(shù)目的關(guān)系

實(shí)驗(yàn)2 網(wǎng)絡(luò)生命周期和高性能節(jié)點(diǎn)數(shù)目關(guān)系實(shí)驗(yàn)。

從圖9可以看出，網(wǎng)絡(luò)生命周期與能量消耗呈現(xiàn)出一定的關(guān)系，在高性能節(jié)點(diǎn)個(gè)數(shù)不是很多的時(shí)候，相比別的算法，HASWNM算法能耗要更高一些，導(dǎo)致其網(wǎng)絡(luò)生命周期比較短，隨著高性能節(jié)點(diǎn)個(gè)數(shù)的增加，HASWNM在網(wǎng)絡(luò)生命周期方面表現(xiàn)出一定的優(yōu)越性。

實(shí)驗(yàn)3 小世界特性和高性能節(jié)點(diǎn)數(shù)目關(guān)系實(shí)驗(yàn)。

本文定義C(0)表示的是僅由普通節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)聚類系數(shù)大小，C(H)表示的是由H個(gè)高性能節(jié)點(diǎn)以及一些普通的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)聚類系數(shù)大小，L(0)表示的是僅由普通節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)平均路徑長度大小，L(H)表示的是由H個(gè)高性能節(jié)點(diǎn)以及一些普通的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)平均路徑長度大小。

從圖10中可以看出，隨著高性能節(jié)點(diǎn)個(gè)數(shù)的增加，L(H)/L(0)呈下降的趨勢(shì)，當(dāng)高性能的節(jié)點(diǎn)個(gè)數(shù)達(dá)到100時(shí)，平均路徑長度減少了72%左右。當(dāng)高性能節(jié)點(diǎn)個(gè)數(shù)達(dá)到100以后，L(H)/L(0)基本維持不變，C(H)/C(0)也基本處于不變的狀態(tài)。采用本實(shí)驗(yàn)的參數(shù)設(shè)置時(shí)，最佳的高性能節(jié)點(diǎn)個(gè)數(shù)為100個(gè)時(shí)，使得網(wǎng)絡(luò)的平均路徑長度最小。

圖9 網(wǎng)絡(luò)生命周期和高性能節(jié)點(diǎn)數(shù)目的關(guān)系

圖10 聚類系數(shù)、平均路徑長度與高性能節(jié)點(diǎn)數(shù)目的關(guān)系

實(shí)驗(yàn)4 網(wǎng)絡(luò)剩余能量和仿真輪數(shù)的關(guān)系。

當(dāng)實(shí)驗(yàn)仿真時(shí)，高性能的節(jié)點(diǎn)個(gè)數(shù)設(shè)置為100，那么低性能節(jié)點(diǎn)的個(gè)數(shù)就為900個(gè)。根據(jù)每輪能量消耗，可以估算出不同算法的最大工作輪數(shù)不超過700，因此，算法最大仿真周期設(shè)置為700輪。

圖11表示的節(jié)點(diǎn)總的剩余能量和仿真輪數(shù)的關(guān)系。通過前面圖8分析可知，高性能節(jié)點(diǎn)的個(gè)數(shù)為100時(shí)，HASWNM算法每輪的平均能耗是最低的。通過圖11可以直觀地看出，節(jié)點(diǎn)總的剩余能量是最多的，其次是CSWN、TSWN，最差的是DASM算法。實(shí)驗(yàn)8和實(shí)驗(yàn)11的結(jié)果具有很強(qiáng)的關(guān)聯(lián)性。

實(shí)驗(yàn)5 不同算法網(wǎng)絡(luò)平均周期比較實(shí)驗(yàn)。

圖12表示的是不同算法的網(wǎng)絡(luò)平均生命周期。從圖中可以看出，HASWNM算法在第一個(gè)節(jié)點(diǎn)死亡、10%節(jié)點(diǎn)死亡以及50%節(jié)點(diǎn)死亡時(shí)，都具有最大的仿真輪數(shù)。第一個(gè)節(jié)點(diǎn)死亡時(shí)，HASWNM算法相比較CSWN延遲了6%，相比較TSWN延遲了6%，相比較DASM延遲了29%。10%節(jié)點(diǎn)死亡時(shí)，HASWNM算法相比較CSWN延遲了18%，相比較TSWN延遲了30%，相比較DASM延遲了63%。50%節(jié)點(diǎn)死亡時(shí)，HASWNM算法相比較CSWN延遲了19%，相比較TSWN延遲了23%，相比較DASM延遲了32%。全部節(jié)點(diǎn)死亡時(shí)，HASWNM算法相比較CSWN延遲了4%，相比較TSWN延遲了10%，相比較DASM延遲了19%。WSN生命周期的長短主要取決于網(wǎng)絡(luò)的能耗情況，通過圖8知道，由于節(jié)點(diǎn)搜索區(qū)域以及捷徑端點(diǎn)的選擇規(guī)則的不同，導(dǎo)致當(dāng)高性能節(jié)點(diǎn)數(shù)為100的時(shí)候，每一輪的能量消耗從小到大依次為：HASWNM、CSWN、TSWN、DASM。

圖11 節(jié)點(diǎn)總的剩余能量和仿真輪數(shù)的關(guān)系

圖12 不同算法的網(wǎng)絡(luò)平均生命周期

4 結(jié)語

本文提出了一種基于小世界網(wǎng)絡(luò)模型的無線傳感器網(wǎng)絡(luò)層次型路由算法，小世界模型的構(gòu)造是通過添加高性能節(jié)點(diǎn)以及在選擇出來的簇頭節(jié)點(diǎn)間添加捷徑的方法實(shí)現(xiàn)的。由于無線傳感器的能耗主要集中在數(shù)據(jù)的發(fā)送階段，所以只有能量高于所有簇頭平均能量的簇頭節(jié)點(diǎn)，才會(huì)選擇候選捷徑端點(diǎn)中距離基站最近的簇頭作為下一跳節(jié)點(diǎn)，否則，會(huì)隨機(jī)選擇一個(gè)候選捷徑端點(diǎn)作為下一跳節(jié)點(diǎn)。這樣做的好處是節(jié)省了一定的能量，避免了個(gè)別節(jié)點(diǎn)能量消耗過快。簇頭根據(jù)距離基站的位置，控制搜索區(qū)域的角度，避免了基站周圍個(gè)別節(jié)點(diǎn)點(diǎn)介數(shù)過高的問題，有效地延長了網(wǎng)絡(luò)的生命周期。通過仿真驗(yàn)證，基于小世界網(wǎng)絡(luò)模型的無線傳感器網(wǎng)絡(luò)層次型算法使得網(wǎng)絡(luò)具有大的聚類系數(shù)和小的平均路徑長度，同時(shí)網(wǎng)絡(luò)能耗相比較也比較低。本文提出的算法主要考慮節(jié)點(diǎn)的能耗，后續(xù)可以考慮從覆蓋率、QoS以及有利于算法的擴(kuò)展性等因素入手，展開進(jìn)一步研究。

References)

[1] GITTERMAN M. Small-world phenomena in physics: the Ising model [J]. Journal of Physics A: Mathematical and General, 2000, 33(47): 8373-8381.

[2] HELMY A. Small worlds in wireless networks [J]. IEEE Communications Letters, 2003, 7(10): 490-492.

[3] 熊書明,胡永娣. 基于小世界概念的異構(gòu)傳感器網(wǎng)絡(luò)拓?fù)淇刂芠J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(11):2869-2875.(XIONG S M, HU Y D. Topology control method for heterogeneous wireless sensor network based on small world concepts [J]. Computer Engineering and Design, 2016, 37(11): 2869-2875.)

[4] 葉秀彩,許力,林力偉.基于小世界現(xiàn)象的無線傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化[J].福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,24(5):37-40.(YE X C, XU L, LIN L W. Topology optimization based on small-world phenomenon in wireless sensor networks [J]. Journal of Fujian Normal University (Natural Science Edition), 2008, 24(5): 37-40.)

[5] 馬晨明.面向節(jié)能和容錯(cuò)的異構(gòu)無線傳感器網(wǎng)絡(luò)分布式拓?fù)淇刂扑惴ㄑ芯縖D].杭州:浙江工業(yè)大學(xué),2015.(MA C M. Research on distribution topology control algorithm for energy saving and fault tolerant in heterogeneous wireless sensor networks [D]. Hangzhou: Zhejiang University of Technology, 2015.)

[6] 任秀麗,董姜穎,薜建生.基于小世界的無線傳感器網(wǎng)絡(luò)的路由算法[J].計(jì)算機(jī)應(yīng)用,2010,30(9):2497-2500.(REN X L, DONG J Y, XUE J S. Small world routing algorithm of wireless sensor network [J]. Journal of Computer Applications, 2010, 30(9): 2497-2500.)

[7] 周祖德,胡鵬,李方敏,等.無線傳感器網(wǎng)絡(luò)分簇通信協(xié)議的可靠性方案[J].通信學(xué)報(bào),2008,29(5):114-121.(ZHOU Z D, HU P, LI F M, et al. Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J]. Journal on Communication, 2008, 29(5): 114-121.)

[8] GUIDONI D L, MINI R A F, LOUREIRO A A F. On the design of resilient heterogeneous wireless sensor networks based on small world concepts [J]. Computer Networks, 2010, 54(8): 1266-1281.

[9] 張婧.無線傳感器網(wǎng)絡(luò)能耗平衡策略研究[D].長春:吉林大學(xué),2015.(ZHANG J. Research on energy-balanced strategy in wireless sensor networks [D]. Changchun: Jilin University, 2015.)

[10] 謝啟輝,黃杰.基于動(dòng)態(tài)搜索區(qū)域的無線傳感器網(wǎng)絡(luò)小世界特性構(gòu)建方案[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,42(4):593-598.(XIE Q H, HUANG J. A scheme of constructing small world network in WSNs based on dynamically searching zone [J]. Journal of Southeast University (Natural Science Edition), 2012, 42(4): 593-598.)

[11] ASIF W, QURESHI H K, RAJARAJAN M. Variable Rate Adaptive Modulation (VRAM) for introducing small-world model into WSNs [C]// Proceedings of the 2013 47th Annual Conference on Information Sciences and Systems. Piscataway, NJ: IEEE, 2013: 1-6.

Hierarchicalroutingalgorithmforwirelesssensornetworksbasedonsmallworldmodel

WEI Shihong, TANG Qichao*

(KeyLabofMobileCommunicationsTechnology,ChongqingUniversityofPostsandCommunications,Chongqing400065,China)

Hierarchical routing algorithm is now a hotspot in the field of wireless sensor network. Aiming at the problem that the energy of sensor nodes are limited, a hierarchical routing algorithm for wireless sensor networks based on small world model (HASWNM) was proposed. The Wireless Sensor Network (WSN) could reflect characteristics of the small world by adding nodes with high performance as well as shortcuts among cluster heads. As the energy consumption was mainly concentrated in the data transmission phase, the energy of the cluster head was taken into account while choosing the relay node between clusters. Besides, the different adaptive search area was determined according to the distance between the cluster head and the base station. The experimental results showed that the network can show the characteristics of small world when the number of high-performance nodes reached 100, and compared to the algorithms of CSWN (topology Control based on Small World Network), TSWN (Tree-based Small World Network), DASM (Directed Angulation towards the Sink node Model), the number of death rounds of the first node was delayed by 6%，6%，29% separately, and the average energy consumption of the network per round was reduced by 5%，12%，17% respectively. Thus the wireless sensor network constructed by the proposed algorithm has the characteristics of small world and low energy consumption.

Wireless Sensor Network (WSN); clustering coefficient; average path length; energy consumption

2017- 03- 20;

2017- 04- 11。

長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃項(xiàng)目(IRT1299)；重慶市科委項(xiàng)目(CSTC2012jjA40044, CSTC2013yykfA40010)。

韋世紅(1970—)，女，重慶人，副教授，博士，主要研究方向：無線傳感器網(wǎng)絡(luò)拓?fù)淇刂婆c路由算法、MIMO信道估計(jì)； 唐起超(1989—)，男，山東威海人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)路由算法、復(fù)雜網(wǎng)絡(luò)模型。

1001- 9081(2017)09- 2457- 06

10.11772/j.issn.1001- 9081.2017.09.2457

TN929.5

A

現(xiàn)實(shí)生活中許許多多的網(wǎng)絡(luò)都具有復(fù)雜網(wǎng)絡(luò)的性質(zhì)，如社會(huì)關(guān)系中的科學(xué)協(xié)作網(wǎng)、朋友關(guān)系網(wǎng)；生態(tài)系統(tǒng)中的蛋白質(zhì)網(wǎng)、神經(jīng)元網(wǎng)絡(luò)；技術(shù)網(wǎng)絡(luò)中的Internet以及信息網(wǎng)絡(luò)中的WWW等。作為復(fù)雜網(wǎng)絡(luò)重要特性之一的小世界特性，是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)浣Y(jié)構(gòu)屬性之一，小世界現(xiàn)象普遍存在于大量真實(shí)網(wǎng)絡(luò)中，如計(jì)算機(jī)互聯(lián)網(wǎng)、科學(xué)家合作網(wǎng)、產(chǎn)品生產(chǎn)關(guān)系網(wǎng)和電力網(wǎng)絡(luò)等。

This work is partially supported by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), the Project of Chongqing Science and Technology Commission (CSTC2012jjA40044, CSTC2013yykfA40010).

WEIShihong, born in 1970, Ph. D., associate professor. Her research interests include topology control and routing algorithm of wireless sensor networks, channel estimation of MIMO system.

TANGQichao, born in 1989, M. S. candidate. His research interests include routing algorithm of wireless sensor networks, complex network model.