移動Ad Hoc網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(xié)議
本文關(guān)鍵詞:移動Ad Hoc網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(xié)議,由筆耕文化傳播整理發(fā)布。
當(dāng)前位置:首頁 >> 金融/投資 >> 移動Ad Hoc網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(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)絡(luò)通信量相關(guān)干擾感知路由協(xié)議
張信明+, 劉 瓊, 代仕芳, 劉永振
(中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 合肥 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
干擾嚴(yán)重影響移動 Ad hoc 網(wǎng)絡(luò)的網(wǎng)絡(luò)吞吐量、能量消耗、網(wǎng)絡(luò)壽命等性能.在已有基于鄰居數(shù)目和分布
位置的干擾模型基礎(chǔ)上,進(jìn)一步考慮各鄰居上的通信量情況,提出通信量干擾模型.并在該干擾模型的基礎(chǔ)上,提出 一個通信量相關(guān)干擾感知路由 TIR(traffic load-based interference-aware routing)協(xié)議.TIR 通過在源節(jié)點(diǎn)和目的節(jié)點(diǎn) 之間選擇干擾最小的路徑來降低數(shù)據(jù)包在轉(zhuǎn)發(fā)過程中可能受到的干擾.模擬實(shí)驗(yàn)結(jié)果表明,所提出的通信量干擾模 型符合移動 Ad hoc 網(wǎng)絡(luò)的特性,通信量相關(guān)干擾感知路由協(xié)議對網(wǎng)絡(luò)壽命、通信延遲及吞吐量等網(wǎng)絡(luò)性能有明顯 改善. 關(guān)鍵詞: 干擾;路由協(xié)議;鄰居節(jié)點(diǎn);通信量;移動 ad hoc 網(wǎng)絡(luò) 文獻(xiàn)標(biāo)識碼: A 中圖法分類號: TP393
移動 Ad hoc(自組織)網(wǎng)絡(luò)是一種具有自組織能力的移動分布式多跳無線網(wǎng)絡(luò).由于自組織所具有的特性, 無須基礎(chǔ)設(shè)施,易于部署,因而有著廣闊的應(yīng)用前景,它在國家安全、環(huán)境監(jiān)測、交通管理、空間探索等領(lǐng)域具
?
Supported by the National Natural Science Foundation of China under Grant No.60673171 (國家自然科學(xué)基金); the National Basic Received 2008-07-17; Accepted 2008-10-27; Published online 2009-06-09
Research Program of China under Grant No.2006CB303006 (國家重點(diǎn)基礎(chǔ)研究發(fā)展計劃(973))
2722
Journal of Software 軟件學(xué)報 Vol.20, No.10, October 2009
有重大的應(yīng)用價值,因而引起了軍界、工業(yè)界和學(xué)術(shù)界的高度關(guān)注. 自組織網(wǎng)絡(luò)使用共享的無線信道傳輸信息,因此它面臨著復(fù)雜的無線傳輸環(huán)境,這將引入一系列的新問題, 例如干擾.一般地,干擾就是不同信號源的信號經(jīng)過信道衰落后在同一接收機(jī)進(jìn)行疊加,這將嚴(yán)重地影響接收機(jī) 區(qū)分有效信息的能力,導(dǎo)致沖突和重傳的增加,致使網(wǎng)絡(luò)的吞吐量下降,延遲增加,節(jié)點(diǎn)能量利用率急劇下降.干 擾嚴(yán)重影響網(wǎng)絡(luò)傳輸能力及性能,降低干擾可減少沖突和重傳,從而減少能量浪費(fèi),提高網(wǎng)絡(luò)吞吐量及壽命.因 此,迫切需要研究者們致力于干擾對移動 Ad hoc 網(wǎng)絡(luò)性能影響的研究,以減小干擾,提高通信質(zhì)量,改善網(wǎng)絡(luò)的 各項(xiàng)性能;從而提高移動 Ad hoc 網(wǎng)絡(luò)的效率,提高其服務(wù)質(zhì)量和健壯性,擴(kuò)大移動 Ad hoc 網(wǎng)絡(luò)的應(yīng)用范圍,使其 成為獨(dú)立且可靠的重要組網(wǎng)形式,成為現(xiàn)有網(wǎng)絡(luò)重要且不可或缺的補(bǔ)充. 干擾原來屬于 MAC(medium access control)層拓?fù)淇刂频难芯糠秶?但拓?fù)淇刂频哪繕?biāo)是節(jié)省能量(隱式地 降低干擾).目前,MAC 層的拓?fù)淇刂粕胁荒芸紤]網(wǎng)絡(luò)流量,而網(wǎng)絡(luò)流量卻是干擾模型的基礎(chǔ).本文首先提出通信 量干擾模型,給出節(jié)點(diǎn)干擾值、路徑干擾值以及平均鏈路干擾值的計算方式.然后在此基礎(chǔ)上,提出通信量相關(guān) 干擾感知路由協(xié)議,在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間選擇干擾最小的路徑對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā). 本文第 1 節(jié)簡述干擾的相關(guān)工作.第 2 節(jié)詳細(xì)介紹通信量干擾模型.第 3 節(jié)闡述通信量相關(guān)干擾感知路由 協(xié)議.第 4 節(jié)通過模擬實(shí)驗(yàn)驗(yàn)證我們的通信量干擾模型及路由協(xié)議的有效性.第 5 節(jié)總結(jié)并展望下一步工作.
1
相關(guān)工作
一般來說,干擾問題的解決分干擾建模和干擾策略兩個步驟來完成.首要的問題是對移動 Ad hoc 網(wǎng)絡(luò)中的
干擾情況進(jìn)行正確且有效的建模.只有建立完全符合移動 Ad hoc 網(wǎng)絡(luò)特性、能夠真實(shí)體現(xiàn)移動 Ad hoc 網(wǎng)絡(luò)干 擾狀況的干擾模型,才能有效地達(dá)到減小干擾的目的.對移動 Ad hoc 網(wǎng)絡(luò)的干擾進(jìn)行建模的過程,就是根據(jù)移動 Ad hoc 網(wǎng)絡(luò)的特性給出干擾發(fā)生的原因以及對其如何進(jìn)行量化的過程. 目前,學(xué)者們已提出了若干種干擾模型,一般分為物理模型和基于圖的干擾模型兩類.基于圖的干擾模型, 最典型的就是基于鄰居節(jié)點(diǎn)的干擾模型,另外還有一些是鄰居節(jié)點(diǎn)干擾模型的變種,如基于通信量的干擾模型. 物理模型,即在信號衰減模型基礎(chǔ)上建立的基于信噪比 SINR(signal-to-interference-plus-noise ratio)的干擾模型, 大多考慮信號功率. (1) 鄰居節(jié)點(diǎn)數(shù)模型 在各種干擾模型中,最著名的就是文獻(xiàn)[1]中提到的鄰居節(jié)點(diǎn)數(shù)模型.該模型認(rèn)為,節(jié)點(diǎn)的所有鄰居都會對該 節(jié)點(diǎn)產(chǎn)生干擾,故而將兩個正在通信的節(jié)點(diǎn)的覆蓋范圍內(nèi)的所有鄰居節(jié)點(diǎn)的數(shù)目定為這條鏈路的干擾值.或者 利用鄰居數(shù)直接定義某節(jié)點(diǎn)的干擾值. (2) 基于通信量的干擾模型 這類模型在認(rèn)同鄰居節(jié)點(diǎn)干擾模型的同時,認(rèn)為鄰居節(jié)點(diǎn)上不同的通信量,對該節(jié)點(diǎn)的干擾也不同.在建立 干擾模型時,于考慮鄰居節(jié)點(diǎn)的同時,也考慮各節(jié)點(diǎn)上的實(shí)際通信量情況.比如,文獻(xiàn)[2]定義節(jié)點(diǎn)的通信干擾為 所有鄰居的活躍度之和.其中,節(jié)點(diǎn)的活躍度是經(jīng)過該節(jié)點(diǎn)的路徑條數(shù).文獻(xiàn)[3]則將節(jié)點(diǎn)所有鄰居上的數(shù)據(jù)發(fā)送 率疊加起來得到了該節(jié)點(diǎn)的干擾值. (3) 基于信號功率的干擾模型 這類模型一般都針對特殊拓?fù)溆嬎隳硞接收節(jié)點(diǎn)的信噪比.文獻(xiàn)[4]將發(fā)送節(jié)點(diǎn)置于一個六邊形的中心,接 收節(jié)點(diǎn)位于六邊形的頂點(diǎn)上,半徑為最大發(fā)送距離 R.一個六邊形外層的 6 個節(jié)點(diǎn)(相鄰的發(fā)送節(jié)點(diǎn))是第 1 層干 擾節(jié)點(diǎn),并且忽略其他節(jié)點(diǎn)對接收節(jié)點(diǎn)造成的干擾,然后計算該接收節(jié)點(diǎn)所受到的干擾大小及信噪比.也有直接 利用節(jié)點(diǎn)信噪比信息的,如文獻(xiàn)[5]通過在 CTS(clear to send)包中攜帶接收節(jié)點(diǎn)的信噪比信息,收到該包的節(jié)點(diǎn) 判斷此信噪比是否大于某個給定門限值,若是,則開始傳輸,否則,延遲.該方式能夠有效地控制網(wǎng)絡(luò)中的干擾. 建立干擾模型后,針對如何利用量化的干擾信息來抑制干擾對網(wǎng)絡(luò)性能的影響這一問題,研究者們也提出 了若干策略.目前,研究者們大多采用兩種方式來考慮解決干擾問題:一種是拓?fù)淇刂?另一種是功率控制.也有 少數(shù)在路由層對干擾問題進(jìn)行思考.拓?fù)淇刂乒ぷ髟?MAC 層,簡單地說,就是在所有鏈路組成的集合中以減小
張信明 等:移動 Ad Hoc 網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(xié)議
2723
干擾為目的,在保證網(wǎng)絡(luò)連通的前提下,根據(jù)一定的規(guī)則選擇出一部分合適鏈路,并利用這部分鏈路進(jìn)行數(shù)據(jù)傳 輸.拓?fù)淇刂苿h除了一些干擾較大的鏈路,網(wǎng)絡(luò)也變得較為稀疏,因而降低了干擾.典型的拓?fù)淇刂扑惴ㄓ形墨I(xiàn) [1,6,7].功率控制工作在物理層,為鏈路層提供服務(wù).通過功率控制來減小干擾,包括調(diào)整發(fā)送功率、接收門限和 感知門限等,文獻(xiàn)[2,4,8,9]屬于這一類.例如,文獻(xiàn)[4]通過調(diào)整發(fā)送功率,在滿足一定信噪比的條件下盡量提高數(shù) 據(jù)發(fā)送率,進(jìn)而增加整個網(wǎng)絡(luò)的吞吐量. 另外還有很多其他控制干擾的方式.文獻(xiàn)[2,10]通過在源和目的之間選擇干擾最小的路徑來避開干擾較大 的區(qū)域.文獻(xiàn)[11]基于信號功率的干擾模型,根據(jù)節(jié)點(diǎn)所受干擾的歷史信息,估算出節(jié)點(diǎn)在下一時刻可能受到的 干擾值大小,再結(jié)合節(jié)點(diǎn)可能受到的最大干擾值給出相應(yīng)路由請求轉(zhuǎn)發(fā)概率.文獻(xiàn)[12]則給出了在源節(jié)點(diǎn)和目 的節(jié)點(diǎn)之間尋找一條不經(jīng)過其他任何節(jié)點(diǎn)干擾范圍的路徑的近似算法,但此算法比較復(fù)雜.而文獻(xiàn)[5]則在 CTS 包中攜帶接收節(jié)點(diǎn)的信噪比信息,收到該包的節(jié)點(diǎn)判斷此信噪比是否大于某個給定門限值,若是,則開始傳輸, 否則,延遲.改進(jìn)后的 MAC 層協(xié)議能夠有效地控制網(wǎng)絡(luò)中的干擾.
2
通信量干擾模型
文獻(xiàn)[1,13]將干擾定義為節(jié)點(diǎn)通信范圍所覆蓋的鄰居數(shù)目,而文獻(xiàn)[10]則將實(shí)際的范圍擴(kuò)展至節(jié)點(diǎn)的干擾
范圍,并將這些鄰居根據(jù)距離進(jìn)行分類,以鄰居數(shù)的加權(quán)和作為干擾值.這些干擾模型的前提是假設(shè)節(jié)點(diǎn)周圍的 其他節(jié)點(diǎn)都是其潛在的干擾源.周圍的節(jié)點(diǎn)越多,其可能受到干擾的機(jī)會和程度就越大.但在某個時刻,并不是 處在節(jié)點(diǎn)干擾區(qū)域內(nèi)的所有節(jié)點(diǎn)都會對該節(jié)點(diǎn)產(chǎn)生干擾,只有那些同時進(jìn)行傳輸?shù)墓?jié)點(diǎn)才會在此刻對該節(jié)點(diǎn) 產(chǎn)生干擾.所以,單純以周圍節(jié)點(diǎn)的數(shù)目來定義節(jié)點(diǎn)所受的干擾并不十分精確,而應(yīng)該同時考慮這些節(jié)點(diǎn)上的通 信量情況. 2.1 節(jié)點(diǎn)的通信量 為了建立基于通信量的干擾模型,首先要得到網(wǎng)絡(luò)中節(jié)點(diǎn)的通信量.由于網(wǎng)絡(luò)中各節(jié)點(diǎn)的通信量是動態(tài)分 布的,并且會隨著節(jié)點(diǎn)移動、網(wǎng)絡(luò)沖突、擁塞等情況而發(fā)生變化,所以節(jié)點(diǎn)通信量的精確統(tǒng)計并不容易.文獻(xiàn)[2] 給每個節(jié)點(diǎn)設(shè)置了活躍度,即經(jīng)過該節(jié)點(diǎn)的路徑條數(shù),并定義節(jié)點(diǎn)的通信干擾為所有鄰居的活躍度之和.文獻(xiàn)[3] 將所有經(jīng)過某鏈路的數(shù)據(jù)流發(fā)送率之和作為該鏈路的負(fù)載,并將干擾該鏈路的所有鏈路的負(fù)載之和作為該鏈 路的干擾值. 我們定義節(jié)點(diǎn)的通信量為節(jié)點(diǎn)的平均包發(fā)送率,即平均每秒鐘發(fā)送的包數(shù)目.在節(jié)點(diǎn)所發(fā)送的包中,既包括 數(shù)據(jù)包,也包括控制包,但是由于控制包一般較短,其引發(fā)沖突的概率較小,因此可以忽略不計. 為了精確地得到節(jié)點(diǎn)的通信量情況,各個節(jié)點(diǎn)從 MAC 層搜集通信量信息,并進(jìn)行實(shí)時記錄.具體來說,就是 各節(jié)點(diǎn)每隔 1 秒累計 1 次已發(fā)送數(shù)據(jù)包的數(shù)目,這樣可以得到一系列的節(jié)點(diǎn)包發(fā)送率,記作 Tt(1),Tt(2),Tt(3),…, Tt(N). 然后,取最近 n 秒鐘的包發(fā)送率來求平均值,得到該節(jié)點(diǎn)的平均包發(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)絡(luò)中各節(jié)點(diǎn)上的通信量分布情況 .但由于節(jié)點(diǎn)上的通信量是動態(tài)變化 的,當(dāng) n 很大時,其平均包發(fā)送率反而不能很好地體現(xiàn)通信量的這種動態(tài)變化狀況;當(dāng) n 很小時,節(jié)點(diǎn)上的突發(fā)數(shù) 據(jù)對通信量的計算影響就會非常明顯 , 求得的通信量將發(fā)生明顯的震蕩 .各節(jié)點(diǎn)的通信量必須能夠反映節(jié)點(diǎn)上 通信情況的動態(tài)變化,也要能避免突發(fā)數(shù)據(jù)造成的通信量劇烈波動.因此,n 值不能太大,否則,不符合移動 Ad hoc 網(wǎng)絡(luò)的動態(tài)特點(diǎn);n 值也不能太小,否則,通信量將很容易受到突發(fā)數(shù)據(jù)的影響. 2.2 節(jié)點(diǎn)的干擾值 當(dāng)某節(jié)點(diǎn)進(jìn)行發(fā)送時 ,其通信范圍內(nèi)的其他節(jié)點(diǎn)不能同時進(jìn)行發(fā)送 ,否則將引發(fā)沖突 .節(jié)點(diǎn)上的發(fā)送活動越 頻繁 ,其通信范圍內(nèi)的其他節(jié)點(diǎn)發(fā)生沖突的可能性就越大 ,并且需要更大程度地延遲各自的發(fā)送 .節(jié)點(diǎn)的通信量 正好反映了節(jié)點(diǎn)發(fā)送活動的頻率 .同時 ,由于節(jié)點(diǎn)上的發(fā)送活動能夠被其通信范圍外感知范圍內(nèi)的所有節(jié)點(diǎn)感 知到 ,并且會對干擾范圍內(nèi)的接收節(jié)點(diǎn)產(chǎn)生干擾 [14],所以節(jié)點(diǎn)上的通信量也會對整個感知范圍內(nèi)的節(jié)點(diǎn)產(chǎn)生影
2724
Journal of Software 軟件學(xué)報 Vol.20, No.10, October 2009
響 . 當(dāng)節(jié)點(diǎn)上的通信量較大時 , 在其周圍將形成一個較強(qiáng)的干擾區(qū)域 , 嚴(yán)重影響鄰近節(jié)點(diǎn)的通信活動 , 且通信量 越大 , 其影響越大 . 因此 , 可以將節(jié)點(diǎn)的通信量視作其對周圍鄰近節(jié)點(diǎn)的干擾值 . 該值越大 , 說明其對其他節(jié)點(diǎn)的 潛在干擾也越大.顯然,一個節(jié)點(diǎn)所有鄰近節(jié)點(diǎn)的通信量之和就是該節(jié)點(diǎn)可能受到的總干擾值. 假設(shè) Si 為節(jié)點(diǎn) i 所有鄰近節(jié)點(diǎn)的集合,則節(jié)點(diǎn) i 的干擾值 Ii 為
Ii =
a∈Si
∑ Ta
(2)
文獻(xiàn) [10]指出 , 這些干擾源根據(jù)其與本地節(jié)點(diǎn)之間距離的大小產(chǎn)生不同程度的干擾 : 離得越近的節(jié)點(diǎn) , 其上 的通信活動對該節(jié)點(diǎn)產(chǎn)生的干擾越大;反之,離得越遠(yuǎn),則干擾越小.為了更準(zhǔn)確地對移動 Ad hoc 網(wǎng)絡(luò)干擾進(jìn)行 建模 ,需要綜合考慮所有鄰近節(jié)點(diǎn)的位置分布情況 ,因此引入權(quán)值來體現(xiàn)不同距離的鄰近節(jié)點(diǎn) ,其上的通信量對 本地節(jié)點(diǎn)所造成的干擾大小程度也各不相同. 路徑損耗公式如公式(3)所示,節(jié)點(diǎn) i 平均每秒受到的來自節(jié)點(diǎn) 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é)點(diǎn) a 到節(jié)點(diǎn) i 的距離為 dia,節(jié)點(diǎn) a 的通信量為 Ta,k 為指數(shù),一般 k∈[2,4].發(fā)送功率 Pa,發(fā)送節(jié)點(diǎn)和接收節(jié)
k 點(diǎn)的天線增益 Ga,Gi,天線高度 ha,hi 和系統(tǒng)損耗 L 均為定值.因此,可將 1/ dia 作為節(jié)點(diǎn) a 通信量的權(quán)值,則由此可
得節(jié)點(diǎn) i 的干擾值為
Ii =
a∈Si
∑ d ak
T
(5)
ia
由于通信范圍外節(jié)點(diǎn)的距離無法直接測得 , 我們給通信范圍外的所有節(jié)點(diǎn)一個固定的權(quán)值 . 如果在干擾區(qū) 域外有若干個節(jié)點(diǎn)同時進(jìn)行發(fā)送 ,雖然這些信號不能單獨(dú)引起干擾 , 但是它們疊加起來也有可能會造成信噪比 低于門限值 ,從而淹沒有效信號 .因此 ,我們將干擾涉及的范圍擴(kuò)大至兩倍通信半徑即 2×RT 范圍內(nèi) .通信范圍外
2×RT 范圍內(nèi)的節(jié)點(diǎn)通信量權(quán)值,見公式(6):
1 2k ?2? 1 = =? ? ? k k k k ( RT + 2 RT ) / 2 (3RT ) ? 3 ? RT
k
(6)
綜上所述,我們可以得到節(jié)點(diǎn) i 的加權(quán)干擾總值,見公式(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é)點(diǎn) i 通信范圍內(nèi)所有鄰居節(jié)點(diǎn)的集合,S2T(i)為節(jié)點(diǎn)兩倍通信半徑,即 2×RT 范圍內(nèi)所有節(jié)點(diǎn)的集合. 網(wǎng)絡(luò)中節(jié)點(diǎn)干擾值是一種處于不斷動態(tài)變化過程中的網(wǎng)絡(luò)狀態(tài) ,獲得準(zhǔn)確的實(shí)時值是非常困難的 , 并且過 于頻繁地變化也不利于網(wǎng)絡(luò)性能控制 .所以 ,利用節(jié)點(diǎn)干擾值的歷史信息 ,通過加權(quán)時序平均數(shù)的方式預(yù)測出下 一時刻的干擾值 ,作為控制網(wǎng)絡(luò)性能的依據(jù) .通信量是隨機(jī)分布的 ,并且會隨著網(wǎng)絡(luò)沖突、擁塞、節(jié)點(diǎn)的移動等 情況而發(fā)生動態(tài)的變化 , 加權(quán)時序平均數(shù)方法可以通過加大新歷史數(shù)據(jù)權(quán)重 ,讓干擾預(yù)測值能夠迅速、及時地 反映出通信量變化 .同時 ,網(wǎng)絡(luò)中也可能會出現(xiàn)突發(fā)通信量引起節(jié)點(diǎn)干擾值的急劇波動 ,加權(quán)時序平均數(shù)方法能 夠平緩?fù)话l(fā)通信量的影響. 假設(shè)節(jié)點(diǎn) 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ù) .其值越大 ,說明該時刻的干擾值對下一時刻的干擾 值影響越大;值越小,說明其影響越小.當(dāng)某系數(shù)為 0 時,說明該時刻的干擾值對下一時刻干擾值沒有影 響.1≥α>β>χ>δ>…>ε≥0,且α+β+χ+δ+…+ε=1.
張信明 等:移動 Ad Hoc 網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(xié)議
2725
2.3 通信量干擾模型的實(shí)現(xiàn) 我們利用已有的 RTS(request to send)/CTS 控制包來實(shí)現(xiàn)通信量干擾模型.利用 RTS/CTS 除了開銷小、實(shí) 現(xiàn)方便以外 ,還使得節(jié)點(diǎn)不需要定期地向周圍節(jié)點(diǎn)廣播通信量信息 ,而只需在有發(fā)送活動時才廣播通信量信息 , 避免了不必要的信息重復(fù)交換 .同時也能及時地反映出通信量的動態(tài)變化 ,使周圍節(jié)點(diǎn)獲取最新、最及時的通 信量信息.具體過程如下:
(1) 在 RTS 包中,增加 T 和 TF 兩個字段.其中,T 用來存放需要交換的通信量信息,TF 為標(biāo)志位,若該 RTS
包攜帶有通信量信息,則為 1,否則為 0.
(2) 為了提取通信量 ,節(jié)點(diǎn)在發(fā)送數(shù)據(jù)包時 ,在 MAC 層對其數(shù)目進(jìn)行統(tǒng)計.每個節(jié)點(diǎn)都有一個計時器 ,時間
設(shè)置為 1s.當(dāng)計時器計時時,節(jié)點(diǎn)累加數(shù)據(jù)包數(shù)目,當(dāng)計時器超時時,即可得到最近 1s 內(nèi)的數(shù)據(jù)包發(fā)送率.然后根 據(jù)公式(1)可以求得該節(jié)點(diǎn)的平均通信量 T. 當(dāng)計時器處于計時狀態(tài)時 ,由于節(jié)點(diǎn)尚未統(tǒng)計出通信量值 ,不需要向周圍節(jié)點(diǎn)進(jìn)行廣播 ,因此 ,將 RTS 包的
TF 位設(shè)置為 0.當(dāng)鄰近節(jié)點(diǎn)第 1 次收到這個 TF 為 0 的 RTS 包時,采用原有的 RTS/CTS 機(jī)制,不做任何其他動作 .
當(dāng)計時器處于超時狀態(tài)時,節(jié)點(diǎn)需要向周圍鄰近節(jié)點(diǎn)廣播新的平均通信量,將 TF 位設(shè)置為 1.同時將 RTS 包的 TTL 位設(shè)為 2,使得 RTS 可以傳輸兩跳,覆蓋了節(jié)點(diǎn)的兩倍通信范圍,從而使得兩倍通信范圍內(nèi)的所有節(jié)點(diǎn) 都能收到攜帶了該節(jié)點(diǎn)通信量的 RTS 包,能夠獲知該節(jié)點(diǎn)上的通信量情況.
(3) 當(dāng)節(jié)點(diǎn)第 1 次收到一個 RTS 包后,如果 TF 為 1,就提取該 RTS 包中的通信量信息.此時,該節(jié)點(diǎn)需要另
外一個計時器,來統(tǒng)計 1s 內(nèi)所有鄰近節(jié)點(diǎn)上的通信量加權(quán)和,以得到該節(jié)點(diǎn)的干擾值. 具體來說,當(dāng)節(jié)點(diǎn)第 1 次收到的 RTS 包的 TF 位為 1 時,如果此時該包的 TTL 為 1,說明該節(jié)點(diǎn)在發(fā)送 RTS 包的節(jié)點(diǎn)的通信范圍內(nèi).可以根據(jù) RTS 包的接收功率,依照公式(3)計算出這兩個節(jié)點(diǎn)間的距離 d.此時,該節(jié)點(diǎn)的 干擾值 I 累加 T/dk(其中,T 是 RTS 包中攜帶的通信量信息),并且按照原有 RTS/CTS 機(jī)制,抑制自身的通信活動. 如果節(jié)點(diǎn)第 1 次收到一個 RTS 包,TF 位為 1,且該包的 TTL 為 0,則說明這個節(jié)點(diǎn)在 RTS 發(fā)送節(jié)點(diǎn)的通信范
?2? T 圍以外.這時,將該節(jié)點(diǎn)的干擾值 I 增加 ? ? ? k .其中,T 是 RTS 包中攜帶的通信量信息.由于收到該 RTS 包的 ? 3 ? RT
節(jié)點(diǎn)已位于通信范圍之外,所以不必抑制自身的通信活動. 按照上述機(jī)制 ,我們得到了節(jié)點(diǎn)每秒鐘的即時干擾值 .然后根據(jù)歷史記錄 ,按照公式 (8)估算出下一時刻該節(jié) 點(diǎn)可能受到的干擾值大小.
k
3
通信量相關(guān)干擾感知路由協(xié)議
根據(jù)上述干擾模型的定義 , 我們得到了網(wǎng)絡(luò)中各個節(jié)點(diǎn)的干擾值 ,然后采用通信量相關(guān)干擾感知路由協(xié)議
來降低干擾.基于通信量的最小干擾路由協(xié)議,簡稱 TIR,選路機(jī)制與平均鏈路干擾感知路由協(xié)議 ALIR(average
link interference-aware routing) [10]類似.TIR 建立在 DSR(dynamic source routing)協(xié)議[15]基礎(chǔ)上,采用與 DSR 協(xié)議
相同的路由機(jī)制,可分為兩個部分:路由發(fā)現(xiàn)和路由維護(hù).主要的區(qū)別體現(xiàn)在路由發(fā)現(xiàn)過程中.具體過程如下:
(1) 該協(xié)議在路由請求包和路由應(yīng)答包中各自增加一個干擾值 I 字段,用來存放相關(guān)的干擾值.在各節(jié)點(diǎn)的
路由表中也增加一個干擾值 I 字段,用以存放與各路徑相關(guān)的干擾值信息.
(2) 在路由發(fā)現(xiàn)過程中,路由請求包在增加的干擾值 I 字段中記錄沿途各節(jié)點(diǎn)的干擾值.當(dāng)路由請求包到達(dá)
目的節(jié)點(diǎn)時,即可對所有中間節(jié)點(diǎn)的干擾值求和得到該路徑的干擾值.假設(shè)網(wǎng)絡(luò)存在一條從節(jié)點(diǎn) u0 到節(jié)點(diǎn) un 的 多跳路徑 P(u0,un):u0u1u0u2…un?1un,則其路徑干擾值可表達(dá)為公式(9). I ( P) = I (u0 ) + I (u1 ) + I (u2 ) + ... + I (un ?1 ) + I (un )
(9)
然后結(jié)合該路徑的長度即跳數(shù) n,計算出路徑的平均干擾值 Metric,見公式(10). I ( P) Metric( P) = (10) n (3) 目的節(jié)點(diǎn)收到的每個路由請求包都代表一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的可能路徑 ,并且可以從路由請求包
2726
Journal of Software 軟件學(xué)報 Vol.20, No.10, October 2009
的干擾值字段獲知每條路徑上的干擾值信息 .目的節(jié)點(diǎn)為每個路由請求包都生成一個路由應(yīng)答包 ,將完整的路 經(jīng)信息及其平均鏈路干擾值返回給源節(jié)點(diǎn).平均鏈路干擾值存放在路由應(yīng)答包的干擾值 I 字段中.
(4) 源節(jié)點(diǎn)收到路由應(yīng)答包后 , 即將路徑信息連同其對應(yīng)的平均鏈路干擾值記錄在自己的路由表中 . 當(dāng)源
節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包時 , 如果其路由表中已有到達(dá)目的節(jié)點(diǎn)的路徑 , 則在這些路徑中選擇平均鏈路干擾值最小 的一條進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā).
(5) 為使路由協(xié)議能夠適應(yīng)網(wǎng)絡(luò)拓?fù)浼巴ㄐ帕糠植嫉膭討B(tài)變化,具有自適應(yīng)性,除了采用與 DSR 協(xié)議相同
的路由維護(hù)機(jī)制外 ,新協(xié)議每隔一段時間將所有節(jié)點(diǎn)的路由表清空 , 然后重新發(fā)起一次路由發(fā)現(xiàn)過程進(jìn)行路由 更新.
4
模擬實(shí)驗(yàn)
本節(jié)我們用模擬實(shí)驗(yàn)來驗(yàn)證通信量相關(guān)干擾感知路由協(xié)議 TIR 的性能,比較的對象是 DSR 路由協(xié)議和平
均鏈路干擾感知路由協(xié)議 ALIR[10],使用的模擬實(shí)驗(yàn)環(huán)境是 ns-2 模擬器[16]. 模擬環(huán)境和參數(shù):所有節(jié)點(diǎn)隨機(jī)分布在 1000m×1000m 的區(qū)域內(nèi);節(jié)點(diǎn)數(shù)為 49;CBR(constant bit rate)數(shù)據(jù)流 隨機(jī)生成 ,即每條 CBR 的源節(jié)點(diǎn)和目的節(jié)點(diǎn)隨機(jī)選擇 ,并分別考慮了變化數(shù)量和固定數(shù)量的情況 .數(shù)據(jù)包大小 為 512 字節(jié),并分別考慮了固定速率和變化速率的情況;節(jié)點(diǎn)傳輸半徑為 150m;節(jié)點(diǎn)感知范圍為 300m;初始能量 為 100;模擬時間為 300s;對于節(jié)點(diǎn)的移動性,采用普遍使用的 RWP(random waypoint model)模型,節(jié)點(diǎn)的初始位 置是隨機(jī)生成的,節(jié)點(diǎn)最小速度為 0m/s,最大速度為 20m/s;MAC 層協(xié)議為 802.11 協(xié)議 (RTS/CTS 機(jī)制根據(jù)第 2.3 節(jié)作了修改);路由層協(xié)議為 DSR 協(xié)議基礎(chǔ)上改進(jìn)而來的 TIR 協(xié)議.另外,在模擬過程中,在計算節(jié)點(diǎn)平均通信量 時,取最近 5 個連續(xù)時刻的通信量求平均值;在計算節(jié)點(diǎn)干擾值時,取最近 3 個時刻的干擾值用以估算下一時刻 節(jié)點(diǎn)的干擾值信息,且α=0.5,β=0.3,χ=0.2. 首先在網(wǎng)絡(luò)中隨機(jī)分布 49 個節(jié)點(diǎn),每條 CBR 數(shù)據(jù)流每秒鐘發(fā)送 120 個數(shù)據(jù)包.圖 1~圖 3 分別是不同 CBR 數(shù)據(jù)流總數(shù)情況下的丟包率、平均延遲和網(wǎng)絡(luò)吞吐量.然后,固定 CBR 數(shù)據(jù)流的總數(shù)為 12 條,考察不同數(shù)據(jù)發(fā) 送率情況下的網(wǎng)絡(luò)性能.圖 4~圖 6 分別是不同數(shù)據(jù)發(fā)送率情況下的網(wǎng)絡(luò)壽命、平均延遲和網(wǎng)絡(luò)吞吐量. 由圖 1 可以看出,當(dāng)節(jié)點(diǎn)數(shù)不變時,在不同的負(fù)載下,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é)議的改進(jìn)不明顯,然而它卻獲得了很好的網(wǎng)絡(luò)吞吐量,并且大大優(yōu)于 DSR 協(xié)議.從圖 3 可知,在不同 CBR
數(shù)據(jù)流情況下,TIR 協(xié)議的吞吐量比 DSR 協(xié)議的吞吐量增加竟高達(dá) 84.17%.由圖 6 可得,在不同數(shù)據(jù)發(fā)送率的情 況下,TIR 協(xié)議的吞吐量比 DSR 協(xié)議的吞吐量增加 79.22%.由圖 4 可以看出,TIR 協(xié)議的網(wǎng)絡(luò)壽命比 DSR 協(xié)議 的網(wǎng)絡(luò)壽命平均延長 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)絡(luò)通信量相關(guān)干擾感知路由協(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)絡(luò)壽命
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é)束語
本文提出的通信量干擾模型不但考慮了節(jié)點(diǎn)的鄰居數(shù)目和鄰居的分布位置 , 而且考慮了各鄰居上的通信
量情況 . 鄰居節(jié)點(diǎn)上的通信活動越頻繁 , 發(fā)生碰撞沖突的概率就越大 , 對節(jié)點(diǎn)產(chǎn)生的干擾程度也就越大 . 采用
RTS/ CTS 機(jī)制實(shí)現(xiàn)了通信量干擾模型.利用已有的 RTS 包,除了開銷小、 實(shí)現(xiàn)方便以外,還使得節(jié)點(diǎn)不需要定期
地向周圍節(jié)點(diǎn)廣播通信量信息 ,而只需在有發(fā)送活動時才進(jìn)行廣播 ,避免了不必要的信息重復(fù)交換 .同時也能及 時地反映出通信量的動態(tài)變化 ,使周圍節(jié)點(diǎn)獲取最新、最及時的通信量信息 .干擾源與接收節(jié)點(diǎn)之間距離的遠(yuǎn) 近不同也會造成干擾程度的不同,我們利用 RTS/CTS 機(jī)制來測量各鄰居節(jié)點(diǎn)的距離,并以此作為因子為各節(jié)點(diǎn) 設(shè)置權(quán)值. 本文提出的通信量相關(guān)的干擾感知路由協(xié)議 ,在路由發(fā)現(xiàn)過程中搜集沿途所有中間節(jié)點(diǎn)的干擾值 , 當(dāng)?shù)竭_(dá) 目的節(jié)點(diǎn)時 ,即可累加求和得到路徑干擾值 ,并進(jìn)一步求得平均鏈路干擾值 .每一個可能路徑都向源節(jié)點(diǎn)返回一 個攜帶有干擾信息的路由應(yīng)答包 .源節(jié)點(diǎn)就按照收到的路由應(yīng)答包所攜帶的干擾信息 ,為數(shù)據(jù)包選擇平均鏈路 干擾值最小的那條路徑,進(jìn)行逐跳轉(zhuǎn)發(fā).大量模擬實(shí)驗(yàn)數(shù)據(jù)表明,通信量干擾模型及其路由協(xié)議對移動 Ad hoc 網(wǎng) 絡(luò)的各項(xiàng)性能都有一定的改善. 目前的移動 Ad hoc 網(wǎng)絡(luò)信道接入?yún)f(xié)議大多是基于單信道的,其對干擾問題的解決有限.我們的干擾模型也 是在單信道基礎(chǔ)上提出來的 ,因而也存在一定的局限性 ,下一步可以考慮在多信道接入?yún)f(xié)議基礎(chǔ)上來解決干擾 問題 .另外 ,本文所采用的信號衰減模型是最簡單、最理想的自由空間傳播模型 ,而實(shí)際的信號衰減情況可能要 復(fù)雜得多 ,所以更進(jìn)一步的實(shí)際應(yīng)用研究應(yīng)該針對較為復(fù)雜的信號傳播模型來進(jìn)行 .最后 ,我們的所有方案都是 在 ns-2 模擬器下實(shí)現(xiàn)的.該模擬器雖然功能十分強(qiáng)大,但與實(shí)際情況還是有些偏差.所以,為了設(shè)計出更為精確、 更能反映移動 Ad hoc 網(wǎng)絡(luò)特性的干擾模型和路由協(xié)議,需要在本文工作的基礎(chǔ)上采用另一種技術(shù)路線,即搭建
2728
Journal of Software 軟件學(xué)報 Vol.20, No.10, October 2009
測試床來驗(yàn)證有關(guān)模型和協(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 高級會員,主要研究領(lǐng)域?yàn)闊o線 網(wǎng)絡(luò),IP 網(wǎng)絡(luò) QoS 控制,網(wǎng)絡(luò)性能分析.
代仕芳(1984-),女,碩博連讀生,主要研究 領(lǐng)域?yàn)闊o線網(wǎng)絡(luò).
劉瓊(1982-),女,碩士,主要研究領(lǐng)域?yàn)闊o 線網(wǎng)絡(luò).
劉永振(1983-),男,碩士生,主要研究領(lǐng)域 為無線網(wǎng)絡(luò).
本文關(guān)鍵詞:移動Ad Hoc網(wǎng)絡(luò)通信量相關(guān)干擾感知路由協(xié)議,,由筆耕文化傳播整理發(fā)布。
本文編號:172205
本文鏈接:http://sikaile.net/kejilunwen/wltx/172205.html