郭建立，劉 剛

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

0 引言

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

1 熵度量

1.1 局部拓?fù)渥兓瘎?dòng)態(tài)特征

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

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

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

1.2 局部拓?fù)渥兓囟攘?/h3>

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

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

記Si為節(jié)點(diǎn)k局部拓?fù)浣Y(jié)構(gòu)變化過(guò)程中的一個(gè)狀態(tài)，各狀態(tài)元素按時(shí)間順序構(gòu)成一個(gè)有序序列:

可用一對(duì)離散隨機(jī)變量S和R作為局部拓?fù)浣Y(jié)構(gòu)變化序列的特征向量來(lái)表示節(jié)點(diǎn)的動(dòng)態(tài)特征:S表示局部拓?fù)浣Y(jié)構(gòu)狀態(tài)的變化，取值空間為ST（k），其概率密度函數(shù)為:

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

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

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

若將SN（k）、RN（k）視為局部拓?fù)錉顟B(tài)變化過(guò)程中2個(gè)獨(dú)立的隨機(jī)特征向量，則根據(jù)信息熵的鏈?zhǔn)椒▌t，節(jié)點(diǎn)k局部拓?fù)浣Y(jié)構(gòu)變化的不確定性程度H（TN（k））可以由下式計(jì)算得到:

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

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

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

1.4 RODSR路由協(xié)議

為了定量評(píng)估該文所提出的穩(wěn)定路由選擇策略，對(duì)源動(dòng)態(tài)路由協(xié)議（Dynamic Source Routing Protocol，DSR）進(jìn)行了必要的擴(kuò)展，提出了一種基于逆向優(yōu)化的源動(dòng)態(tài)路由協(xié)議（Reverse Optimized Dynamic Source Routing Protocol，RODSR）。RODSR對(duì)DSR協(xié)議的路由建立過(guò)程進(jìn)行了部分改進(jìn)，其目的是驗(yàn)證局部拓?fù)渥兓囟攘繉?duì)路由協(xié)議性能的提升。

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

2 仿真實(shí)驗(yàn)及結(jié)果分析

2.1 仿真實(shí)驗(yàn)

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

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

2.2 仿真結(jié)果分析

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

圖1比較了DSR和RODSR協(xié)議的分組遞交成功率。從圖1（a）中可以看出，在節(jié)點(diǎn)移動(dòng)速度緩慢的網(wǎng)絡(luò)環(huán)境中，RODSR協(xié)議的分組遞交成功率提高并不明顯，這是因?yàn)橄鄬?duì)于節(jié)點(diǎn)的無(wú)線傳輸覆蓋范圍，節(jié)點(diǎn)移動(dòng)所導(dǎo)致的拓?fù)渥兓^緩慢，節(jié)點(diǎn)間拓?fù)渥兓牟淮_定程度差異較小。但是，隨著節(jié)點(diǎn)移動(dòng)速度的增加，節(jié)點(diǎn)間拓?fù)渥兓潭鹊牟町惣觿?，RODSR協(xié)議的性能有明顯提升。

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

圖1 分組遞交成功率性能對(duì)比

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

圖2 端到端延遲性能對(duì)比

3 結(jié)束語(yǔ)

基于局部拓?fù)浣Y(jié)構(gòu)變化的熵度量方法能夠?qū)植客負(fù)浣Y(jié)構(gòu)變化的不確定性程度給以定量的度量，適用于在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中選擇相對(duì)穩(wěn)定的路由。該方法提升了移動(dòng)自組網(wǎng)路由協(xié)議的性能，能夠有效降低網(wǎng)絡(luò)開(kāi)銷，提高有限網(wǎng)絡(luò)資源的利用效率，并延長(zhǎng)網(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]劉剛，郭建立，崔剛，等.移動(dòng)自組織網(wǎng)絡(luò)環(huán)境中負(fù)載均衡策略研究[J].無(wú)線電工程，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.