一種高效節(jié)能的小世界無線傳感器網(wǎng)絡*

柳 艷，肖 旻，王紀軍，陳詠秋，徐明生

（1.江蘇電力信息技術有限公司，南京 210000；2.南京工程學院數(shù)理部，南京 211167；3.南京工程學院計算機工程學院，南京 211167）

0 引言

復雜網(wǎng)絡（CN，Complex Networks）是對復雜系統(tǒng)（CS，Complex System）的一種抽象描述。當前，復雜網(wǎng)絡的研究已經被逐步應用到自然科學、社會科學和工程科學等不同領域［1］。大規(guī)模無線傳感器網(wǎng)絡（Large-Scale Wireless Sensor Networks）正是復雜網(wǎng)絡研究的應用之一。隨著物聯(lián)網(wǎng)（IoT，Internet of Things）的廣泛應用，作為其終端支撐技術的無線傳感器網(wǎng)絡的規(guī)模也越來越大，這種大規(guī)模網(wǎng)絡表現(xiàn)出了簡單網(wǎng)絡所不具備的統(tǒng)計特性［2］。因此，利用復雜網(wǎng)絡理論來研究大規(guī)模無線傳感器網(wǎng)絡有著其充分的合理性。復雜網(wǎng)絡的基本網(wǎng)絡模型包括：規(guī)則網(wǎng)絡（Regular Network）、隨機網(wǎng)絡（Random Network）、小世界網(wǎng)絡（Small World Network）、無標度網(wǎng)絡（Scale-free Network）和局域世界演化網(wǎng)絡（Local-world Evolving Network）等［3］。其中，小世界網(wǎng)絡是介于規(guī)則網(wǎng)絡和隨機網(wǎng)絡之間的一種網(wǎng)絡模型。鑒于大部分現(xiàn)實網(wǎng)絡既不是規(guī)則的，也不是完全隨機的，研究基于小世界網(wǎng)絡模型的無線傳感器網(wǎng)絡更有現(xiàn)實意義。

無線傳感器網(wǎng)絡是指在感興趣的區(qū)域內布置一定數(shù)量的通信節(jié)點，這些節(jié)點依靠相應的算法自組織網(wǎng)絡結構，并通過無線信道和鄰居節(jié)點進行通信，以多跳方式將感應數(shù)據(jù)傳遞到指定的Sink 節(jié)點位置。由于無線傳感器網(wǎng)絡通常被布置在環(huán)境惡劣的區(qū)域，進行人工補充節(jié)點能量將會付出相當大的代價，所以，采取相應的措施減少網(wǎng)絡能量消耗是無線傳感器網(wǎng)絡的重要研究課題［4］。小世界網(wǎng)絡具有較小的平均路徑長度和較大的聚類系數(shù)，此特性為減少網(wǎng)絡能耗提供了理論保證［5］。基于小世界模型來構造無線傳感器網(wǎng)絡拓撲的方法有靜態(tài)模式和動態(tài)模式兩類［6］。本文將靜態(tài)和動態(tài)模式相結合，提出一種構造小世界無線傳感器網(wǎng)絡的混合模式，即在拓撲優(yōu)化后的網(wǎng)絡中選擇特定節(jié)點，使之在網(wǎng)絡中隨機移動，從而構造出具有小世界特性的無線傳感器網(wǎng)絡。此方法從拓撲層面上對網(wǎng)絡結構進行優(yōu)化控制，以達到節(jié)約能量的目的。最后將上述小世界網(wǎng)絡拓撲構造方法與經典的基于連通支配集的拓撲構造方法A3［7］和A3 Cov［8］進行了仿真比較，結果表明，本方案增加了網(wǎng)絡能效性，延長了網(wǎng)絡的生命周期，提高了網(wǎng)絡運行的有效性。

1 無線傳感器網(wǎng)絡的小世界構造方法

小世界網(wǎng)絡的核心思想是：盡管有些網(wǎng)絡規(guī)模大、結構復雜，但其中任意兩個節(jié)點之間卻存在一個相對較小的路徑長度。兩種典型的小世界網(wǎng)絡模型分別為WS 小世界模型［9］和NW 小世界模型［10］。利用小世界模型來構造無線傳感器網(wǎng)絡的方法有靜態(tài)模式和動態(tài)模式兩類。其中，靜態(tài)的構造方法有基于加邊的靜態(tài)構造、基于超級節(jié)點的靜態(tài)構造和基于拓撲優(yōu)化的靜態(tài)構造；動態(tài)的構造方法目前主要是研究基于數(shù)據(jù)騾子的動態(tài)構造。

1.1 基于加邊的靜態(tài)構造

此構造方法基于NW 小世界模型的思想，即在無線傳感器網(wǎng)絡中在節(jié)點之間增加連接邊。文獻［11］根據(jù)節(jié)點度進行排序，在考慮網(wǎng)絡均勻覆蓋的前提下，將在一定距離范圍內的具有較高度的節(jié)點進行有線連接并形成鏈。文獻［12］討論了在瑞利衰落環(huán)境下的小世界無線自組織網(wǎng)絡構建方法，使用增加無線連接邊方式，讓距離Sink 節(jié)點較遠的普通節(jié)點與之直接相連，可顯著降低平均最短路徑。文獻［13］針對無線自組織網(wǎng)絡的特殊性，引入空間圖的概念進行網(wǎng)絡初始化，然后進行加邊形成小世界網(wǎng)絡。

1.2 基于超級節(jié)點的靜態(tài)構造

此構造方法在網(wǎng)絡中添加一類能量更充足、通信半徑更長、數(shù)據(jù)處理能力更強的超級節(jié)點，普通節(jié)點優(yōu)先選擇超級節(jié)點作為數(shù)據(jù)轉發(fā)的中繼，使得數(shù)據(jù)傳輸?shù)絊ink 節(jié)點的跳數(shù)大大減少。文獻［14］通過升級一部分節(jié)點使之成為超級節(jié)點，隨著能量的消耗，再將之降為普通節(jié)點。此機制可以比小世界網(wǎng)絡減少40%的端到端延時和減少25%的能耗。文獻［15］利用局部重要性節(jié)點設計了傳輸捷徑，將處于捷徑兩端的節(jié)點設置為超級節(jié)點。此機制下的網(wǎng)絡呈現(xiàn)出明顯的小世界特征，并具有較好的魯棒性。

1.3 基于拓撲優(yōu)化的靜態(tài)構造

此構造方法是以一定規(guī)則去簡化網(wǎng)絡結構，以滿足小世界模型的某些特征量的要求。文獻［16］通過刪除網(wǎng)絡中多余的連接，以增加平均聚類系數(shù)，使得網(wǎng)絡簇結構更加顯著、拓撲結構更加簡單，提高了數(shù)據(jù)傳輸效率。文獻［17］證明了當網(wǎng)絡具有小世界特性，且確定網(wǎng)絡直徑所需要的算法循環(huán)次數(shù)遠小于網(wǎng)絡節(jié)點數(shù)n 時，算法的時間復雜度為O（n2）。實驗表明，當對連接度和連接方式進行適當控制時，可形成小世界網(wǎng)絡特征，即可使網(wǎng)絡取得最優(yōu)的連接增益。

1.4 基于數(shù)據(jù)騾子的動態(tài)構造

在一些特殊場合，如戰(zhàn)場應用中，無線傳感器網(wǎng)絡呈現(xiàn)出稀疏性，甚至會出現(xiàn)多個網(wǎng)絡片互不連通的情況，此時利用上述靜態(tài)方法構造小世界網(wǎng)絡無法實現(xiàn)。文獻［18］提出了基于數(shù)據(jù)騾子（Data Mules）來構造小世界無線傳感器網(wǎng)絡的方法。此方法在靜態(tài)網(wǎng)絡中添加一些移動節(jié)點，當移動節(jié)點在網(wǎng)絡中游走時，收集相應普通節(jié)點轉發(fā)的數(shù)據(jù)，當其與Sink 節(jié)點建立連接時，即可將數(shù)據(jù)卸載至Sink 節(jié)點。由數(shù)據(jù)騾子所建立起來的傳輸路徑是一種動態(tài)路徑，并無固定結構，但從數(shù)據(jù)傳輸跳數(shù)而言，仍然減少了網(wǎng)絡平均路徑。文獻［19］分析了數(shù)據(jù)騾子在無線傳感器網(wǎng)絡中的應用，在不同的場景中仿真分析了加入數(shù)據(jù)騾子后網(wǎng)絡最短路徑、最長路徑和聚類系數(shù)的變化情況。

2 基于混合模式的小世界無線傳感器網(wǎng)絡

目前在構造具有小世界特性的無線傳感器網(wǎng)絡時，通常從規(guī)則網(wǎng)絡開始著手。但無線傳感器網(wǎng)絡一般被應用在人力物力難以到達的特殊場合，采用的部署方式是在目標區(qū)域隨機撒下若干個節(jié)點，形成的初始網(wǎng)絡是隨機網(wǎng)絡。基于此種特點，本文首先對隨機網(wǎng)絡進行拓撲優(yōu)化改造，然后在拓撲優(yōu)化后的網(wǎng)絡中選擇特定節(jié)點，使之在網(wǎng)絡中隨機移動，從而構造出具有小世界特性的無線傳感器網(wǎng)絡。這種把靜態(tài)和動態(tài)相結合的小世界構造方法，稱為混合模式?；诨旌夏Ｊ綐嬙斓男∈澜鐭o線傳感器網(wǎng)絡可分為拓撲優(yōu)化階段、小世界模型構造階段和能量動態(tài)均衡階段。

2.1 拓撲優(yōu)化階段

在拓撲優(yōu)化方面，本文將利用基于連通支配集（CDS，Connected Dominating Set） 的拓撲構造方法A3［7］和A3 Cov［8］。A3 算法的目標是在網(wǎng)絡中找到一個次優(yōu)的連通支配集，其算法執(zhí)行分為3 個階段：鄰居發(fā)現(xiàn)階段、子節(jié)點選擇階段和二次機會階段。涉及到的消息收發(fā)有：Hello 消息、Parent Recognition 消息、Children Recognition 消息和Sleeping 消息。

鄰居發(fā)現(xiàn)階段：節(jié)點在目標區(qū)域布置完畢后，從Sink 節(jié)點開始啟動樹的構建過程。網(wǎng)絡中A 節(jié)點通過發(fā)送Hello 消息發(fā)現(xiàn)鄰居節(jié)點，收到此消息的B 節(jié)點如果沒有被其他節(jié)點覆蓋，則B 的屬性將被設置為覆蓋子節(jié)點，A 為父節(jié)點，B 回復Parent Recognition 消息給A，否則B 將忽略Hello 消息。另外，可利用式（1）來計算收到Hello 消息的信號強度和節(jié)點的能量強度，此公式可用于候選父節(jié)點的確定。

其中，x（子節(jié)點）是y（父節(jié)點）的候選節(jié)點，WE是節(jié)點的剩余能量權值，Ex是節(jié)點x 的剩余能量，Emax是最大的初始能量，WD是與父節(jié)點距離的權值，RSSIy是接收父節(jié)點信號的強度，RSSI*是保證連接的最小RSSI，由接收機的靈敏度確定。

子節(jié)點選擇階段：父節(jié)點設置了一個超時時限來接收其鄰居子節(jié)點的應答。一旦時限到，父節(jié)點根據(jù)式（1）按降序排列每個子節(jié)點從而形成列表，并將此列表信息包含在Children Recognition 消息中發(fā)送給子節(jié)點。子節(jié)點接收到此消息后，會設置一個與其在列表中位置成正比的時限。在此時限中，子節(jié)點等待來自兄弟節(jié)點發(fā)送的Sleeping 消息，若收到，則自動進入睡眠狀態(tài)?？梢钥闯觯切┠芰扛?、距離父節(jié)點較遠的節(jié)點更容易成為候選父節(jié)點（樹的一部分）。

二次機會階段：特殊情況下，節(jié)點發(fā)送Sleeping消息會使網(wǎng)絡進入死等狀態(tài)。為了防止此現(xiàn)象，節(jié)點在接收到Sleeping 消息后會設置一個定時器，在此時間段內進行操作。

A3 算法根據(jù)節(jié)點傳輸半徑進行消息傳遞，進而生成連通樹，沒有考慮節(jié)點感知半徑。A3 Cov 算法在A3 算法的基礎上增加了感知選擇階段，是一個既考慮連通又考慮覆蓋的生成樹算法。在感知選擇階段，若被選擇的子節(jié)點不在感知半徑以內，仍然不能處于活躍狀態(tài)。

在如圖1 所示的隨機網(wǎng)絡布局下，采用A3 和A3 Cov 算法進行生成樹構建的虛擬骨干網(wǎng)（VBN，Virtual Backbone Network）如圖2 和圖3 所示。

圖1 隨機網(wǎng)絡布局

圖2 基于A3 算法的虛擬骨干網(wǎng)

圖3 基于A3 Cov 算法的虛擬骨干網(wǎng)

2.2 小世界模型構造階段

本文基于惡劣環(huán)境（如軍事應用場所、災難應用場所等）下的無線傳感器網(wǎng)絡部署，無法向網(wǎng)絡中添加基礎設施以實現(xiàn)添加有線邊。另外，除Sink節(jié)點外，假設網(wǎng)絡中的普通節(jié)點是同質的、能量有限的和可移動的。Sink 節(jié)點是靜止的、能量無限的和處于部署區(qū)域中心。為了避免增加無線邊使得網(wǎng)絡拓撲重新復雜化，且節(jié)點通信負載更大的情況，本文將基于數(shù)據(jù)騾子來動態(tài)構造具有小世界特征的無線傳感器網(wǎng)絡。具體可分為參數(shù)計算、數(shù)據(jù)騾子選擇、移動策略和數(shù)據(jù)轉發(fā)等4 個方面。

由于拓撲優(yōu)化后形成虛擬骨干網(wǎng)，每個普通節(jié)點到Sink 節(jié)點的路徑長度一定，即可計算任意節(jié)點到Sink 節(jié)點的路徑長度dis及網(wǎng)絡平均路徑長度L，如式（4）所示。

其中，dij表示網(wǎng)絡中兩個節(jié)點之間連接的最短路徑邊數(shù)，對網(wǎng)絡中任意兩個節(jié)點之間的最短路徑取平均值便可得到平均路徑長度，本文考慮全連通網(wǎng)絡情況。

數(shù)據(jù)騾子選擇：本文基于以下兩點進行數(shù)據(jù)騾子的選擇。

2）若節(jié)點i 到Sink 節(jié)點的路徑長度dis大于網(wǎng)絡平均路徑長度L，則證明i 距離Sink 節(jié)點較遠。為了構造小世界網(wǎng)絡平均路徑長度較短的特性，使節(jié)點i 成為數(shù)據(jù)騾子。第1）點與第2）點不重復使用。

移動策略：由于被選定的數(shù)據(jù)騾子并不存儲整個網(wǎng)絡的拓撲結構圖，為了節(jié)省傳感器存儲容量和減少計算復雜度，本文采取數(shù)據(jù)騾子在網(wǎng)絡規(guī)劃范圍內隨機選擇方向進行移動的方式。初始階段，數(shù)據(jù)騾子隨機選擇方向并勻速移動，當?shù)竭_網(wǎng)絡邊界時，以對稱角度向反方向移動，當網(wǎng)絡重新進行拓撲優(yōu)化時，停止移動。

數(shù)據(jù)轉發(fā)：數(shù)據(jù)騾子在隨機移動的過程中正常進行數(shù)據(jù)收發(fā)。在全連通情況下進行數(shù)據(jù)傳輸時，如果源節(jié)點找不到數(shù)據(jù)騾子進行轉發(fā)，則依據(jù)圖2和圖3 所示的虛擬骨干網(wǎng)進行傳輸。否則，源節(jié)點將數(shù)據(jù)加載到與目的節(jié)點方向一致的數(shù)據(jù)騾子上，稱為“上騾”。當數(shù)據(jù)騾子到達目的節(jié)點或改變方向時，從其存儲器提取信息發(fā)送到其他節(jié)點，稱為“卸騾”。

2.3 能量動態(tài)均衡階段

利用混合模式構造形成小世界網(wǎng)絡之后，即可進入網(wǎng)絡運行狀態(tài)。在網(wǎng)絡運行中，各個節(jié)點的能量均衡利用是無線傳感器網(wǎng)絡需要實現(xiàn)的重要目標。盡管小世界模型本身有利于節(jié)點的能量均衡，但靜態(tài)的拓撲結構仍然使得一部分承擔較重流量的節(jié)點提早耗盡能量。本文采用拓撲結構動態(tài)重構的方法來進一步實現(xiàn)節(jié)點能量的均衡使用，即當某條件成立時，立即重新調用拓撲構造算法進行拓撲優(yōu)化。將能量閾值和時間閾值作為拓撲重構的觸發(fā)條件。當某個活動節(jié)點的剩余能量低于其初始能量的20%或網(wǎng)絡運行時間超過1 000 s 時，重新調用拓撲構造算法。最終形成了應用A3 算法的基于混合模式的小世界無線傳感器網(wǎng)絡（MSW-WSNs-A3，Mixed-mode Small World Wireless Sensor Networks Using A3）和應用A3 Cov 算法的基于混合模式的小世界無線傳感器網(wǎng)絡（MSW-WSNs-A3 Cov，Mixed-mode Small World Wireless Sensor Networks Using A3 Cov）。

綜上所述，MSW-WSNs-A3 和MSW-WSNs-A3 Cov 的構造步驟如下：

1）在目標區(qū)域隨機部署可移動同質無線傳感器作為普通節(jié)點，在區(qū)域中心位置部署能量無限的靜止Sink 節(jié)點，普通節(jié)點與Sink 節(jié)點的傳輸半徑相同。轉向步驟2）；

2）調用A3 或A3 Cov 算法進行拓撲優(yōu)化。轉向步驟3）；

5）網(wǎng)絡運行，在生命周期內，當任意節(jié)點的剩余能量低于其初始能量的20%或網(wǎng)絡運行時間超過1 000 s 時，轉向步驟2）；若Sink 節(jié)點成為孤立節(jié)點，網(wǎng)絡運行完畢，生命周期結束。

3 仿真分析

本文把生命周期定義為從網(wǎng)絡運行開始至Sink 節(jié)點成為孤立節(jié)點為止。將基于A3 和A3 Cov的無線傳感器網(wǎng)絡分別記作WSNs-A3 和WSNs-A3 Cov，在一定網(wǎng)絡環(huán)境下對WSNs-A3、WSNs-A3 Cov、MSW-WSNs-A3 和MSW-WSNs-A3 Cov 進行仿真分析，比較各自的生命周期情況。

圖4 和圖5 以時間為橫坐標，以與Sink 節(jié)點存在路徑的活動節(jié)點數(shù)目為縱坐標，描述的是WSNs-A3 同MSW-WSNs-A3 以 及WSNs-A3 Cov同MSW-WSNs-A3 Cov 對比的生命周期情況。可以看出，為了保證覆蓋率，WSNs-A3 Cov 一開始便激活了約4 倍于WSNs-A3 的節(jié)點數(shù)。隨著時間的推移，WSNs-A3 和WSNs-A3 Cov 都存在活動節(jié)點數(shù)量階躍式下降的情況，MSW-WSNs-A3 和MSW-WSNs-A3 Cov 大大緩和了這種躍式下降的程度，證明本文設計的高效節(jié)能的小世界無線傳感器網(wǎng)絡具有很好的能量均衡效果，生命周期得到了明顯的改善。

表1 仿真參數(shù)設置

圖4 WSNs-A3 與MSW-WSNs-A3 生命周期比較

圖5 WSNs-A3 Cov 與MSW-WSNs-A3 Cov 生命周期比較

下頁圖6 和圖7 以時間為橫坐標，以節(jié)點通信覆蓋為縱坐標，描述的是WSNs-A3 同MSW-WSNs-A3以及WSNs-A3 Cov 同MSW-WSNs-A3 Cov 對比的通信覆蓋率情況。通過生命周期可以看出網(wǎng)絡的能量使用情況，而通過觀察通信覆蓋隨時間的變化情況，可以看出網(wǎng)絡運行的有效性，因為當通信覆蓋率降低到一定程度后，盡管生命周期還沒有完成，節(jié)點采集的數(shù)據(jù)已不能反映部署區(qū)域的整體情況。通過仿真可以看出，WSNs-A3 Cov 的通信覆蓋降到50%所花費的時間比WSNs-A3 要快約3 000 s，這是由于WSNs-A3 Cov 在網(wǎng)絡運行之初激活的節(jié)點數(shù)較多造成的。MSW-WSNs-A3 的通信覆蓋降到50 %所花費的時間比WSNs-A3 慢約2 倍，MSW-WSNs-A3 Cov 的通信覆蓋降到50 %所花費的時間比WSNs-A3 Cov 慢約4 倍，證明本文設計的高效節(jié)能的小世界無線傳感器網(wǎng)絡具有很好的運行有效性。

圖6 WSNs-A3 與MSW-WSNs-A3 通信覆蓋比較

圖7 WSNs-A3 Cov 與MSW-WSNs-A3 Cov 通信覆蓋比較

4 結論

本文提出了一種利用靜態(tài)和動態(tài)相結合的混合模式來構造小世界無線傳感器網(wǎng)絡的方法，該方法可分為拓撲優(yōu)化、小世界模型構造和能量動態(tài)均衡3 個階段，最終形成了應用A3 和A3 Cov 算法的基于混合模式的小世界無線傳感器網(wǎng)絡MSW-WSNs-A3 和MSW-WSNs-A3 Cov。經過仿真分析，表明MSW-WSNs-A3 和MSW-WSNs-A3 Cov可以較大程度緩解WSNs-A3 和WSNs-A3 Cov 有效活動節(jié)點數(shù)躍式下降的程度，并能使網(wǎng)絡具有很好的運行有效性，達到了節(jié)點能量均衡利用的目的，延長了網(wǎng)絡生命周期。下一步的工作重點將研究新的適合小世界特征的拓撲優(yōu)化方案，使拓撲優(yōu)化階段不再依附于其他算法之上。