移動自組織網路由穩定性分析

郭建立，劉 剛

（1.北京郵電大學，北京100876;2.中國電子科技集團公司第五十四研究所，河北石家莊050081;3.燕山大學電氣工程學院，河北秦皇島066004）

0 引言

在移動自組織網絡環境中，節點的自由移動導致網絡拓撲結構變化頻繁，用于數據轉發的路由壽命相對于傳統有線網絡極其短暫。在動態網絡環境中選擇一條穩定的路由能夠有效地減少網絡路由重建和維護過程所需的帶寬和能源消耗、避免對網絡中其他節點的正常數據傳輸產生干擾[1-3]，并能夠提供更好的QoS需求保障，這在網絡資源和能源供應都極其有限的移動自組織網絡中尤其重要[4]。該文分析了移動自組織網絡中節點的動態特性與其局部拓撲結構變化程度之間的關系，提出了一種利用局部拓撲結構變化的不確定性程度刻畫移動節點動態特征的穩定路由選擇策略，并利用信息熵的特性對局部拓撲結構變化的不確定性程度給以定量的度量。

1 熵度量

1.1 局部拓撲變化動態特征

在包含n個節點的移動自組織網絡中，某一時刻t的網絡拓撲結構可以表示為一個無向圖Tt=〈V，Lt〉，其中V={N1，N2，…Nn}是網絡中所有節點的集合，Lt是t時刻網絡中狀態為連通的所有邏輯鏈路組成的集合。

定義1:節點D在時刻t的局部拓撲結構信息由節點D、節點D的鄰居，以及它們間的邏輯鏈路組成，表示為其中為t時刻節點D所在局部拓撲空間內所有節點的集合為t時刻局部拓撲空間內存在的所有邏輯鏈路的集合。

局部空間內的邏輯鏈路可以劃分為2種:一類是節點D與其所有鄰居節點間存在的鏈路，這類鏈路的變化程度能夠反映動態網絡環境中節點D的鄰居節點的變化特性;另一類是節點D的所有鄰居節點之間的鏈路，這類鏈路的變化能夠反映局部范圍內鄰居節點彼此之間以及鄰居節點與節點D之間拓撲結構變化的動態特征。

1.2 局部拓撲變化熵度量

在信息論中，熵[5]作為隨機變量的自信息，用來度量一個隨機變量自身所具有的不確定性程度，一個離散型隨機變量X的熵定義為:

式中，χ為離散型隨機變量X的取值空間;p（x）為隨機變量X的概率密度函數。

記Si為節點k局部拓撲結構變化過程中的一個狀態，各狀態元素按時間順序構成一個有序序列:

可用一對離散隨機變量S和R作為局部拓撲結構變化序列的特征向量來表示節點的動態特征:S表示局部拓撲結構狀態的變化，取值空間為ST（k），其概率密度函數為:

式中，R表示各狀態在SN（k）序列中的實際分布。如果將SN（k）序列中連續出現的同一個狀態形成的子序列稱為一個子游程，則可以將SN（k）序列表示為游程序列形式RN（k）:

令LEN（Ri）為子游程Ri的長度，將RN（k）序列表示為概率形式，其概率密度函數為:

在RN（k）序列中有通過以上計算結果可以分別計算SN（k）和RN（k）的熵:

若將SN（k）、RN（k）視為局部拓撲狀態變化過程中2個獨立的隨機特征向量，則根據信息熵的鏈式法則，節點k局部拓撲結構變化的不確定性程度H（TN（k））可以由下式計算得到:

1.3 路由穩定性度量

在移動自組織網絡中，一條從源節點S到目的節點D的路由Path（S，D）的穩定程度可以由該路由上所有轉發節點的穩定程度來共同反映，通過以下2個參數來描述:

式中，Htotal（S，R）為Path（S，D）中所有轉發節點局部拓撲變化熵的和;Hmin（S，R）為Path（S，D）中瓶頸節點的穩定程度。顯然，路由的長度以及轉發節點的穩定程度都將對Htotal（S，R）的值造成影響，因此那些跳數少并且轉發節點較穩定的路由具有更小的Htotal（S，R）值。

1.4 RODSR路由協議

為了定量評估該文所提出的穩定路由選擇策略，對源動態路由協議（Dynamic Source Routing Protocol，DSR）進行了必要的擴展，提出了一種基于逆向優化的源動態路由協議（Reverse Optimized Dynamic Source Routing Protocol，RODSR）。RODSR對DSR協議的路由建立過程進行了部分改進，其目的是驗證局部拓撲變化熵度量對路由協議性能的提升。

在RODSR中，每個節點需要維護一個兩跳鄰居列表以實現逆向路由優化，其操作過程與DSR協議基本相同。為了實現路由的逆向優化操作，需要擴展DSR協議的RREQ分組，使其攜帶節點的最新穩定性測度信息，以及節點所維護的鄰居節點信息。當RREQ到達目的節點時，由目的節點結合RREQ中獲取的路由信息和本地維護的鄰居列表信息對路由進行優化。

2 仿真實驗及結果分析

2.1 仿真實驗

使用NS2.31仿真軟件對協議進行仿真，節點移動模型采用隨機點模型（Random Waypoint Model，RWM），仿真區域設置為1800×900m2的矩形區域，仿真過程中的其他參數設置如表1所示。

表1 仿真參數設置

2.2 仿真結果分析

在仿真過程中，針對不同網絡環境下的分組成功遞交率和端到端分組時延，對DSR和RODSR協議進行了比較。

圖1比較了DSR和RODSR協議的分組遞交成功率。從圖1（a）中可以看出，在節點移動速度緩慢的網絡環境中，RODSR協議的分組遞交成功率提高并不明顯，這是因為相對于節點的無線傳輸覆蓋范圍，節點移動所導致的拓撲變化較緩慢，節點間拓撲變化的不確定程度差異較小。但是，隨著節點移動速度的增加，節點間拓撲變化程度的差異加劇，RODSR協議的性能有明顯提升。

從圖1（b）中可以看出，在節點密度較小的情況下，RODSR協議的分組遞交成功率僅有小幅提高，這是由于共同鄰居數較少，使得RODSR協議的優化機會減小。但是，隨著節點密度的增加，RODSR協議可利用的優化節點數開始增多，從而使得協議的性能較DSR協議有較大提升。

圖1 分組遞交成功率性能對比

圖2比較了2種路由協議的端到端分組時延?？梢钥闯鯮ODSR協議的端到端延遲相比于DSR協議具有比較明顯的降低，還可以看出網絡負載對網絡的端到端延遲也具有明顯的影響。

圖2 端到端延遲性能對比

3 結束語

基于局部拓撲結構變化的熵度量方法能夠對局部拓撲結構變化的不確定性程度給以定量的度量，適用于在動態網絡環境中選擇相對穩定的路由。該方法提升了移動自組網路由協議的性能，能夠有效降低網絡開銷，提高有限網絡資源的利用效率，并延長網絡的生命周期。

[1]SU，LEE SJ，GERLA M.Mobility prediction and routing in ad hoc wireless networks[J].International Journal of Network Management，2001，11（1）:3-30.

[2]LENDERS V，WAGNER J，HEIMICHER S，etal.An empirical study of the impact of mobility on link failures in 802.11 ad hoc network[J].IEEE Wireless Communications，2008，15（6）:16-21.

[3]劉剛，郭建立，崔剛，等.移動自組織網絡環境中負載均衡策略研究[J].無線電工程，2010，40（7）:1-3.

[4]ZHANG H，DONG YN.A novel path stability computation model for wireless Ad Hoc networks[J].IEEE Signal Processing Letters，2007，14（12）:928-931.

[5]CHANNON CE.A mathematical theory of communication[J].The Bell System Technical Journal，1948（27）:379-423，623-656.