面向無線通信網絡的分簇穩定性控制研究?

付 蝶

（四川文理學院信息化建設與服務中心 達州 635000）

1 引言

移動無線Ad Hoc網絡（MANET）［1］是由一組不依賴于固定通信網絡設施的無線移動節點組成，能夠快速形成網絡體系并提供重要通信與服務的臨時網絡。MANET具有多跳路由，節點能量有限，無線通信環境不可靠，動態拓撲快速變化等特性［2］。為了提高MANET的可擴展性，分簇是一種十分重要與常見的策略。采用分簇策略［3］后絕大多數節點的信息交換次數會降低，因此節點路由信息維護開銷也將降低，此外網絡規模也可以在一定程度上得到增大，并可保證網絡管理與控制的高效性。

分簇［4］的基本思想就是按照位置的遠近關系將網絡的節點分成若干集群，以便于管理。在一個簇內，部分節點負責建立分簇并且維持網絡拓撲的穩定性，這樣的節點也被稱作簇首節點，簇首節點的集合構成一個支配集［5］。簇內的節點一般被劃分為普通成員節點與協助簇間通信的網關節點，即簇首節點之間不進行直接的信息交換。一般的MANET分簇算法根據某些本地條件或者Ad Hoc網絡的屬性（例如節點密度、移動性、權重、剩余能量等因素）將節點加入到簇首節點集合之中［6］。現有的分簇機制中往往忽視了節點分布、節點頻繁變動對分簇穩定性的影響，且以上工作雖考慮到多種參數對分簇的影響，但多采用觀測值［7～9］的方法，缺乏嚴謹的推導模型來進行簇首選擇判定。因此本文有必要設計新的理論化簇首選擇判定模型。

此外，現有的分簇算法中未考慮如何維護調整動態網絡環境下的分簇結構。因此，本文還需給出相應的分簇維護機制以保證分簇結構的調整。本文的主要貢獻在于以下三個方面:1）提出了簇的期望生存時間模型，保證分簇在動態環境下具備更高的穩定性，即提高了簇的生存時間。2）給出了簇的可靠性通信度量模型，提高了動態環境下的通信可靠性，并降低了成員節點與簇首節點的更新次數與隨之帶來的通信開銷。3）給出了分簇的維護機制，以保證分簇結構的有效調整。

2 Ad Hoc網絡模型

根據圖論［10］知識可知，平面Ad Hoc網絡可以用一張無向圖來表示，即G=(V,E)。其中V代表了節點vi的集合，E表示由所有鏈路ei組成的集合。一般情況下節點的個數恒定，即V的勢保持不變，但E的勢隨著鏈路的建立和刪除發生改變。因此也可將分簇稱作受到額外限制的圖形分割問題。由于基本圖沒有表現出任何規則形結構，所以根據一定參數對圖形進行分割就成為一個NP-Hard問題［11］。分簇策略主要關心的問題是如何尋找支配集即最佳簇首集合:，使得成立。其中 N[vi]表示節點vi的相鄰區域，可定義為

其中，txrange表示節點vi的傳輸距離，通常情況下所有節點的傳輸半徑大小一致。節點領域密度被定義為N[vi]的勢，即

3 簇首的穩定性度量模型

短暫的成簇時間會導致簇首節點與成員節點的頻繁更迭，隨之帶來的通信開銷會增大節點的計算壓力，此外簇內節點分布對通信質量的影響亦會對簇的穩定性產生很大的影響。考慮到以上問題并未在以往文獻中得到很好的解決，本文設計了簇首的穩定性度量模型。該模型有以下兩個優點:1）保證所選擇的簇首節點所構成的簇具有最佳的生存時間；2）保證了所劃分簇的節點分布產生較小的通信開銷，同時具備較好的通信可靠性。

3.1 簇的期望生存時間度量模型

位于同一個分簇內的節點由于節點地位的劃分被分成簇首節點與成員節點。從拓撲穩定的角度出發，作為簇首的節點“希望”其成員節點位于簇內的時間越長越好，而成員節點亦“希望”其共同的簇首節點作為簇首的時間越長越好。簇首節點與其成員節點位于同一簇內的時間越長說明節點的變動頻度越小，即提高了簇的穩定性，同時降低了節點頻繁變動帶來的通信開銷。單純的移動性衡量方式并不能保證簇內節點位于同簇的時間較長，而以往的簇結構穩態度量方式也缺乏嚴格推導。為此，本文將簇的期望生存時間值，即簇首節點與其成員節點位于同一簇內的期望時間值作為衡量簇的穩定性的指標之一，并給出相應的推導公式。

假設在MANET，所有節點都含有GPS模塊，且節點的傳輸半徑都表示為R，則可得出簇首節點i與其任一成員節點 j在同一簇的生存時間求解方程:

其中，v表示節點速度，Dij表示節點之間的距離值，Dxij與Dyij分別表示該距離在水平與豎直方向的分量。此外

因此簇的期望生存時間被定義為

其中，dist()表示節點之間的距離函數，ni為成員節點個數。概率函數Pij表示節點i為簇首節點時，節點 j為其成員節點且兩點的距離值恰為Dij的概率。根據概率函數的定義，首先需要推出節點j位于節點i的傳輸半徑范圍之內的概率分布函數表達式 p{dist(i,j)≤R}。根據本文對網絡場景設定，節點的平面分布概率密度函數可表示為

其中，L表示場景的長度，W表示場景寬度。考慮到節點與節點之間具有相互獨立性，兩個節點的聯合平面分布概率密度函數就可以記作:

至此可以得出節點 j位于備選簇首節點i的傳輸半徑范圍之內的概率分布函數:

其中，元積分函數 funit_PDF(dist)為分段函數，當0＜R＜W 時，

當W≤R＜L時，

將式（12）帶入式（5）就可推導出 E(Ti)的量化度量函數。

通過求解簇的期望生存時間可知，若簇結構穩定性較高，則簇首節點所在的簇具有較大的E(Ti)值。除了規避以往分簇算法中采用移動性測度的缺陷，E(Ti)測度函數能較精確地衡量成員節點在簇中的權重大小(Pij)，即考慮到成員節點分布差異對簇結構穩定性的影響。在本文中，E(Ti)將作為新的簇首選擇測度因子之一。

3.2 簇的可靠性通信度量模型

在簇首節點傳輸覆蓋的范圍之內，成員節點距離簇首節點越近通信質量越好，反之信號隨著距離的增大而迅速衰減，成員節點與簇首節點的通信越發困難［13］。現有分簇算法大多將簇首節點與其成員節點的距離之和作為通信開銷度量因子，距離之和越小表明節點作為簇首節點的距離屬性、通信屬性越好。而在實際網絡中，往往存在簇首節點與其成員節點距離之和相同，而成員節點分布各異的情況。若在此情況下，節點分布差異會導致簇的整體通信質量與通信開銷的不同，則以往關于簇首選擇的策略缺乏完備的考慮。通信質量與報文丟失率存在負相關且報文丟失率Ploss與距離的函數關系可表示為［14］

式中，a,b,c,d為大于0的正擬合系數，x為節點之間的距離大小值，erf()為標準誤差函數。為了反映節點分布對通信質量的具體影響，對Ploss(x)求一階導數可得:

基于上述推導，本文可對簇的結構進行分層處理，圖1所示，并做出如下合理假設:當成員節點處在(0,r]時，簇首節點與成員節點的通信質量處在可接受范圍內即不產生通信風險；反之，當成員節點處在(r,R]時通信質量發生快速衰減，產生通信風險。

圖1 簇的分層結構

圖2 節點分布對通信的影響

圖2 給出了此時簇成員節點分布不同導致通信質量不同的示例。如圖2所示，A、F分別為簇的簇首節點，距離簇首節點F距離之和分別為

若DA=DF，則以A為簇首的四個成員節點全部落入通信質量可接受的區域范圍內，而以F為簇首的簇的四個成員節點中有2個節點落入通信質量快速衰減的區域范圍內。此時兩個簇雖然具有相同的距離屬性與密度屬性測度，卻產生不同的通信屬性測度。

為了形式化的描述此時節點分布不同對通信質量產生的影響，本文將通信風險概率分布函數定義為

其中，i表示簇首節點，j表示其成員節點，λ是一個介于0與1之間的調節系數。由此簇首節點i的平均通信風險代價（Communication risk）函數可被定義為

其中，n1表示距離簇首節點為(0,r]區域范圍內的成員節點數，ni為節點i的成員節點數。

考慮到MANET作為一種具備局部連通性的特殊聚集網絡［15］，本文對聚集網絡的標準中心性指標［16］函數進行改進，并作為MANET簇首通信負載（Communication load）函數以反映節點作為簇首的通信開銷與負載能力:

至此，可將簇的可靠性通信度量函數定義為

其中，Rci的取值越大，節點i作為簇首節點所在簇的通信開銷越小，簇的平均通信質量越高；反之，Rci越小則簇的通信開銷越大，簇的平均通信質量越低。因此在考慮節點通信質量與可靠性的同時，Rci仍反映了備選節點的距離測度與密度測度對簇首選擇的影響。

為了維護簇結構的穩定性，簇首節點所在簇應該具備較高的期望生存時間與通信質量且產生相對小的通信開銷。因此本文把簇首的穩定性度量函數即簇首選擇函數定義為

其中，τ代表Ad Hoc網絡系統所在的時刻，w1+w2=1，E'(Ti)和 Rc'i(τ)為歸一化表達式可記作:

至此，本文給出基于穩定性度量模型的一次簇首節點選擇算法過程:

算法1一次基于穩定性測度的簇首選擇

輸入:G=(V,E)

輸出:簇首節點（Clusterheads）

Fo（r所有節點i）Do:

將該消息以廣播的形式發送到節點傳輸半徑內的所有鄰居節點。

Fo（r所有處在節點i傳輸半徑范圍內的節點j）Do:

存儲收到的Wi信息，將收到的所有加權值與自己的加權值進行比較

IF（Wi為最大值）Then

j被選為簇首節點，且將該消息以廣播的形式發送到其傳輸半徑范圍內的鄰居節點。

Else

j接收到具有最大權重值節點的簇首選擇信息。

End

3.3 分簇的維護機制

MANET的實時動態性會導致簇首節點與成員節點不斷發生變化更迭。因為有必要給出一種分簇的維護機制以保證分簇結構的有效調整。考慮節點的兩種移動行為可知，節點在加入簇或者離開簇的時候都會導致簇結構的變化。當節點為簇首節點時，在它離開所在簇的時候需要通知簇內所有的成員節點，與此同時，需要在該簇內重新選擇一個合適的簇首節點。當節點為成員節點時，在它離開所在簇時就需要通知該簇的簇首節點，并更新成員表。用如下的流程表示節點離開導致的分簇維護機制:

算法2.1分簇的維護機制（節點離開行為）

Fo（r所有移動節點i）Do:

IF（節點i是簇首節點）Then

節點i在其所在的簇內向成員節點廣播一條信息（放棄簇首狀態）。

節點i將其當前狀態更新為未決定狀態，且申請加入一個可加入的簇。

Fo（r所有節點j，j是i所在簇的成員節點）Do:

節點 j更新所在簇信息并調用算法1重新選擇該簇的簇首節點。

Else

IF（節點i是成員節點）Then

節點i向其所在簇的簇首節點發送一條信息（離開所在簇）。

節點i將其當前狀態更新為未決定狀態，且申請加入一個可加入的簇。

For（所有節點 j，j是i所在簇的簇首節點）Do:

節點 j更新所在簇信息并向其他成員節點廣播一條信息（成員節點i離開簇）。

End

相應地，當成為未決定態的節點申請加入一個可加入的簇時，被加入簇的結構也會發生變化。用如下的流程表示節點加入簇導致的分簇維護機制。

算法2.2分簇的維護機制（節點加入行為）

For（所有移動節點i且節點i當前狀態為未決定態）Do:

節點i發送一個廣播信息申請加入一個可加入的簇，并等待可加入簇的回復信息。

IF（節點i收到了一條回復信息，即可加入的簇為1）Then

節點i加入該簇并更新相應的簇信息。

Else（節點i收到多條回復信息，即可加入的簇超過1）Then

節點i選擇加入W值最大的簇并更新相應的簇信息。

End

至此，就給出了分簇的維護機制以保證在動態環境下分簇結構的有效調整。

4 本文提出的算法對比實驗

4.1 仿真參數設置

本文利用NS-3［17］進行仿真實驗，首先對實驗參數進行配置，如表1所示。

表1 實驗參數

本文的網絡場景設為平面矩形場景，節點總個數以10作為遞增單位，移動模型為random waypointmodel，節點的最大移動速度以5作為遞增單位。

仿真實驗將 WCA［18］、FCA［19］、TVCA［20］的分簇算法與本文提出的分簇策略（SCA）進行對比，比較它們在不同節點密度、動態強度（移動速度）下的相關性能。

4.2 平均簇首個數

圖3描述了在Random Waypoint模型下，最大移動速度為10m/s，平均簇首節點個數與節點總個數的關系。從圖中可知，平均簇首個數隨著節點個數的增加而增大，但不具有嚴格的的線性關系。本文提出的算法（SCA）所得的平均簇首節點個數總體上多于WCA算法，少于其他兩種算法（FCA＞TVCA）。不難發現FCA算法所得的平均簇首節點個數變動差異最大。用最大攜帶成員個數（2 ln(N)）衡量五種算法可知，本文提出的算法（SCA）與其余三種分簇算法都可保證成員節點個數小于最大攜帶成員個數。

圖3 平均簇首節點個數vs節點個數

圖4平均簇首節點個數vs移動速度

圖4 描述了在Random Waypoint模型下，節點總個數為50，平均簇首節點個數與移動速度的關系。從圖中可知，平均簇首個數不會隨最大移動速度的增加而增大或減少，而是呈現一種小幅度浮動狀態。本文算法（SCA）所得的平均簇首節點個數總體上多于WCA算法與FCA算法（FCA＞WCA），少于TVCA。

4.3 成員節點更新頻度

圖5描述了在Random Waypoint模型下，最大移動速度為10m/s，成員節點累積更新次數與節點總個數的關系。如圖所示，成員節點累積更新次數會隨著節點個數的增加而增大，但不具有嚴格的線性關系。在Random Waypoint模型中，本文提出算法（SCA）所得的成員節點累計更新次數最小。以本文提出的算法（SCA）作為基礎進行對比，WCA、FCA、TVCA的成員節點累積更新次數平均增多了45.6%、8.1%、37.5%。

圖5 成員節點更新頻度vs節點個數

圖6 描述了在Random Waypoint下，節點總個數為50，成員節點累積更新次數與移動速度的關系。如圖所示，成員節點累積更新次數會隨著最大移動速度的增加而增大，但不具有嚴格的線性關系。本文提出算法（SCA）所得的成員節點累計更新次數整體上最小。以本文提出的算法（SCA）作為基礎進行對比，在Random waypoint模型中，WCA、FCA、TVCA的成員節點累積更新次數平均增多了60.1%、11.2%、33.6%。

圖6 成員節點更新頻度vs移動速度

4.4 支配集更新頻度

圖7 描述了在Random Waypoint模型下，最大移動速度為10m/s，簇首節點累積更新次數與節點個數的關系。如圖所示，簇首節點累積更新次數會隨著節點個數的增加而增大，但不具有嚴格的線性關系。以本文提出的算法（SCA）作為基礎進行對比，在Random waypoint模型中，WCA、FCA、TVCA的簇首節點累積更新次數平均增多了38.9%、18.3%、20.1%。

圖7 支配集更新頻度vs節點個數

圖8 描述了在Random Waypoint模型下，節點總個數為50，簇首節點累積更新次數與移動速度的關系。如圖所示，簇首節點累積更新次數會隨著最大移動速度的增加而增大，但不具有嚴格的線性關系。以本文提出的算法（SCA）作為基礎進行對比，在 Random waypoint模型中，WCA、FCA、TVCA的簇首節點累積更新次數平均增多了47.8%、15.2%、26.8%。

圖8 支配集更新頻度vs移動速度

4.5 節點通信負載

圖9 描述了在Random waypoint模型下，最大移動速度為10m/s，單位時間平均每個節點發送信息數量與節點個數的關系。如圖所示，單位時間平均每個節點發送信息數量會隨著節點個數的增加而增大，但不具有嚴格的線性關系。以本文提出的算法（SCA）作為基礎進行對比，在Random waypoint模型中，WCA、FCA、TVCA的節點單位時間發送信息數量平均增多了35.0%、5.2%、23.9%。

圖10描述了在Random waypoint模型下，節點總個數為50，單位時間平均每個節點發送信息數量與移動速度的關系。如圖所示，單位時間平均每個節點發送信息數量會隨著節點個數的增加而增大，但不具有嚴格的線性關系。以本文提出的算法（SCA）作為基礎進行對比，在Random waypoint模型中，WCA、FCA、TVCA的節點單位時間發送信息數量平均增多了44.6%、2.3%、21.8%。

圖9 節點通信負載vs節點個數

圖10 節點通信負載vs移動速度

4.6 結果分析

分析以上實驗數據組，本文可得出如下的結論:

1）若用理想簇首節點個數（實現分簇全覆蓋的最少簇首節點個數）衡量分簇效率，本文算法SCA得到的簇首個數指標并未獲得最佳的分簇效率。

2）從支配集與成員節點更新頻度的實驗數據對比可知，本文提出的SCA算法能夠有效地降低節點的更新頻度，顯著地提高了分簇結構的穩定性，這也說明了本文提出的簇首穩定性度量模型具有正確性。

3）簇首選擇與頻繁地節點更迭都會增加節點交換信息的數量，增加通信開銷。從節點通信負載實驗數據對比可知，本文提出算法（SCA）的通信負載指標優于其余算法，即有效地減少了系統的通信開銷，也說明了本文提出的簇首穩態度量模型與分簇行為認知機制是實際可行的。

5 結語

分簇是一種提高動態網絡可擴展性與拓撲穩定性的重要方法。現有MANET分簇算法中往往未考慮到節點分布差異與頻繁的節點狀態更迭對分簇穩定性的影響。基于以上事實，本文提出了基于穩定性控制的MANET分簇策略（SCA）。本文通過構建簇的期望生存時間模型與簇的可靠性通信度量模型，給出了一種新的簇首穩定性度量模型進行簇首選擇。同樣給出了分簇的維護機制，以保證動態網絡環境下分簇結構的有效調整。實驗結果證明本文提出的分簇算法能夠有效地改善分簇的穩定性，并減少節點的通信負載。