移動自組織網(wǎng)路由穩(wěn)定性分析

郭建立，劉 剛

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

0 引言

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

1 熵度量

1.1 局部拓撲變化動態(tài)特征

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

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

局部空間內(nèi)的邏輯鏈路可以劃分為2種:一類是節(jié)點D與其所有鄰居節(jié)點間存在的鏈路，這類鏈路的變化程度能夠反映動態(tài)網(wǎng)絡(luò)環(huán)境中節(jié)點D的鄰居節(jié)點的變化特性;另一類是節(jié)點D的所有鄰居節(jié)點之間的鏈路，這類鏈路的變化能夠反映局部范圍內(nèi)鄰居節(jié)點彼此之間以及鄰居節(jié)點與節(jié)點D之間拓撲結(jié)構(gòu)變化的動態(tài)特征。

1.2 局部拓撲變化熵度量

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

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

記Si為節(jié)點k局部拓撲結(jié)構(gòu)變化過程中的一個狀態(tài)，各狀態(tài)元素按時間順序構(gòu)成一個有序序列:

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

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

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

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

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

1.3 路由穩(wěn)定性度量

在移動自組織網(wǎng)絡(luò)中，一條從源節(jié)點S到目的節(jié)點D的路由Path（S，D）的穩(wěn)定程度可以由該路由上所有轉(zhuǎn)發(fā)節(jié)點的穩(wěn)定程度來共同反映，通過以下2個參數(shù)來描述:

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

1.4 RODSR路由協(xié)議

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

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

2 仿真實驗及結(jié)果分析

2.1 仿真實驗

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

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

2.2 仿真結(jié)果分析

在仿真過程中，針對不同網(wǎng)絡(luò)環(huán)境下的分組成功遞交率和端到端分組時延，對DSR和RODSR協(xié)議進行了比較。

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

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

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

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

圖2 端到端延遲性能對比

3 結(jié)束語

基于局部拓撲結(jié)構(gòu)變化的熵度量方法能夠?qū)植客負浣Y(jié)構(gòu)變化的不確定性程度給以定量的度量，適用于在動態(tài)網(wǎng)絡(luò)環(huán)境中選擇相對穩(wěn)定的路由。該方法提升了移動自組網(wǎng)路由協(xié)議的性能，能夠有效降低網(wǎng)絡(luò)開銷，提高有限網(wǎng)絡(luò)資源的利用效率，并延長網(wǎng)絡(luò)的生命周期。

[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]劉剛，郭建立，崔剛，等.移動自組織網(wǎng)絡(luò)環(huán)境中負載均衡策略研究[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.