本文關鍵詞：移動Ad Hoc網(wǎng)絡通信量相關干擾感知路由協(xié)議，由筆耕文化傳播整理發(fā)布。

當前位置：首頁 >> 金融/投資 >> 移動Ad Hoc網(wǎng)絡通信量相關干擾感知路由協(xié)議

ISSN 1000-9825, CODEN RUXUEW Journal of Software, Vol.20, No.10, October 2009, pp.2721?2728 doi: 10.3724/SP.J.1001.2009.03502 ? by Institute of Software, the Chinese Academy of Sciences. All

rights reserved.

E-mail: jos@iscas.ac.cn Tel/Fax: +86-10-62562563

移動 Ad Hoc 網(wǎng)絡通信量相關干擾感知路由協(xié)議
張信明+, 劉 瓊, 代仕芳, 劉永振
(中國科學技術大學 計算機科學與技術學院,安徽 合肥 230027)

?

Traffic Load-Based Interference-Aware Routing Protocol for Mobile Ad Hoc Networks
ZHANG Xin-Ming+, LIU Qiong, DAI Shi-Fang, LIU Yong-Zhen

(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China)

+ Corresponding author: E-mail: xinming@ustc.edu.cn,

Zhang XM, Liu Q, Dai SF, Liu YZ. Traffic load-based interference-aware routing protocol for mobile ad hoc networks. Journal of Software, 2009,20(10):2721?2728. Abstract: The interference will greatly influence the performances of networks on its throughput, energy

consumption, and lifetime in mobile ad hoc networks (MANET). On the basis of the existing interference models founded on the number and distribution position of the neighbor nodes, the traffic load of neighbors is further considered and an interference model based on traffic load is proposed. Based on the new interference model, a traffic load-based interference-aware routing (TIR) protocol is proposed, which chooses the routing path with the minimal interference between the source node and the destination node to reduce the possible interference generated when a packet is being forwarded. The results of the simulations show that the proposed interference model based on traffic load suits the characteristic of the MANET, and the TIR protocol obviously improves the network’s lifetime, communication delay and throughput. Key words: 摘 要: interference; routing protocol; neighbor node; traffic load; mobile ad hoc network

干擾嚴重影響移動 Ad hoc 網(wǎng)絡的網(wǎng)絡吞吐量、能量消耗、網(wǎng)絡壽命等性能.在已有基于鄰居數(shù)目和分布

位置的干擾模型基礎上,進一步考慮各鄰居上的通信量情況,提出通信量干擾模型.并在該干擾模型的基礎上,提出 一個通信量相關干擾感知路由 TIR(traffic load-based interference-aware routing)協(xié)議.TIR 通過在源節(jié)點和目的節(jié)點 之間選擇干擾最小的路徑來降低數(shù)據(jù)包在轉發(fā)過程中可能受到的干擾.模擬實驗結果表明,所提出的通信量干擾模 型符合移動 Ad hoc 網(wǎng)絡的特性,通信量相關干擾感知路由協(xié)議對網(wǎng)絡壽命、通信延遲及吞吐量等網(wǎng)絡性能有明顯 改善. 關鍵詞: 干擾;路由協(xié)議;鄰居節(jié)點;通信量;移動 ad hoc 網(wǎng)絡 文獻標識碼: A 中圖法分類號: TP393

移動 Ad hoc(自組織)網(wǎng)絡是一種具有自組織能力的移動分布式多跳無線網(wǎng)絡.由于自組織所具有的特性, 無須基礎設施,易于部署,因而有著廣闊的應用前景,它在國家安全、環(huán)境監(jiān)測、交通管理、空間探索等領域具
?

Supported by the National Natural Science Foundation of China under Grant No.60673171 (國家自然科學基金); the National Basic Received 2008-07-17; Accepted 2008-10-27; Published online 2009-06-09

Research Program of China under Grant No.2006CB303006 (國家重點基礎研究發(fā)展計劃(973))

2722

Journal of Software 軟件學報 Vol.20, No.10, October 2009

有重大的應用價值,因而引起了軍界、工業(yè)界和學術界的高度關注. 自組織網(wǎng)絡使用共享的無線信道傳輸信息,因此它面臨著復雜的無線傳輸環(huán)境,這將引入一系列的新問題, 例如干擾.一般地,干擾就是不同信號源的信號經(jīng)過信道衰落后在同一接收機進行疊加,這將嚴重地影響接收機 區(qū)分有效信息的能力,導致沖突和重傳的增加,致使網(wǎng)絡的吞吐量下降,延遲增加,節(jié)點能量利用率急劇下降.干 擾嚴重影響網(wǎng)絡傳輸能力及性能,降低干擾可減少沖突和重傳,從而減少能量浪費,提高網(wǎng)絡吞吐量及壽命.因 此,迫切需要研究者們致力于干擾對移動 Ad hoc 網(wǎng)絡性能影響的研究,以減小干擾,提高通信質量,改善網(wǎng)絡的 各項性能;從而提高移動 Ad hoc 網(wǎng)絡的效率,提高其服務質量和健壯性,擴大移動 Ad hoc 網(wǎng)絡的應用范圍,使其 成為獨立且可靠的重要組網(wǎng)形式,成為現(xiàn)有網(wǎng)絡重要且不可或缺的補充. 干擾原來屬于 MAC(medium access control)層拓撲控制的研究范圍,但拓撲控制的目標是節(jié)省能量(隱式地 降低干擾).目前,MAC 層的拓撲控制尚不能考慮網(wǎng)絡流量,而網(wǎng)絡流量卻是干擾模型的基礎.本文首先提出通信 量干擾模型,給出節(jié)點干擾值、路徑干擾值以及平均鏈路干擾值的計算方式.然后在此基礎上,提出通信量相關 干擾感知路由協(xié)議,在源節(jié)點和目的節(jié)點之間選擇干擾最小的路徑對數(shù)據(jù)包進行轉發(fā). 本文第 1 節(jié)簡述干擾的相關工作.第 2 節(jié)詳細介紹通信量干擾模型.第 3 節(jié)闡述通信量相關干擾感知路由 協(xié)議.第 4 節(jié)通過模擬實驗驗證我們的通信量干擾模型及路由協(xié)議的有效性.第 5 節(jié)總結并展望下一步工作.

1

相關工作
一般來說,干擾問題的解決分干擾建模和干擾策略兩個步驟來完成.首要的問題是對移動 Ad hoc 網(wǎng)絡中的

干擾情況進行正確且有效的建模.只有建立完全符合移動 Ad hoc 網(wǎng)絡特性、能夠真實體現(xiàn)移動 Ad hoc 網(wǎng)絡干 擾狀況的干擾模型,才能有效地達到減小干擾的目的.對移動 Ad hoc 網(wǎng)絡的干擾進行建模的過程,就是根據(jù)移動 Ad hoc 網(wǎng)絡的特性給出干擾發(fā)生的原因以及對其如何進行量化的過程. 目前,學者們已提出了若干種干擾模型,一般分為物理模型和基于圖的干擾模型兩類.基于圖的干擾模型, 最典型的就是基于鄰居節(jié)點的干擾模型,另外還有一些是鄰居節(jié)點干擾模型的變種,如基于通信量的干擾模型. 物理模型,即在信號衰減模型基礎上建立的基于信噪比 SINR(signal-to-interference-plus-noise ratio)的干擾模型, 大多考慮信號功率. (1) 鄰居節(jié)點數(shù)模型 在各種干擾模型中,最著名的就是文獻[1]中提到的鄰居節(jié)點數(shù)模型.該模型認為,節(jié)點的所有鄰居都會對該 節(jié)點產(chǎn)生干擾,故而將兩個正在通信的節(jié)點的覆蓋范圍內的所有鄰居節(jié)點的數(shù)目定為這條鏈路的干擾值.或者 利用鄰居數(shù)直接定義某節(jié)點的干擾值. (2) 基于通信量的干擾模型 這類模型在認同鄰居節(jié)點干擾模型的同時,認為鄰居節(jié)點上不同的通信量,對該節(jié)點的干擾也不同.在建立 干擾模型時,于考慮鄰居節(jié)點的同時,也考慮各節(jié)點上的實際通信量情況.比如,文獻[2]定義節(jié)點的通信干擾為 所有鄰居的活躍度之和.其中,節(jié)點的活躍度是經(jīng)過該節(jié)點的路徑條數(shù).文獻[3]則將節(jié)點所有鄰居上的數(shù)據(jù)發(fā)送 率疊加起來得到了該節(jié)點的干擾值. (3) 基于信號功率的干擾模型 這類模型一般都針對特殊拓撲計算某個接收節(jié)點的信噪比.文獻[4]將發(fā)送節(jié)點置于一個六邊形的中心,接 收節(jié)點位于六邊形的頂點上,半徑為最大發(fā)送距離 R.一個六邊形外層的 6 個節(jié)點(相鄰的發(fā)送節(jié)點)是第 1 層干 擾節(jié)點,并且忽略其他節(jié)點對接收節(jié)點造成的干擾,然后計算該接收節(jié)點所受到的干擾大小及信噪比.也有直接 利用節(jié)點信噪比信息的,如文獻[5]通過在 CTS(clear to send)包中攜帶接收節(jié)點的信噪比信息,收到該包的節(jié)點 判斷此信噪比是否大于某個給定門限值,若是,則開始傳輸,否則,延遲.該方式能夠有效地控制網(wǎng)絡中的干擾. 建立干擾模型后,針對如何利用量化的干擾信息來抑制干擾對網(wǎng)絡性能的影響這一問題,研究者們也提出 了若干策略.目前,研究者們大多采用兩種方式來考慮解決干擾問題:一種是拓撲控制,另一種是功率控制.也有 少數(shù)在路由層對干擾問題進行思考.拓撲控制工作在 MAC 層,簡單地說,就是在所有鏈路組成的集合中以減小

張信明 等:移動 Ad Hoc 網(wǎng)絡通信量相關干擾感知路由協(xié)議

2723

干擾為目的,在保證網(wǎng)絡連通的前提下,根據(jù)一定的規(guī)則選擇出一部分合適鏈路,并利用這部分鏈路進行數(shù)據(jù)傳 輸.拓撲控制刪除了一些干擾較大的鏈路,網(wǎng)絡也變得較為稀疏,因而降低了干擾.典型的拓撲控制算法有文獻 [1,6,7].功率控制工作在物理層,為鏈路層提供服務.通過功率控制來減小干擾,包括調整發(fā)送功率、接收門限和 感知門限等,文獻[2,4,8,9]屬于這一類.例如,文獻[4]通過調整發(fā)送功率,在滿足一定信噪比的條件下盡量提高數(shù) 據(jù)發(fā)送率,進而增加整個網(wǎng)絡的吞吐量. 另外還有很多其他控制干擾的方式.文獻[2,10]通過在源和目的之間選擇干擾最小的路徑來避開干擾較大 的區(qū)域.文獻[11]基于信號功率的干擾模型,根據(jù)節(jié)點所受干擾的歷史信息,估算出節(jié)點在下一時刻可能受到的 干擾值大小,再結合節(jié)點可能受到的最大干擾值給出相應路由請求轉發(fā)概率.文獻[12]則給出了在源節(jié)點和目 的節(jié)點之間尋找一條不經(jīng)過其他任何節(jié)點干擾范圍的路徑的近似算法,但此算法比較復雜.而文獻[5]則在 CTS 包中攜帶接收節(jié)點的信噪比信息,收到該包的節(jié)點判斷此信噪比是否大于某個給定門限值,若是,則開始傳輸, 否則,延遲.改進后的 MAC 層協(xié)議能夠有效地控制網(wǎng)絡中的干擾.

2

通信量干擾模型
文獻[1,13]將干擾定義為節(jié)點通信范圍所覆蓋的鄰居數(shù)目,而文獻[10]則將實際的范圍擴展至節(jié)點的干擾

范圍,并將這些鄰居根據(jù)距離進行分類,以鄰居數(shù)的加權和作為干擾值.這些干擾模型的前提是假設節(jié)點周圍的 其他節(jié)點都是其潛在的干擾源.周圍的節(jié)點越多,其可能受到干擾的機會和程度就越大.但在某個時刻,并不是 處在節(jié)點干擾區(qū)域內的所有節(jié)點都會對該節(jié)點產(chǎn)生干擾,只有那些同時進行傳輸?shù)墓?jié)點才會在此刻對該節(jié)點 產(chǎn)生干擾.所以,單純以周圍節(jié)點的數(shù)目來定義節(jié)點所受的干擾并不十分精確,而應該同時考慮這些節(jié)點上的通 信量情況. 2.1 節(jié)點的通信量 為了建立基于通信量的干擾模型,首先要得到網(wǎng)絡中節(jié)點的通信量.由于網(wǎng)絡中各節(jié)點的通信量是動態(tài)分 布的,并且會隨著節(jié)點移動、網(wǎng)絡沖突、擁塞等情況而發(fā)生變化,所以節(jié)點通信量的精確統(tǒng)計并不容易.文獻[2] 給每個節(jié)點設置了活躍度,即經(jīng)過該節(jié)點的路徑條數(shù),并定義節(jié)點的通信干擾為所有鄰居的活躍度之和.文獻[3] 將所有經(jīng)過某鏈路的數(shù)據(jù)流發(fā)送率之和作為該鏈路的負載,并將干擾該鏈路的所有鏈路的負載之和作為該鏈 路的干擾值. 我們定義節(jié)點的通信量為節(jié)點的平均包發(fā)送率,即平均每秒鐘發(fā)送的包數(shù)目.在節(jié)點所發(fā)送的包中,既包括 數(shù)據(jù)包,也包括控制包,但是由于控制包一般較短,其引發(fā)沖突的概率較小,因此可以忽略不計. 為了精確地得到節(jié)點的通信量情況,各個節(jié)點從 MAC 層搜集通信量信息,并進行實時記錄.具體來說,就是 各節(jié)點每隔 1 秒累計 1 次已發(fā)送數(shù)據(jù)包的數(shù)目,這樣可以得到一系列的節(jié)點包發(fā)送率,記作 Tt(1),Tt(2),Tt(3),…, Tt(N). 然后,取最近 n 秒鐘的包發(fā)送率來求平均值,得到該節(jié)點的平均包發(fā)送率,見公式(1). Tt ( N ? n +1) + ... + Tt ( N ? 3) + Tt ( N ? 2) + Tt ( N ?1) + Tt ( N ) T= (1) n 其中 ,n 越大 ,平均包發(fā)送率就越能體現(xiàn)網(wǎng)絡中各節(jié)點上的通信量分布情況 .但由于節(jié)點上的通信量是動態(tài)變化 的,當 n 很大時,其平均包發(fā)送率反而不能很好地體現(xiàn)通信量的這種動態(tài)變化狀況;當 n 很小時,節(jié)點上的突發(fā)數(shù) 據(jù)對通信量的計算影響就會非常明顯 , 求得的通信量將發(fā)生明顯的震蕩 .各節(jié)點的通信量必須能夠反映節(jié)點上 通信情況的動態(tài)變化,也要能避免突發(fā)數(shù)據(jù)造成的通信量劇烈波動.因此,n 值不能太大,否則,不符合移動 Ad hoc 網(wǎng)絡的動態(tài)特點;n 值也不能太小,否則,通信量將很容易受到突發(fā)數(shù)據(jù)的影響. 2.2 節(jié)點的干擾值 當某節(jié)點進行發(fā)送時 ,其通信范圍內的其他節(jié)點不能同時進行發(fā)送 ,否則將引發(fā)沖突 .節(jié)點上的發(fā)送活動越 頻繁 ,其通信范圍內的其他節(jié)點發(fā)生沖突的可能性就越大 ,并且需要更大程度地延遲各自的發(fā)送 .節(jié)點的通信量 正好反映了節(jié)點發(fā)送活動的頻率 .同時 ,由于節(jié)點上的發(fā)送活動能夠被其通信范圍外感知范圍內的所有節(jié)點感 知到 ,并且會對干擾范圍內的接收節(jié)點產(chǎn)生干擾 [14],所以節(jié)點上的通信量也會對整個感知范圍內的節(jié)點產(chǎn)生影

2724

Journal of Software 軟件學報 Vol.20, No.10, October 2009

響 . 當節(jié)點上的通信量較大時 , 在其周圍將形成一個較強的干擾區(qū)域 , 嚴重影響鄰近節(jié)點的通信活動 , 且通信量 越大 , 其影響越大 . 因此 , 可以將節(jié)點的通信量視作其對周圍鄰近節(jié)點的干擾值 . 該值越大 , 說明其對其他節(jié)點的 潛在干擾也越大.顯然,一個節(jié)點所有鄰近節(jié)點的通信量之和就是該節(jié)點可能受到的總干擾值. 假設 Si 為節(jié)點 i 所有鄰近節(jié)點的集合,則節(jié)點 i 的干擾值 Ii 為
Ii =
a∈Si

∑ Ta

(2)

文獻 [10]指出 , 這些干擾源根據(jù)其與本地節(jié)點之間距離的大小產(chǎn)生不同程度的干擾 : 離得越近的節(jié)點 , 其上 的通信活動對該節(jié)點產(chǎn)生的干擾越大;反之,離得越遠,則干擾越小.為了更準確地對移動 Ad hoc 網(wǎng)絡干擾進行 建模 ,需要綜合考慮所有鄰近節(jié)點的位置分布情況 ,因此引入權值來體現(xiàn)不同距離的鄰近節(jié)點 ,其上的通信量對 本地節(jié)點所造成的干擾大小程度也各不相同. 路徑損耗公式如公式(3)所示,節(jié)點 i 平均每秒受到的來自節(jié)點 a 的干擾信號總功率如公式(4)所示:
Pr (d ) = Pt × Gt × Gr × (ht2 × hr2 ) dk × L 2 T × P × Ga × Gi × (ha × hi2 ) = a a k dia × L

(3)
(4)

Pi ( a )

其中,節(jié)點 a 到節(jié)點 i 的距離為 dia,節(jié)點 a 的通信量為 Ta,k 為指數(shù),一般 k∈[2,4].發(fā)送功率 Pa,發(fā)送節(jié)點和接收節(jié)
k 點的天線增益 Ga,Gi,天線高度 ha,hi 和系統(tǒng)損耗 L 均為定值.因此,可將 1/ dia 作為節(jié)點 a 通信量的權值,則由此可

得節(jié)點 i 的干擾值為

Ii =

a∈Si

∑ d ak

T

(5)

ia

由于通信范圍外節(jié)點的距離無法直接測得 , 我們給通信范圍外的所有節(jié)點一個固定的權值 . 如果在干擾區(qū) 域外有若干個節(jié)點同時進行發(fā)送 ,雖然這些信號不能單獨引起干擾 , 但是它們疊加起來也有可能會造成信噪比 低于門限值 ,從而淹沒有效信號 .因此 ,我們將干擾涉及的范圍擴大至兩倍通信半徑即 2×RT 范圍內 .通信范圍外

2×RT 范圍內的節(jié)點通信量權值,見公式(6):
1 2k ?2? 1 = =? ? ? k k k k ( RT + 2 RT ) / 2 (3RT ) ? 3 ? RT
k

(6)

綜上所述,我們可以得到節(jié)點 i 的加權干擾總值,見公式(7):
Ii = Ta T ?2? + ∑ ? 3 ? ? ( R b) k k a∈ST ( i ) d ia b∈( S 2 T ( i ) ? ST ( i ) ) ? ? T

∑

k

(7)

其中,ST(i)為節(jié)點 i 通信范圍內所有鄰居節(jié)點的集合,S2T(i)為節(jié)點兩倍通信半徑,即 2×RT 范圍內所有節(jié)點的集合. 網(wǎng)絡中節(jié)點干擾值是一種處于不斷動態(tài)變化過程中的網(wǎng)絡狀態(tài) ,獲得準確的實時值是非常困難的 , 并且過 于頻繁地變化也不利于網(wǎng)絡性能控制 .所以 ,利用節(jié)點干擾值的歷史信息 ,通過加權時序平均數(shù)的方式預測出下 一時刻的干擾值 ,作為控制網(wǎng)絡性能的依據(jù) .通信量是隨機分布的 ,并且會隨著網(wǎng)絡沖突、擁塞、節(jié)點的移動等 情況而發(fā)生動態(tài)的變化 , 加權時序平均數(shù)方法可以通過加大新歷史數(shù)據(jù)權重 ,讓干擾預測值能夠迅速、及時地 反映出通信量變化 .同時 ,網(wǎng)絡中也可能會出現(xiàn)突發(fā)通信量引起節(jié)點干擾值的急劇波動 ,加權時序平均數(shù)方法能 夠平緩突發(fā)通信量的影響. 假設節(jié)點 i 在 t(N)時刻的干擾值為 I it ( N ) ,之前 n 個時刻的干擾值分別為 I it ( N ? n +1) ,…, I it ( N ? 3) , I it ( N ? 2) , I it ( N ?1) ,即 可估算出下一時刻 t(N+1)的干擾值,如公式(8)所示:

I it ( N +1) = α I it ( N ) + β I it ( N ?1) + χ I it ( N ? 2) + δ I it ( N ? 3) + ... + ε I it ( N ? n +1)

(8)

其中 ,α,β,χ,δ,…,ε是各時刻干擾值的系數(shù) ,均為 [0,1]上的實數(shù) .其值越大 ,說明該時刻的干擾值對下一時刻的干擾 值影響越大;值越小,說明其影響越小.當某系數(shù)為 0 時,說明該時刻的干擾值對下一時刻干擾值沒有影 響.1≥α>β>χ>δ>…>ε≥0,且α+β+χ+δ+…+ε=1.

張信明 等:移動 Ad Hoc 網(wǎng)絡通信量相關干擾感知路由協(xié)議

2725

2.3 通信量干擾模型的實現(xiàn) 我們利用已有的 RTS(request to send)/CTS 控制包來實現(xiàn)通信量干擾模型.利用 RTS/CTS 除了開銷小、實 現(xiàn)方便以外 ,還使得節(jié)點不需要定期地向周圍節(jié)點廣播通信量信息 ,而只需在有發(fā)送活動時才廣播通信量信息 , 避免了不必要的信息重復交換 .同時也能及時地反映出通信量的動態(tài)變化 ,使周圍節(jié)點獲取最新、最及時的通 信量信息.具體過程如下:

(1) 在 RTS 包中,增加 T 和 TF 兩個字段.其中,T 用來存放需要交換的通信量信息,TF 為標志位,若該 RTS
包攜帶有通信量信息,則為 1,否則為 0.

(2) 為了提取通信量 ,節(jié)點在發(fā)送數(shù)據(jù)包時 ,在 MAC 層對其數(shù)目進行統(tǒng)計.每個節(jié)點都有一個計時器 ,時間
設置為 1s.當計時器計時時,節(jié)點累加數(shù)據(jù)包數(shù)目,當計時器超時時,即可得到最近 1s 內的數(shù)據(jù)包發(fā)送率.然后根 據(jù)公式(1)可以求得該節(jié)點的平均通信量 T. 當計時器處于計時狀態(tài)時 ,由于節(jié)點尚未統(tǒng)計出通信量值 ,不需要向周圍節(jié)點進行廣播 ,因此 ,將 RTS 包的

TF 位設置為 0.當鄰近節(jié)點第 1 次收到這個 TF 為 0 的 RTS 包時,采用原有的 RTS/CTS 機制,不做任何其他動作 .
當計時器處于超時狀態(tài)時,節(jié)點需要向周圍鄰近節(jié)點廣播新的平均通信量,將 TF 位設置為 1.同時將 RTS 包的 TTL 位設為 2,使得 RTS 可以傳輸兩跳,覆蓋了節(jié)點的兩倍通信范圍,從而使得兩倍通信范圍內的所有節(jié)點 都能收到攜帶了該節(jié)點通信量的 RTS 包,能夠獲知該節(jié)點上的通信量情況.

(3) 當節(jié)點第 1 次收到一個 RTS 包后,如果 TF 為 1,就提取該 RTS 包中的通信量信息.此時,該節(jié)點需要另
外一個計時器,來統(tǒng)計 1s 內所有鄰近節(jié)點上的通信量加權和,以得到該節(jié)點的干擾值. 具體來說,當節(jié)點第 1 次收到的 RTS 包的 TF 位為 1 時,如果此時該包的 TTL 為 1,說明該節(jié)點在發(fā)送 RTS 包的節(jié)點的通信范圍內.可以根據(jù) RTS 包的接收功率,依照公式(3)計算出這兩個節(jié)點間的距離 d.此時,該節(jié)點的 干擾值 I 累加 T/dk(其中,T 是 RTS 包中攜帶的通信量信息),并且按照原有 RTS/CTS 機制,抑制自身的通信活動. 如果節(jié)點第 1 次收到一個 RTS 包,TF 位為 1,且該包的 TTL 為 0,則說明這個節(jié)點在 RTS 發(fā)送節(jié)點的通信范

?2? T 圍以外.這時,將該節(jié)點的干擾值 I 增加 ? ? ? k .其中,T 是 RTS 包中攜帶的通信量信息.由于收到該 RTS 包的 ? 3 ? RT
節(jié)點已位于通信范圍之外,所以不必抑制自身的通信活動. 按照上述機制 ,我們得到了節(jié)點每秒鐘的即時干擾值 .然后根據(jù)歷史記錄 ,按照公式 (8)估算出下一時刻該節(jié) 點可能受到的干擾值大小.

k

3

通信量相關干擾感知路由協(xié)議
根據(jù)上述干擾模型的定義 , 我們得到了網(wǎng)絡中各個節(jié)點的干擾值 ,然后采用通信量相關干擾感知路由協(xié)議

來降低干擾.基于通信量的最小干擾路由協(xié)議,簡稱 TIR,選路機制與平均鏈路干擾感知路由協(xié)議 ALIR(average

link interference-aware routing) [10]類似.TIR 建立在 DSR(dynamic source routing)協(xié)議[15]基礎上,采用與 DSR 協(xié)議
相同的路由機制,可分為兩個部分:路由發(fā)現(xiàn)和路由維護.主要的區(qū)別體現(xiàn)在路由發(fā)現(xiàn)過程中.具體過程如下:

(1) 該協(xié)議在路由請求包和路由應答包中各自增加一個干擾值 I 字段,用來存放相關的干擾值.在各節(jié)點的
路由表中也增加一個干擾值 I 字段,用以存放與各路徑相關的干擾值信息.

(2) 在路由發(fā)現(xiàn)過程中,路由請求包在增加的干擾值 I 字段中記錄沿途各節(jié)點的干擾值.當路由請求包到達
目的節(jié)點時,即可對所有中間節(jié)點的干擾值求和得到該路徑的干擾值.假設網(wǎng)絡存在一條從節(jié)點 u0 到節(jié)點 un 的 多跳路徑 P(u0,un):u0u1u0u2…un?1un,則其路徑干擾值可表達為公式(9). I ( P) = I (u0 ) + I (u1 ) + I (u2 ) + ... + I (un ?1 ) + I (un )

(9)

然后結合該路徑的長度即跳數(shù) n,計算出路徑的平均干擾值 Metric,見公式(10). I ( P) Metric( P) = (10) n (3) 目的節(jié)點收到的每個路由請求包都代表一條從源節(jié)點到目的節(jié)點的可能路徑 ,并且可以從路由請求包

2726

Journal of Software 軟件學報 Vol.20, No.10, October 2009

的干擾值字段獲知每條路徑上的干擾值信息 .目的節(jié)點為每個路由請求包都生成一個路由應答包 ,將完整的路 經(jīng)信息及其平均鏈路干擾值返回給源節(jié)點.平均鏈路干擾值存放在路由應答包的干擾值 I 字段中.

(4) 源節(jié)點收到路由應答包后 , 即將路徑信息連同其對應的平均鏈路干擾值記錄在自己的路由表中 . 當源
節(jié)點需要發(fā)送數(shù)據(jù)包時 , 如果其路由表中已有到達目的節(jié)點的路徑 , 則在這些路徑中選擇平均鏈路干擾值最小 的一條進行數(shù)據(jù)轉發(fā).

(5) 為使路由協(xié)議能夠適應網(wǎng)絡拓撲及通信量分布的動態(tài)變化,具有自適應性,除了采用與 DSR 協(xié)議相同
的路由維護機制外 ,新協(xié)議每隔一段時間將所有節(jié)點的路由表清空 , 然后重新發(fā)起一次路由發(fā)現(xiàn)過程進行路由 更新.

4

模擬實驗
本節(jié)我們用模擬實驗來驗證通信量相關干擾感知路由協(xié)議 TIR 的性能,比較的對象是 DSR 路由協(xié)議和平

均鏈路干擾感知路由協(xié)議 ALIR[10],使用的模擬實驗環(huán)境是 ns-2 模擬器[16]. 模擬環(huán)境和參數(shù):所有節(jié)點隨機分布在 1000m×1000m 的區(qū)域內;節(jié)點數(shù)為 49;CBR(constant bit rate)數(shù)據(jù)流 隨機生成 ,即每條 CBR 的源節(jié)點和目的節(jié)點隨機選擇 ,并分別考慮了變化數(shù)量和固定數(shù)量的情況 .數(shù)據(jù)包大小 為 512 字節(jié),并分別考慮了固定速率和變化速率的情況;節(jié)點傳輸半徑為 150m;節(jié)點感知范圍為 300m;初始能量 為 100;模擬時間為 300s;對于節(jié)點的移動性,采用普遍使用的 RWP(random waypoint model)模型,節(jié)點的初始位 置是隨機生成的,節(jié)點最小速度為 0m/s,最大速度為 20m/s;MAC 層協(xié)議為 802.11 協(xié)議 (RTS/CTS 機制根據(jù)第 2.3 節(jié)作了修改);路由層協(xié)議為 DSR 協(xié)議基礎上改進而來的 TIR 協(xié)議.另外,在模擬過程中,在計算節(jié)點平均通信量 時,取最近 5 個連續(xù)時刻的通信量求平均值;在計算節(jié)點干擾值時,取最近 3 個時刻的干擾值用以估算下一時刻 節(jié)點的干擾值信息,且α=0.5,β=0.3,χ=0.2. 首先在網(wǎng)絡中隨機分布 49 個節(jié)點,每條 CBR 數(shù)據(jù)流每秒鐘發(fā)送 120 個數(shù)據(jù)包.圖 1~圖 3 分別是不同 CBR 數(shù)據(jù)流總數(shù)情況下的丟包率、平均延遲和網(wǎng)絡吞吐量.然后,固定 CBR 數(shù)據(jù)流的總數(shù)為 12 條,考察不同數(shù)據(jù)發(fā) 送率情況下的網(wǎng)絡性能.圖 4~圖 6 分別是不同數(shù)據(jù)發(fā)送率情況下的網(wǎng)絡壽命、平均延遲和網(wǎng)絡吞吐量. 由圖 1 可以看出,當節(jié)點數(shù)不變時,在不同的負載下,TIR 協(xié)議的丟包率比 DSR 協(xié)議的丟包率降低 16.26%, 并且也低于 ALIR 協(xié)議.從圖 2 和圖 5 可以看出,雖然某些情況下 TIR 的平均延遲不如 DSR 協(xié)議,但總體而言,TIR 協(xié)議的平均延遲要低于 DSR 協(xié)議.圖 2 中,TIR 協(xié)議的平均延遲比 DSR 協(xié)議的要小 63.61%.TIR 在延遲方面對

DSR 協(xié)議的改進不明顯,然而它卻獲得了很好的網(wǎng)絡吞吐量,并且大大優(yōu)于 DSR 協(xié)議.從圖 3 可知,在不同 CBR
數(shù)據(jù)流情況下,TIR 協(xié)議的吞吐量比 DSR 協(xié)議的吞吐量增加竟高達 84.17%.由圖 6 可得,在不同數(shù)據(jù)發(fā)送率的情 況下,TIR 協(xié)議的吞吐量比 DSR 協(xié)議的吞吐量增加 79.22%.由圖 4 可以看出,TIR 協(xié)議的網(wǎng)絡壽命比 DSR 協(xié)議 的網(wǎng)絡壽命平均延長 7.884s.
1.00 0.95 0.90 0.85 0.80 0.75 0.70 0.65 0.60 0.55 0.50 10 9 8 7 6 5 4 3 2 1 0 4 6 8 10 12 14 16 DSR ALIR TIR

DSR ALIR TIR 4 6 8 10 12 14 16 18 20

Average delay (s)

Loss rate (%)

18

20

Number of CBR connections

Number of CBR connections

Fig.1

Packet loss under different CBR connection numbers 圖 1 不同 CBR 條數(shù)時的丟包率

Fig.2

Average delay under different CBR connection numbers 圖 2 不同 CBR 條數(shù)時的平均延遲

張信明 等:移動 Ad Hoc 網(wǎng)絡通信量相關干擾感知路由協(xié)議

2727

12000 Network end-to-end throughput 10000 8000 6000 4000 2000 0 4 6

Network lifetime (s)

DSR ALIR TIR

300 295 290 285 280 275 270 200 400 600 DSR ALIR TIR 800

8

10

12

14

16

18

20

Number of CBR connections

CBR rate (Kb/s)

Fig.3
圖3
5.0 4.5 4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5 0.0

Throughput under different CBR connection numbers
不同 CBR 條數(shù)時的吞吐量
DSR ALIR TIR

Fig.4
圖4

Network lifetime under different CBR connection numbers
不同數(shù)據(jù)發(fā)送率時的網(wǎng)絡壽命
12000

Network end-to-end throughput

Average delay (s)

10000 8000 6000 4000 2000 0 200 400 600 DSR ALIR TIR 800

200

400

600

800

CBR rate (Kb/s)

CBR rate (Kb/s)

Fig.5

Average delay under different CBR rates
不同數(shù)據(jù)發(fā)送率時的平均延遲

Fig.6

Throughput under different CBR rates
不同數(shù)據(jù)發(fā)送率時的吞吐量

圖5

圖6

5

結束語
本文提出的通信量干擾模型不但考慮了節(jié)點的鄰居數(shù)目和鄰居的分布位置 , 而且考慮了各鄰居上的通信

量情況 . 鄰居節(jié)點上的通信活動越頻繁 , 發(fā)生碰撞沖突的概率就越大 , 對節(jié)點產(chǎn)生的干擾程度也就越大 . 采用

RTS/ CTS 機制實現(xiàn)了通信量干擾模型.利用已有的 RTS 包,除了開銷小、 實現(xiàn)方便以外,還使得節(jié)點不需要定期
地向周圍節(jié)點廣播通信量信息 ,而只需在有發(fā)送活動時才進行廣播 ,避免了不必要的信息重復交換 .同時也能及 時地反映出通信量的動態(tài)變化 ,使周圍節(jié)點獲取最新、最及時的通信量信息 .干擾源與接收節(jié)點之間距離的遠 近不同也會造成干擾程度的不同,我們利用 RTS/CTS 機制來測量各鄰居節(jié)點的距離,并以此作為因子為各節(jié)點 設置權值. 本文提出的通信量相關的干擾感知路由協(xié)議 ,在路由發(fā)現(xiàn)過程中搜集沿途所有中間節(jié)點的干擾值 , 當?shù)竭_ 目的節(jié)點時 ,即可累加求和得到路徑干擾值 ,并進一步求得平均鏈路干擾值 .每一個可能路徑都向源節(jié)點返回一 個攜帶有干擾信息的路由應答包 .源節(jié)點就按照收到的路由應答包所攜帶的干擾信息 ,為數(shù)據(jù)包選擇平均鏈路 干擾值最小的那條路徑,進行逐跳轉發(fā).大量模擬實驗數(shù)據(jù)表明,通信量干擾模型及其路由協(xié)議對移動 Ad hoc 網(wǎng) 絡的各項性能都有一定的改善. 目前的移動 Ad hoc 網(wǎng)絡信道接入?yún)f(xié)議大多是基于單信道的,其對干擾問題的解決有限.我們的干擾模型也 是在單信道基礎上提出來的 ,因而也存在一定的局限性 ,下一步可以考慮在多信道接入?yún)f(xié)議基礎上來解決干擾 問題 .另外 ,本文所采用的信號衰減模型是最簡單、最理想的自由空間傳播模型 ,而實際的信號衰減情況可能要 復雜得多 ,所以更進一步的實際應用研究應該針對較為復雜的信號傳播模型來進行 .最后 ,我們的所有方案都是 在 ns-2 模擬器下實現(xiàn)的.該模擬器雖然功能十分強大,但與實際情況還是有些偏差.所以,為了設計出更為精確、 更能反映移動 Ad hoc 網(wǎng)絡特性的干擾模型和路由協(xié)議,需要在本文工作的基礎上采用另一種技術路線,即搭建

2728

Journal of Software 軟件學報 Vol.20, No.10, October 2009

測試床來驗證有關模型和協(xié)議. References:
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] Burkhart M, Rickenbach P, Wattenhofer R, Zollinger A. Does topology control reduce interference? In: Proc. of the ACM MobiHoc. 2004. ?id=989462 Hassanein H, Zhou A. Load-Aware destination-controlled routing for MANETs. Computer Communications, 2003,26(14): 1551?1559. Tang J, Xue G, Chandler C, Zhang W. Interference-Aware routing in multihop wireless networks using directional antennas. In: Proc. of the IEEE INFOCOM. 2005. ?tp=&arnumber=1497940 Kim TS, Lim H, Hou JC. Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in multihop wireless networks. In: Proc. of the ACM MobiCom. 2006. 366?377. ?id=1161089.1161131 Maniezzo D, Cesana M, Gerla M. IA-MAC: Interference aware MAC for WLANs. Technical Report, 020037, UCLA Computer Science Department, 2002. Johansson T, Carr-Motyckova L. Reducing interference in ad hoc networks through topology control. In: Proc. of the ACM/ SIGMOBILE Workshop on Foundations of Mobile Computing. 2005. ?id=1080810.1080815 Moaveni-Nejad K, Li X. Low-Interference topology control for wireless ad hoc networks. Ad Hoc & Sensor Wireless Networks, 2005,1(1-2):41?64. Tan H, Seah W. Dynamic topology control to reduce interference in MANETs. In: Proc. of the 2nd Int’l Conf. on Mobile Computing and Ubiquitous Networking. 2005. Krunz M, Muqattash A, Lee S. Transmission power control in wireless ad hoc networks: Challenges, solutions, and open issues. IEEE Network, 2004,18(5):8?14. Zhang XM, Liu Q, Shi D, Liu YZ, Yu X. An average link interference-aware routing protocol for mobile ad hoc networks. In: Proc. of the 3rd Int’l Conf. on Wireless and Mobile Communications (ICWMC). 2007. ?id=1261451 Liu Q, Zhang XM, Liu YZ, Shi D, Wang EB. Interference-Aware probability forwarding mechanism for mobile ad hoc networks. In: Proc. of the 4th Int’l Conf. on Networked Computing and Advanced Information Management (NCM). 2008. acm.org/citation.cfm?id=1445118 [12] [13] [14] [15] [16] Kapadia PR, Damani OP. Interference-Constrained wireless coverage in a protocol model. In: Proc. of the MSWiM. 2006. 207?211. ?id=1164717.1164754 Blough DM, Leoncini M, Resta G, Santi P. The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks. IEEE Trans. on Mobile Computing, 2006,5(9):1267?1282. Yang Y, Hou JC, Kung LC. Modeling the effect of transmit power and physical carrier sense in multi-hop wireless networks. In: Proc. of the IEEE INFOCOM. 2007. ?arnumber=04215857 Johnson D, Hu Y, Maltz D. The dynamic source routing protocol for mobile ad hoc networks (DSR) for IPv4. IETF RFC 4728, 2007. NS-2 home page.

張信明(1964－),男,安徽天 長人,博士,副 教授,CCF 高級會員,主要研究領域為無線 網(wǎng)絡,IP 網(wǎng)絡 QoS 控制,網(wǎng)絡性能分析.

代仕芳(1984－),女,碩博連讀生,主要研究 領域為無線網(wǎng)絡.

劉瓊(1982－),女,碩士,主要研究領域為無 線網(wǎng)絡.

劉永振(1983－),男,碩士生,主要研究領域 為無線網(wǎng)絡.



  本文關鍵詞：移動Ad Hoc網(wǎng)絡通信量相關干擾感知路由協(xié)議，，由筆耕文化傳播整理發(fā)布。