周期休眠輪詢耦合拓撲優化的WSN節點覆蓋算法

龐國莉，王小英，潘志安

(防災科技學院 信息工程學院，河北 三河 065201)

0 引 言

為提高無線傳感網(wireless sensor network，WSN)節點覆蓋性能，增強網絡傳輸能力及拓撲收斂速度[1-3]，研究者提出了一些具有前瞻性解決算法。如Shan等[4]提出了一種基于貪心機制的WSN網絡傳輸節點覆蓋算法，其首先采用網格方式設計了節點隨機部署模型，通過強化網格部署密度及提升節點隨機布撒強度，增強了簇頭節點對傳輸區域的覆蓋能力。不過，該算法需要追加簇頭節點密度來保證網絡傳輸質量，在節點密集環境時容易造成嚴重的傳輸串擾現象，易發生嚴重的網絡擁塞現象。Yin等[5]提出了一種WSN網絡傳輸節點覆蓋算法，通過在傳輸熱點區域部署若干傳輸能力較強的節點作為備用中繼節點，構建簇節點-中繼節點路徑優化方案強化網絡鏈路傳輸能力，可顯著提高網絡傳輸過程的穩定性，改善數據擁塞現象，具有較好的實際部署價值。但是，該算法在數據匯聚帶寬較高時，會直接削弱傳輸鏈路收斂性能，使得高干擾條件下網絡易因中繼節點受限而出現癱瘓現象。Sheng等[6]提出了一種WSN網絡傳輸節點覆蓋算法，通過預置傳輸節點作為備用簇頭節點，優化區域傳輸質量，提高簇頭節點覆蓋能力。然而，該算法需要將網絡中傳輸能力較強的節點作為備用節點，使得數據傳輸過程中無法利用這些傳輸能力較強的節點進行網絡傳輸，降低了網絡傳輸能力。

為了增強WSN網絡節點覆蓋能力，提高數據匯聚能力，提出了一種WSN網絡傳輸節點覆蓋算法。設計基于周期休眠機制的中繼節點權值輪詢預部署方法，以提高WSN網絡骨干節點的傳輸能力。采用拉普拉斯校驗機制優化中繼節點有向圖的收斂性能，剔除可能受限的中繼節點，達到改善中繼節點性能的目的，結合休眠方式進一步增強了中繼節點的匯聚能力。隨后，基于最優連通度來優化中繼節點部署性能，提高中繼節點數據傳輸的穩定性。最后，通過NS2仿真實驗環境，驗證了本文算法的性能。

1 網絡模型

無線傳感網節點一共分為區域節點、簇頭節點、中繼節點，如圖1所示。區域節點(regional node，R節點)作為數據采集節點，主要針對簇頭覆蓋區域內的數據進行采集并傳輸至簇頭節點，傳輸過程一般均采用單跳模式[7]；簇頭節點(cluster head node，CH節點)主要用于維護區域結構并匯聚RN節點所傳數據，此外CH節點還需維護CN-sink之間的鏈路，以便維持數據傳輸過程的穩定性；中繼節點(relay node，RN節點)主要用于維護傳輸路徑的穩定性，確保CH節點間處于暢通狀態，實踐中往往以部分簇頭節點充當R節點的功能。本文主要關注簇頭節點與sink節點間數據暢通性能，因此網絡模型設計如下：

(1)網絡節點一共分為R節點、CH節點和RN節點3類，如圖1所示，3類節點均為靜止狀態，在網絡部署完成后節點位置將處于不變狀態；

圖1 網絡部署

(2)數據傳輸過程均遵循周期特性，即數據傳輸過程中以時間片為單位進行輪詢傳輸，一旦數據傳輸完畢之后，R節點將處于休眠狀態；

(3)中繼節點和簇頭節點均具有相同的制式信號，兩者具有不同的覆蓋半徑，但初始覆蓋半徑均相同；

(4)網絡節點按照5G信號模式進行信號預成型，接入協議選取MAC接入協議；

(5)Sink節點僅有一個，但Sink節點與CH節點間遵循多跳傳輸模式，由RN節點負責數據接力傳輸。

由于節點數據傳輸過程中均存在數據接收和數據發送兩個環節，接收環節和發送環節的數據帶寬均維持恒定值，不妨設數據帶寬為B，則節點接收數據能耗Erecv(B)滿足如下模型

Erecv(B)=dBP

(1)

式中：d表示節點間數據傳輸距離，P表示節點傳輸功率。

節點發送數據能耗Esend(B)滿足如下模型

Esend(B)=dBP+BPdn

(2)

式中：n表示距離系數。一般而言，若節點處于自身覆蓋半徑之內，n取2，反之則可以通過測量方式獲取具體數值，但一般均大于4。

若節點初始能量為E，則剩余能量Elost(B)滿足

Elost(B)=E-Erecv(B)-Esend(B)

(3)

針對任意一個中繼節點而言，由于中繼節點可以同時匯聚多個簇頭節點數據，因此中繼節點的能量消耗Elost(B1,B2,…,Bm)可由如下模型獲取

(4)

式中：Bi表示第i個簇頭節點與中繼節點的匯聚帶寬，di表示該簇頭節點與中繼節點間距離。

網絡生存周期內，中繼節點將持續進行數據的發送和傳輸；若部分中繼節點出現受限現象，將通過其余的中繼節點繼續進行數據傳輸過程。由于WSN節點分布具有不均衡性[8]，部分熱點區域內中繼節點能量消耗將顯著高于網絡均值[9]。此外，不同物理部署區域內信道噪聲也存在強弱之分，節點傳輸穩定性亦將有所差異[10]。因此，網絡覆蓋過程中需要充分考慮到RN節點和CH節點特性，有針對性的部署RN節點，以便提高網絡骨干傳輸鏈路的性能，增大網絡生存周期。

2 本文WSN網絡傳輸節點覆蓋算法

節點部署過程中需要充分考慮到數據傳輸與節點特性，同時兼顧網絡鏈路穩定性能及優化中繼節點部署。因此，本文設計了一種基于周期休眠輪詢機制及拉普拉斯拓撲耦合優化的WSN網絡傳輸節點覆蓋算法(WSN transmission node coverage algorithm based on periodic sleep polling mechanism and Laplace topology coupling optimization，PSP-LTC算法)。該算法由3個部分組成：基于周期休眠機制的中繼節點權值輪詢預部署、基于拉普拉斯校驗機制的中繼節點拓撲耦合優化方法和基于最優連通度的網絡拓撲參數更新方案。

2.1 基于周期休眠機制的中繼節點權值輪詢預部署

由于中繼節點需要選取網絡中若干個性能較優的節點，其數量不宜超過一定比例，否則被選取的簇頭節點性能將會受到嚴重影響[10]。因此，本文針對傳統方案在部署中繼節點過程中存在的不足，設計了一種中繼節點權值輪詢預部署，如圖2所示。首先將網絡區域按照初級和次級結構進行分割，盡量減少中繼節點個數：

(1)首先對網絡區域進行分割，獲取初始CH節點集合ΩCH，并將集合中剩余的CH節點作為備用中繼節點；

(2)從ΩCH中選取最接近sink節點的2個節點作為種子節點，如圖2所示，并統計ΩCH中可完全覆蓋網絡區域的備用簇頭節點集合ΔCH；

圖2 基于周期休眠機制的中繼節點權值輪詢預部署

(3)將種子節點覆蓋區域從網絡區域中剔除，并繼續統計ΔCH中剩余可用于網絡覆蓋的備用簇頭節點集合ΔCH(1)；該過程將進行n次，直到種子節點無法被選取為止；最終得到備用簇頭節點集合為ΔCH(n)；

(4)將ΔCH(n)中全部節點設置為中繼節點，統計中繼節點中連通度低于2的節點，記為ΔRH；

(5)將離ΔRH最近的節點作為備用中繼節點，并加入到集合ΔCH(n)，本輪傳輸周期結束后，將重新執行(1)；方案結束。

集合ΔCH(n)可由圖論中所提及的有向圖G和系數矩陣K表示[11]，如圖3所示，其中系數矩陣中某元素K(i,j)為0時，表示i節點與j節點之間不存在數據中繼關系。K(i,j)為1時，表示數據由節點i傳輸至節點j；K(i,j)為-1時，表示數據由節點j傳輸至節點i。

圖3 有向圖

在圖3中所示的有向圖，其系數矩陣K為

(5)

由線性代數知識可知[13]，系數矩陣K的特征值λn共有n個，滿足如下關系

λn≥λn-1…≥λ2≥λ1≥0

(6)

式中：若λ1=0表示網絡中存在盲區，盲區中簇頭節點無法通過中繼節點與sink節點進行數據交互。若λ1=1說明網絡節點處于全連通狀態，此時網絡具有良好的健壯性。

由于系數矩陣K滿足拉普拉斯收斂性能[14]，因此該矩陣的權值系數W(G)可由如下模型獲取

(7)

式中：n表示有向圖G中節點個數，i與j表示任意兩個節點，d(i,j)表示i節點與j節點之間對應的系數矩陣元素K(i,j)。

結合式(6)和式(7)可知系數矩陣K的特征值λn與權值系數W(G)滿足如下關系

(8)

在進行中繼節點預部署過程時，可通過權值系數W(G)來裁定部署效果：若權值系數W(G)小于1，說明當前網絡中存在一些連通性能較差的中繼節點，這些中繼節點與其余簇頭節點及中繼節點連通程度較低，需要持續執行(1)-(5)，以便提高中繼節點對網絡區域的覆蓋能力。通過不斷輪詢權值系數W(G)并使之持續高于1，則可顯著提高網絡中繼節點覆蓋能力，增強節點拓撲的連通性能。

2.2 基于拉普拉斯校驗機制的中繼節點拓撲優化

由于中繼節點個數與網絡穩定性能并非呈現強正相關性，因此在網絡處于穩定狀態時需要盡量減少中繼節點個數。由式(7)可知，權值系數W(G)小于1時，說明網絡中存在若干連通性較差的中繼節點，但若權值系數W(G)接近1時，中繼節點雖然可暫時滿足網絡傳輸所需，但易因受限而導致網絡出現盲區，因此本文設計基于拉普拉斯校驗機制的中繼節點拓撲優化方法，詳情如下：

(1)評估中繼節點連通程度，首先按式(7)來構建連通系數L(G)如下

(9)

(2)采用拉普拉斯方式進行拓撲連通校驗。在中繼節點個數不唯一的情況下，需要盡量擴大式(9)所示的連通系數，以便網絡能以較強的收斂性能實現拓撲收斂。因此，該問題可以用拉普拉斯數學校驗模型進行解決，其函數為

(10)

(11)

其中，T表示矩陣轉秩。

(3)將系數矩陣K對應的連通圖進行優化并進行路由初始化。系數矩陣K僅由中繼節點對應的有向圖唯一決定，且K對應的有向圖G即為網絡節點的拓撲連通圖。將該連通圖對應的路由表作為初始路由表。

(4)剔除不滿足需求的失效節點。不妨設完成2.1節所示基于周期休眠機制的中繼節點權值輪詢預部署后，中繼節點數據傳輸比例系數FR為

(12)

式中：m表示預部署中繼節點總數，Em表示第m個中繼節點的能量。

由式(12)可知，FR越低，則說明中繼節點出故障的概率越低，網絡拓撲收斂性能也就越高。

令網絡傳輸周期為Tnet，可由如下模型獲取

(13)

式中：k表示按式(8)裁決后新增加的中繼節點總數。

聯立式(3)和式(13)對中繼節點逐個進行裁決，若不滿足式(3)則將中繼節點進行剔除，使得備用簇頭節點集合為ΔCH(n)始終處于可用狀態。

2.3 基于最優連通度的網絡拓撲參數更新

完成基于拉普拉斯校驗機制的中繼節點拓撲耦合優化方法后，網絡中備用簇頭節點集合ΔCH(n)將在滿足網絡傳輸需求的同時，數量始終處于較少狀態。然而，由于單純采用拉普拉斯矩陣校驗難以適應網絡節點密度較高的實際應用場景，因此需要對備用簇頭節點集合ΔCH(n)進行實時更新，以便網絡拓撲能夠以較優的參數進行數據傳輸。備用簇頭節點集合ΔCH(n)中當前最優連通度的節點記為dij，其中i表示該節點匯聚的節點，j表示該節點匯出的節點。據此設計基于最優連通度的網絡拓撲參數更新方法如下：

(1)定義迭代函數。為了優化系數矩陣K所表示的有向圖連通系數，定義了如下迭代函數

dij(n)=dij(n-1)+μ(dij(n-2)-dij(n-3))

(14)

式中：n表示第n次迭代次數，μ為系數矩陣K中小于0的系數個數，此時系數矩陣K由ΔCH(n)確定。

(2)更新拉普拉斯系數矩陣。按式(14)來更新式(11)中的系數矩陣，更新完畢后，按如下模型計算中繼節點i和中繼節點j之間的連通概率P(i,j)

P(i,j)=|K|e-μL(i,j)

(15)

式中：|K|表示計算K的行列式的值；L(i,j)表示中繼節點i和中繼節點j之間的距離；其余參數同式(14)。

(3)根據系數矩陣判斷節點連通度并進行拓撲參數優化。通過式(15)對系數矩陣K中節點進行判斷，若相應的連通概率小于0.5，說明節點容易處于受限狀態，將該節點剔除出備用簇頭節點集合ΔCH(n)后，可減少中繼節點數量，并確保備用簇頭節點的連通概率均要高于0.5，進一步降低了中繼節點受限的概率。

3 仿真實驗

為便于測試本文算法的性能，采用NS2仿真實驗環境[15]。實驗采用5G制式節點，信號預成型過程按照128ASK星座一次成型；部署區域為矩形區域，大小為10240 m×10240 m；節點采用隨機布撒方式一次成型，布撒完畢后其位置將處于不變狀態。其余仿真參數見表1。對比組算法采用當前WSN網絡部署過程中常用的基于正交旋轉精度提升的WSN節點數據優化傳輸算法[16](optimal data transmission algorithm of WSN nodes based on the improvement of orthogonal rotation accuracy，ORA)和基于啟發蟻群優化-馬爾可夫鏈蒙特卡羅優化傳輸算法[17](minimizing transmission loss using inspired ant colony optimization and Markov chain Monte Carlo in underwater WSN environment，AC-MCMC)。測試指標選取網絡傳輸周期、網絡覆蓋率、數據匯聚帶寬。

表1 仿真參數

實驗開始后，按參數分別部署低信道噪聲環境和高信道噪聲環境兩種實驗環境，按照數據傳輸輪數測試并記錄網絡傳輸周期、網絡覆蓋率、數據匯聚帶寬3項指標。

3.1 網絡傳輸周期

圖4為低信道噪聲環境和高信道噪聲環境兩種實驗環境下，本文算法、ORA算法及AC-MCMC算法的網絡傳輸周期測試結果。測試結果表明：本文算法在兩種實驗環境下網絡傳輸周期均要顯著高于ORA算法及AC-MCMC算法，具有網絡生存能力較強的特點。這是由于本文算法針對WSN網絡數據傳輸過程中存在的節點受限現象，采用預部署機制提前布置中繼節點，采取連通度優化的方案，提高中繼節點之間拓撲鏈路連通程度，降低簇頭節點間數據傳輸過程存在的傳輸抖動現象，有效強化了網絡骨干節點的數據傳輸能力，節點受限現象發生頻率較低。ORA算法主要針對節點信號成型過程中存在的信道干擾現象，采取優化數據預發射的方式提高節點生存能力，然而該算法在數據匯聚時均采用簇頭節點作為中繼節點并直接匯聚到sink節點的方式，易因簇頭節點受限而導致傳輸過程受阻，因而網絡傳輸周期較短。AC-MCMC算法雖然采用了蟻群機制優化中繼節點分布，然而由于該算法并未設計反饋機制來進一步改進中繼傳輸節點的覆蓋能力，特別是該算法在數據傳輸鏈路優化過程中僅采取單純收斂機制進行鏈路樣本訓練，傳輸鏈路難以迅速生成可達路由，降低了中繼節點傳輸能力，因而該算法網絡傳輸周期亦要低于本文算法。

圖4 網絡傳輸周期測試結果

3.2 網絡覆蓋率

圖5為低信道噪聲環境和高信道噪聲環境兩種實驗環境下，本文算法、ORA算法及AC-MCMC算法的網絡覆蓋率測試結果。由圖發現，本文算法在兩種實驗環境下網絡覆蓋率均要顯著高于ORA算法及AC-MCMC算法，具有高網絡覆蓋率的特點。這是由于本文在采用了基于周期休眠機制的中繼節點權值輪詢預部署的同時，鑒于中繼節點存在的連通性問題，設計了基于拉普拉斯校驗機制的中繼節點拓撲耦合優化方法，用于提升中繼節點覆蓋能力，改善中繼節點的連通性能，提高了網絡拓撲的收斂性能，使其具有較高的網絡覆蓋率。ORA算法直接使用簇頭節點作為中繼傳輸節點，一旦發生簇頭節點受限現象時將使得網絡覆蓋率呈現不斷下降的態勢，因而使其網絡覆蓋率有待提高。AC-MCMC算法采用馬爾科夫收斂方式提高中繼傳輸節點覆蓋能力，然而由于馬爾科夫收斂方式需要較長時間進行拓撲學習及訓練，網絡拓撲收斂效率要顯著低于本文算法，影響到了中繼節點覆蓋效果，使其網絡覆蓋率較低。

圖5 網絡覆蓋率測試結果

3.3 數據匯聚帶寬

圖6為低信道噪聲環境和高信道噪聲環境兩種實驗環境下，逐秒統計當前數據匯聚帶寬，所得到的本文算法、ORA算法及AC-MCMC算法的網絡匯聚帶寬測試結果。測試結果表明：本文算法始終具有數據匯聚帶寬較高的優勢。這是由于本文算法針對中繼節點存在的高受限概率的特點，設計了基于最優連通度的網絡拓撲參數更新方案，用于提高中繼節點的連通能力，因而可顯著增強網絡數據傳輸能力，具有數據匯聚帶寬較高的特點。ORA算法由于并未對簇頭節點及中繼節點受限情況進行優化，傳輸過程中易因信道噪聲產生較為嚴重的鏈路抖動現象，因而數據匯聚能力較差，使得數據匯聚帶寬也較低。AC-MCMC算法雖然采用蟻群機制優化中繼節點部署，可在一定程度上提高中繼節點的數據傳輸能力，然而由于該算法同時具有網絡拓撲收斂速度較慢的特點，因此中繼鏈路出現抖動時難以迅速更換中繼節點，使得數據匯聚能力亦要低于本文方案。

圖6 數據匯聚帶寬測試結果

4 結束語

為提高無線傳感網部署過程中存在的節點覆蓋難題，提出了一種基于周期休眠輪詢機制及拉普拉斯拓撲耦合優化的WSN網絡傳輸節點覆蓋算法。首先針對中繼節點的能量消耗特點，通過預部署中繼節點方式優化網絡骨干節點傳輸能力，提出了一種改進的網絡傳輸模型。隨后設計了基于周期休眠機制的中繼節點權值輪詢預部署、基于拉普拉斯校驗機制的中繼節點拓撲耦合優化方法，用于提高中繼節點數據傳輸能力，降低網絡拓撲收斂復雜度。最后，針對中繼節點系數矩陣具有收斂較慢等不足，通過迭代方式提高系數矩陣連通性能，構建了基于最優連通度的網絡拓撲參數更新方案,用于提高中繼節點的覆蓋效率，改善網絡匯聚能力，穩定網絡傳輸性能。

下一步，將針對本文算法對移動節點部署場景適用性較差的不足，擬引入無線傳感網節點流動性控制機制，增強本文算法在移動環境下的網絡覆蓋能力，進一步提高本文算法在實際部署過程中的適用場景。