基于小世界模型的無線傳感器網絡層次型路由算法

韋世紅，唐起超

(重慶郵電大學 移動通信技術重點實驗室，重慶 400065)(*通信作者電子郵箱2075721094@qq.com)

基于小世界模型的無線傳感器網絡層次型路由算法

韋世紅，唐起超*

(重慶郵電大學 移動通信技術重點實驗室，重慶 400065)(*通信作者電子郵箱2075721094@qq.com)

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

無線傳感器網絡；聚類系數；平均路徑長度；能量損耗

1 小世界網絡模型

小世界網絡的本質特征是具有小的平均路徑長度和大的聚類系數[1]，將復雜網絡的小世界現象引入無線傳感器網絡(Wireless Sensor Network, WSN)的研究，對分析WSN的拓撲結構、發現WSN中隱藏的規律以及預測WSN的行為具有十分重要的理論意義。

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

(1)

其中：N表示的是傳感器節點的數量，dij表示的是節點i和節點j之間的通信距離實際存在的邊條數。

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

(2)

其中：N表示的是傳感器節點個數，K表示的是節點度數，p為重連概率，f(x)表示的是普適標度函數。

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

(3)

當節點的平均度固定時，平均路徑長度的增加速度與N的對數成正比。表明基于小世界的無線傳感器網絡其平均路徑長度較小，且對于隨機故障具有較強的魯棒性。

2).聚類系數C：聚類系數描述了節點i與其直接相連的鄰居節點的連接關系，如式(4)所示：

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

(4)

其中：NΔ(i)表示的是該網絡中包含節點i的三角形總數，N3(i)表示包含節點i的三元組總數。

對部分聚類系數較小的邊進行一些必要的選擇性刪改，可提高網絡整體的平均聚類系數，從而達到簡化拓撲結構、優化路徑選擇的效果。

廣大學者提出了很多無線傳感器網絡小世界特性的構造方法。文獻[2]提出了基于NW(Newman-Watts)小世界WSN的構造方法，但是網絡的抗毀性較差，性能低，造價昂貴。文獻[3]提出了基于匯聚節點(sink node)構造小世界WSN，抗毀性較差，適用于小規模的網絡。文獻[4]提出了基于拓撲優化的小世界WSN構造，該算法形成了一種靜態拓撲，抗毀性適中，網絡規模適中。

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

2 本文算法

2.1 系統模型

1)N個傳感器節點隨機部署在M×M的正方形監控區域內，傳感器節點分為普通節點和高性能節點。節點通過ID(Identification)進行標識，并且存儲、計算能量受限。

2)傳感器節點一旦被部署，則一直處于靜止狀態。

3)sink節點存儲、計算能量不受限，并且sink節點是固定的。

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

2.2 基本概念

定義1 兩個高性能節點之間的鏈接成為捷徑[6]。

定義2 高性能節點間的鏈接概率用p表示。

定義3 假設普通節點的通信半徑為RL，高性能節點的通信半徑為RH，在實驗的過程中保證RH?RL。

2.3 算法描述

算法是以輪數為單位，每一輪主要分為簇的劃分以及簇頭的選擇，簇頭的選擇根據數據傳輸的可靠性；選擇出來的簇頭節點同時進行鏈路構建，包括候選捷徑端點的確定以及捷徑端點的確定；最后完成數據的通信過程。具體的流程如圖1所示。

圖1 算法流程

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

2)簇的建立階段分為鄰居發現階段、控制數據廣播以及網絡配置。在鄰居發現階段，所有的傳感器節點廣播一個帶有自己ID號的hello包，收到hello包的傳感器節點會更新自己的鄰居表和接收信號強度(Receive Signal Strength Indicator, RSSI)。控制數據廣播，該算法使用泛洪的方法傳輸控制數據到基站，每個傳感器節點的控制信息包括自身的ID號、剩余能量和它的鄰居表數據。中繼節點接收到數據包會繼續廣播直到數據包傳輸到基站為止。網絡配置階段，當基站收到網絡中所有的傳感器節點的控制包時，基站開始配置網絡。配置廣播，當基站完成網絡配置，以泛洪的方式向所有的傳感器節點廣播網絡配置，對子區域進行劃分。每個傳感器節點根據接收的消息確定要加入的簇。每個子區域的傳感器節點構建單鏈路，并根據成簇的可靠性進行簇頭節點的選舉。

仿真的過程中，位于監控區域左下角位置的匯聚節點，根據距離匯聚節點的距離將監控區域劃分為不同的環形等級，然后將每一層的面積平均化，得到每個簇的大小區域。規定距離基站越近的環形等級越低，分別為0,1…,i，如圖2所示。環形等級level計算公式為：

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

(5)

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

圖2 環形等級示意圖

圖3 簇內數據融合的示意圖

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

(6)

其中：RCH表示的是簇頭節點的數據可靠性，RCMi表示的是普通傳感器節點的數據可靠性。

節點i的數據可靠性定義為：

RCMi=Ere(i)/Einit(i)

(7)

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

圖4 RBD模型示意圖

3)確定簇頭節點i的自適應搜索區域。

(8)

其中：dmax表示的是頭節點集合中距離基站的最遠距離，dis表示的是當前的簇頭節點距離基站的距離，dmin表示的是簇頭節點集合中距離基站的最近距離，θinit表示的是距離基站最遠的簇頭的搜索角度。

圖5 節點i的自適應搜索區域

本算法通過搜索角度控制簇頭的搜索區域。距離基站最遠的簇頭節點的搜索區域為θinit，其余簇頭節點的搜索角度隨著dis的變化而變化，距離基站越近，簇頭節點的搜索區域越大，則可以作為下一跳的節點的選擇性就越多，從而避免個別節點點介數過高的情況，一定程度上緩解了“熱點”問題的產生，延長了網絡壽命。

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

(9)

4)候選捷徑端點的確定。

如果該簇頭在當前θ的搜索區域范圍內沒有發現候選捷徑端點的存在，那么該簇頭節點會繼續擴大搜索范圍，直至找到候選捷徑端點。如果當θ達到360°時，該簇頭仍然沒有找到候選捷徑端點，則選擇距離該節點最近的簇頭節點作為下一跳節點。如果該節點找不到離自己最近的簇頭節點，那么會選擇鄰近區域的普通節點作為中繼節點進行數據傳輸。

5)捷徑端點的確定。

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

(10)

其中：m簇頭節點的數目，Eres(i)表示的是節點i當前的剩余能量。

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

圖6 捷徑端點確定的流程

圖7是 HASWNM算法生成的拓撲結構圖。傳感器節點主要分為4類：當選為簇頭的高性能節點；作為簇成員的高性能節點；當選為簇頭的低性能節點；作為簇成員的低性能節點。簇間的通信采用了大量的捷徑鏈路。每個簇頭在中繼節點的選擇方法上呈現出差異性。

圖7 算法拓撲結構示意圖

6)數據傳輸階段。

當基站接收到所有簇頭傳送過來的數據包時，即完成了一輪的通信。進入下一輪的數據采集。

2.4 算法復雜度分析

假設監控區域內有N個傳感器節點，其中有m個簇頭，那么普通節點的個數為N-m，每個簇內的節點個數平均為N/m。簇的建立階段分為鄰居發現階段、控制數據廣播以及網絡配置。在鄰居發現階段，所有的傳感器節點廣播一個帶有自己ID號的hello包，共有N個數據包。在控制數據廣播階段，每個傳感器節點的控制信息包括自身的ID號、剩余能量和它的鄰居表數據通過泛洪的方式傳送給基站，共有N個數據包。基站收到所有的數據包信息之后，在網絡配置階段，會以泛洪的方式發送一個數據包，使得網絡節點了解網絡整體的情況。

3 仿真結果與分析

3.1 實驗場景設置

根據參考文獻[3]，在實驗仿真時，簇數K取值按照K=πR2/r2。其中，R表示的是高性能節點的通信半徑，r表示的是低性能節點的通信半徑。

實驗驗證借助Matlab平臺，仿真實驗的具體參數設置如表1所示。

表1 實驗參數設置

仿真的大致流程為：

1)隨機部署1 000個傳感器節點，初始化網絡，每個網絡節點坐標為(xi,yi)，ID號為idi，并進行簇的劃分。每個簇內按照數據傳輸的可靠性選取出簇頭節點，并對簇頭節點打上標記flag。

3)當基站收到了所有簇頭的數據包后，一輪傳輸結束，進入到下一輪數據收集的準備階段。

3.2 仿真結果分析

實驗1 能量消耗和高性能節點數目關系實驗。

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

圖8 能量消耗和高性能節點數目的關系

實驗2 網絡生命周期和高性能節點數目關系實驗。

從圖9可以看出，網絡生命周期與能量消耗呈現出一定的關系，在高性能節點個數不是很多的時候，相比別的算法，HASWNM算法能耗要更高一些，導致其網絡生命周期比較短，隨著高性能節點個數的增加，HASWNM在網絡生命周期方面表現出一定的優越性。

實驗3 小世界特性和高性能節點數目關系實驗。

本文定義C(0)表示的是僅由普通節點構成的網絡聚類系數大小，C(H)表示的是由H個高性能節點以及一些普通的傳感器節點構成的網絡聚類系數大小，L(0)表示的是僅由普通節點構成的網絡平均路徑長度大小，L(H)表示的是由H個高性能節點以及一些普通的傳感器節點構成的網絡平均路徑長度大小。

從圖10中可以看出，隨著高性能節點個數的增加，L(H)/L(0)呈下降的趨勢，當高性能的節點個數達到100時，平均路徑長度減少了72%左右。當高性能節點個數達到100以后，L(H)/L(0)基本維持不變，C(H)/C(0)也基本處于不變的狀態。采用本實驗的參數設置時，最佳的高性能節點個數為100個時，使得網絡的平均路徑長度最小。

圖9 網絡生命周期和高性能節點數目的關系

圖10 聚類系數、平均路徑長度與高性能節點數目的關系

實驗4 網絡剩余能量和仿真輪數的關系。

當實驗仿真時，高性能的節點個數設置為100，那么低性能節點的個數就為900個。根據每輪能量消耗，可以估算出不同算法的最大工作輪數不超過700，因此，算法最大仿真周期設置為700輪。

圖11表示的節點總的剩余能量和仿真輪數的關系。通過前面圖8分析可知，高性能節點的個數為100時，HASWNM算法每輪的平均能耗是最低的。通過圖11可以直觀地看出，節點總的剩余能量是最多的，其次是CSWN、TSWN，最差的是DASM算法。實驗8和實驗11的結果具有很強的關聯性。

實驗5 不同算法網絡平均周期比較實驗。

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

圖11 節點總的剩余能量和仿真輪數的關系

圖12 不同算法的網絡平均生命周期

4 結語

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

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] 熊書明,胡永娣. 基于小世界概念的異構傳感器網絡拓撲控制[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] 葉秀彩,許力,林力偉.基于小世界現象的無線傳感器網絡拓撲優化[J].福建師范大學學報(自然科學版),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] 馬晨明.面向節能和容錯的異構無線傳感器網絡分布式拓撲控制算法研究[D].杭州:浙江工業大學,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] 任秀麗,董姜穎,薜建生.基于小世界的無線傳感器網絡的路由算法[J].計算機應用,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] 周祖德,胡鵬,李方敏,等.無線傳感器網絡分簇通信協議的可靠性方案[J].通信學報,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] 張婧.無線傳感器網絡能耗平衡策略研究[D].長春:吉林大學,2015.(ZHANG J. Research on energy-balanced strategy in wireless sensor networks [D]. Changchun: Jilin University, 2015.)

[10] 謝啟輝,黃杰.基于動態搜索區域的無線傳感器網絡小世界特性構建方案[J].東南大學學報(自然科學版),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。

長江學者和創新團隊發展計劃項目(IRT1299)；重慶市科委項目(CSTC2012jjA40044, CSTC2013yykfA40010)。

韋世紅(1970—)，女，重慶人，副教授，博士，主要研究方向：無線傳感器網絡拓撲控制與路由算法、MIMO信道估計； 唐起超(1989—)，男，山東威海人，碩士研究生，主要研究方向：無線傳感器網絡路由算法、復雜網絡模型。

1001- 9081(2017)09- 2457- 06

10.11772/j.issn.1001- 9081.2017.09.2457

TN929.5

A

現實生活中許許多多的網絡都具有復雜網絡的性質，如社會關系中的科學協作網、朋友關系網；生態系統中的蛋白質網、神經元網絡；技術網絡中的Internet以及信息網絡中的WWW等。作為復雜網絡重要特性之一的小世界特性，是復雜網絡最普遍和最重要的拓撲結構屬性之一，小世界現象普遍存在于大量真實網絡中，如計算機互聯網、科學家合作網、產品生產關系網和電力網絡等。

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.