Ad hoc網(wǎng)絡(luò)雙忙音多址訪問協(xié)議的研究與仿真*

喬平安　李峰杰　顏景善

(西安郵電大學(xué)計算機學(xué)院　西安　710121)

?

Ad hoc網(wǎng)絡(luò)雙忙音多址訪問協(xié)議的研究與仿真*

喬平安李峰杰顏景善

(西安郵電大學(xué)計算機學(xué)院西安710121)

摘要由于移動Ad hoc網(wǎng)絡(luò)沒有固定控制中心,信道訪問沖突十分嚴重。論文通過對雙忙音多址訪問(DBTMA)協(xié)議的仿真,發(fā)現(xiàn)當(dāng)網(wǎng)絡(luò)中存在暴露接收節(jié)點時,DBTMA協(xié)議出現(xiàn)了嚴重的不公平性問題,有些節(jié)點甚至可以壟斷信道。論文提出了一種針對DBTMA協(xié)議不足進行改進的策略,該策略通過設(shè)計一種基于競爭節(jié)點數(shù)目的自適應(yīng)競爭窗口調(diào)整因子,以達到根據(jù)網(wǎng)絡(luò)競爭狀況動態(tài)調(diào)整退避窗口的目的。仿真結(jié)果表明,改進后的DBTMA協(xié)議有效地解決了原協(xié)議存在的不公平性問題。

關(guān)鍵詞Ad hoc網(wǎng)絡(luò); 公平性; 調(diào)整因子; 退避窗口

Research and Simulation of DBTMA Protocol for Ad hoc Network

QIAO Ping’anLI FengjieYAN Jingshan

(School of Computer Science, Xi’an Univerity of Posts and Telecommunications, Xi’an710121)

AbstractChannel access conflict is very serious as mobile Ad hoc network has no fixed control center. By emulating dual busy tone multiple access(DBTMA) protocol, it is found that when there is receiving node in the network, DBTMA agreement appeared a serious problem of unfairness, some node can even monopolize the channel. An improve strategy is proposed in this paper aiming at the shtorage if the DBTMA protocol. By designing a kind of adaptive contention window adjument factor based on the number of node, in order to adjust the backoff window according to dynamic network competition. The simulation results show that the improved DBTMA agreement effectively solve the unfairness problem exists in orginal agrement.

Key WordsAd hoc network, fairness, adjustment factor, backoff window

Class NumberTP393

1引言

目前在無線Ad hoc網(wǎng)絡(luò)的研究工作中,多數(shù)采用IEEE802.11DCF[1]作為媒體接入控制(MAC)層協(xié)議。該協(xié)議大多利用載波監(jiān)聽技術(shù)(CSMA)[2]來減少數(shù)據(jù)碰撞,但這樣就會帶來隱藏節(jié)點和暴露節(jié)點的問題,從而影響節(jié)點訪問信道的公平性。一些研究表明節(jié)點在訪問信道時可能出現(xiàn)單個數(shù)據(jù)流獨占信道而其他數(shù)據(jù)流完全處于“饑餓”的狀態(tài),這就是所謂的公平性問題。現(xiàn)有的公平性改進方案大都以退避算法為基礎(chǔ),文獻[3]提到一種針對信道訪問的乘數(shù)遞增線性遞減(Multiplicative Increase Linear Decrease,MILD)退避算法,在一定程度上改善了節(jié)點的公平性,但會使節(jié)點較長時間處于較大競爭窗口狀態(tài),這樣反而會降低網(wǎng)絡(luò)吞吐量。文獻[4]提出一種改進的指數(shù)遞增指數(shù)遞減算法,遞增和遞減指數(shù)參數(shù)可以靈活配置,但如何準確配置參數(shù)還需認真考慮。

雙忙音多址接入(Dual Busy Tone Multiple Access,DBTMA)協(xié)議[5~6]是一種雙信道MAC協(xié)議,該協(xié)議可以在一定程度上解決隱藏節(jié)點和暴露節(jié)點[7]問題,其吞吐量性能優(yōu)于在單信道上使用RTS/CTS分組對話機制的其他MAC協(xié)議,以及所有使用單個忙音的MAC協(xié)議。然而DBTMA協(xié)議中忙音信號與數(shù)據(jù)信號的傳輸范圍相同,當(dāng)網(wǎng)絡(luò)中存在暴露接收節(jié)點時,該協(xié)議存在嚴重的不公平問題[8]。

文章分析了Ad hoc網(wǎng)絡(luò)中存在暴露接收節(jié)點時DBTMA協(xié)議的工作原理,提出了一種新的方案以改善DBTMA協(xié)議的公平性,該方案提出一種動態(tài)感知的退避算法。在保證原有網(wǎng)絡(luò)吞吐量的條件下,經(jīng)過改進后的DBTMA協(xié)議能有效地解決DBTMA協(xié)議存在的不公平問題,避免出現(xiàn)部分節(jié)點對信道的獨占和“餓死”節(jié)點現(xiàn)象。

2DBTMA協(xié)議描述

2.1暴露節(jié)點問題

DBTMA協(xié)議把整個帶寬劃分為兩個獨立的信道(數(shù)據(jù)信道和控制信道),同時增加兩個窄帶忙音,即發(fā)送忙音(BTt)和接收忙音(BTr),分別表示節(jié)點是否正在發(fā)送RTS分組或接收數(shù)據(jù)分組。忙音信號在數(shù)據(jù)持續(xù)發(fā)送期間,傳輸范圍與通信范圍相同[9]。

圖1　暴露節(jié)點

暴露節(jié)點是處于發(fā)送節(jié)點的通信范圍之內(nèi)而在接收節(jié)點的通信范圍之外的節(jié)點。如圖1所示,節(jié)點B為暴露接收節(jié)點。當(dāng)節(jié)點A向節(jié)點B發(fā)送RTS控制信號時,由于傳輸范圍限制,節(jié)點C無法監(jiān)聽到節(jié)點A發(fā)送的BTt信號,所以節(jié)點C能同時向節(jié)點D發(fā)送RTS控制信號。此時節(jié)點C處于接收節(jié)點B的傳輸范圍之內(nèi),節(jié)點A發(fā)送的信息和節(jié)點C發(fā)送的信息可能在節(jié)點B處發(fā)生沖突,導(dǎo)致節(jié)點B無法正確接收到節(jié)點A發(fā)送的控制信號,而節(jié)點D始終可以正確接收節(jié)點C發(fā)送來的控制信號,繼而完成數(shù)據(jù)傳輸任務(wù)。所以,DBTMA協(xié)議雖然能夠通過數(shù)據(jù)信道和控制信道避免信號的碰撞,但當(dāng)網(wǎng)絡(luò)中存在暴露接收節(jié)點時,控制信號的碰撞仍無法避免,從而帶來嚴重的不公平性。

2.2DBTMA協(xié)議仿真與分析

利用NS-2[10]對DBTMA協(xié)議進行仿真。采用圖2所示網(wǎng)絡(luò)拓撲結(jié)構(gòu),節(jié)點均為靜止狀態(tài),節(jié)點間距250m,通信范圍300m。需要指出的是,為了盡量減少其他因素對DBTMA協(xié)議公平性的影響,采用恒定比特率(CBR),仿真參數(shù)如表1所示。

圖2網(wǎng)絡(luò)拓撲結(jié)構(gòu)

為構(gòu)造暴露接收節(jié)點環(huán)境,建立節(jié)點A向節(jié)點B發(fā)送數(shù)據(jù),節(jié)點C向節(jié)點D發(fā)送數(shù)據(jù)的通信線路。仿真時間為200s,數(shù)據(jù)包發(fā)送間隔為1ms。為評價數(shù)據(jù)流之間的公平性,采用文獻[11]提出的公平性指數(shù)FI(Faurness Index)來衡量公平性,公平性指數(shù)定義為網(wǎng)絡(luò)最大鏈路吞吐量Tmax和最小鏈路吞吐量Tmin的比值,即:

表1　仿真參數(shù)

顯然,FI=1是最理想情況,每條鏈路吞吐量相同,公平分配資源。FI越大,節(jié)點競爭能力越懸殊,不公平性越明顯。表2給出了仿真實驗的吞吐量和公平性指數(shù)。

表2　DBTMA公平性仿真數(shù)據(jù)

注:ThAB表示節(jié)點A到節(jié)點B的吞吐量。

在圖2中節(jié)點A向節(jié)點B發(fā)送控制信號,節(jié)點C向節(jié)點B和D發(fā)送控制信號,由于節(jié)點B同時處于節(jié)點A和節(jié)點C的通信范圍之中,則節(jié)點A和節(jié)點C發(fā)出的控制信號可能在節(jié)點B處沖突。從而導(dǎo)致節(jié)點A發(fā)送的控制信號無法被節(jié)點B正確接收。同時,節(jié)點A無法檢測到節(jié)點C的發(fā)送忙音,所以一直認為控制信道空閑而持續(xù)向節(jié)點B發(fā)送控制信號。

仿真數(shù)據(jù)表明,由于節(jié)點B同時處于節(jié)點A和節(jié)點C的通信范圍內(nèi),使得DBTMA協(xié)議出現(xiàn)嚴重不公平性,節(jié)點C向節(jié)點D發(fā)送數(shù)據(jù)的通信線路幾乎獨占了全部信道。通過對仿真數(shù)據(jù)的分析,發(fā)現(xiàn)DBTMA協(xié)議在暴露接收節(jié)點場景下存在嚴重的不公平問題。

3DBTMA協(xié)議的改進與分析

3.1DBTMA協(xié)議的改進策略

針對2.1節(jié)所出現(xiàn)的問題以及對原有DBTMA協(xié)議的分析與仿真,對DBTMA協(xié)議進行改進,引入一種新的能根據(jù)網(wǎng)絡(luò)中競爭節(jié)點的數(shù)目自適應(yīng)調(diào)節(jié)競爭窗口的動態(tài)感知退避(Situational Awareness Backoff,SAB)算法,使退避窗口隨著網(wǎng)絡(luò)節(jié)點的競爭狀況處于動態(tài)變化之中,從而減少部分節(jié)點對信道的壟斷,改善協(xié)議的公平性。

3.2算法描述

SAB算法的核心思想是:通過建立競爭窗口初始值和退避階數(shù)與競爭節(jié)點數(shù)目的對應(yīng)關(guān)系,從而使調(diào)整因子隨競爭節(jié)點的數(shù)目處于動態(tài)變化之中,使競爭窗口可以根據(jù)節(jié)點的競爭狀態(tài)自適應(yīng)地調(diào)整。具體算法如下:

1) 估算網(wǎng)絡(luò)競爭節(jié)點的數(shù)目n。

2) 通過節(jié)點數(shù)n和CWmin,CWmax建立起競爭窗口CW的變化規(guī)律公式如式(1)所示。

(1)

其中a為函數(shù)的底數(shù),n為競爭節(jié)點數(shù)目,競爭窗口初始值為CWint。

3.3仿真與結(jié)果分析

利用NS-2對改進的DBTMA協(xié)議進行仿真。對圖2所示網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行改進,在節(jié)點C覆蓋區(qū)域內(nèi)增加n個競爭節(jié)點,節(jié)點目標地址隨機選擇。傳輸層采用UDP協(xié)議,物理層無線結(jié)點采用DSSS模型,競爭窗口參CWmin=15,CWmax=1023,仿真時間為200s。

3.3.1參數(shù)a的選取

為了使改進DBTMA協(xié)議的性能達到最優(yōu),SAB算法中對參數(shù)a的選取非常重要。針對a的取值問題,仿真了場景中存在不同競爭節(jié)點數(shù)目n時,a取不同值時Thcd(節(jié)點C和D之間的平均吞吐量)的值,仿真結(jié)果如表2所示。

表2　a不同值時Thcd的值(單位Kbps)

通過對表2中的數(shù)據(jù)比較可知,在競爭節(jié)點數(shù)目n取不同值得情況下,當(dāng)?shù)讛?shù)a=3時節(jié)點C和D之間的網(wǎng)絡(luò)吞吐量最大,因此對SAB算法中a=3。

3.3.2公平性分析

根據(jù)3.3.1節(jié)分析得出,使SAB算法性能達到最優(yōu)時參數(shù)a=3。在此前提下利用3.1.1節(jié)中仿真的網(wǎng)絡(luò)結(jié)構(gòu)和仿真參數(shù)對改進后的DBTMA協(xié)議進行仿真。

表3為改進后DBTMA協(xié)議兩條線路吞吐量和公平性指數(shù)的仿真結(jié)果。從表3可知,不論n取何值兩條通信線路的吞吐量相差無幾,公平性指數(shù)FI幾乎趨于最理想狀況。圖3更直觀地顯示了改進前后DBTMA協(xié)議兩條線路吞吐量的比較。兩條線路吞吐量幾乎一樣,不存在差值較大的不公平現(xiàn)象。

圖4顯示了競爭節(jié)點數(shù)目不同時公平性指數(shù)FI的分布。如圖所示,改進后的DBTMA協(xié)議接入信道的公平性指數(shù)接近于1且相對穩(wěn)定。

圖3　改進后DBTMA協(xié)議兩條線路吞吐量的比較

圖4　不同競爭節(jié)點下公平性指數(shù)的變化

nThAB(Kpbs)ThCD(Kpbs)FI31158.3921245.6831.0744956.7811086.4721.1365903.351984.2371.0906698.504748.8721.072

4結(jié)語

本文通過對DBTMA協(xié)議在暴露接收節(jié)點場景下的仿真,發(fā)現(xiàn)節(jié)點接入信道存在嚴重的公平性問題甚至可能出現(xiàn)壟斷的現(xiàn)象。針對該問題,提出了一種改進方案,設(shè)計了一種基于競爭節(jié)點數(shù)目的窗口調(diào)整因子,使競爭窗口可以隨著Ad hoc網(wǎng)絡(luò)的信道使用情況而自適應(yīng)調(diào)整。仿真結(jié)果表明,該改進方案能有效地改進原DBTMA協(xié)議的公平性,使通信線路間的資源能平均分配。

參 考 文 獻

[1] IEEE 802.11-2007. Part Ⅱ: Wireless LAN Medium Access Control(MAC) and Physical Layer(PHY) Specification[S]. 2007.

[2] 趙志峰,鄭少仁.Ad hoc網(wǎng)絡(luò)載波監(jiān)聽雙信道接入?yún)f(xié)議[J].浙江大學(xué)學(xué)報,2005,39(4):478-482.

ZHAO Zhifeng, ZHENG Shaoren. Carrier sensing based dual channel access protocol for Ah Hoc network[J]. Journal of Zhejiang University,2005,39(4):478-482.

[3] 夏羽.Ad Hoc網(wǎng)絡(luò)MAC協(xié)議退避算法研究[D].上海:上海交通大學(xué),2012:3-9.

XIA Yu. Research on Backoff Algorithm in MAC protocol for Ad Hoc Nerwork[D]. Shanghai: Shanghai Jiao Tong University,2012:3-9.

[4] Fan Jing. Performance Analysis of an Adaptive Back-off Scheme for Ad Hoc Networks[C]//Proceedings of IEEE 8th International Conference on Computer and Information Techonolgy Sydney: IEEE,2008:624.

[5] DENG J, HAAS Z J. Dual busy tone multiple access(DBTMA): A multiple access control scheme for ad hoc network[J]. IEEE Transaction Connumication,2002,50(6):975-980.

[6] 陳林星,曾曦,曹毅,等.移動AdHoc網(wǎng)絡(luò):自組織分組無線網(wǎng)絡(luò)技術(shù)[M].北京:電子工業(yè)出版社,2012:81-93.

CHEN Linxing, ZENG Xi, CAO Yi, et al. Mobile Ad Hoc: self-organizing packet radio network technology[M]. Beijing: Electronic Industry Press,2012:81-93.

[7] 蘭麗,單志龍.Ad Hoc網(wǎng)絡(luò)中隱藏終端和暴露終端相關(guān)問題研究[J].計算機與數(shù)字工程,2010,38(7):36-40.

LAN Li, SHAN Zhilong. Analysisi on Relevant Prob-Lems of Hidden Teminal and Exposed Teminal in Ad Hoc Networks[J]. Computer and Digital Engineering,2010,37(7):36-40.

[8] 尤文玨,王成華,等.Ad hoc網(wǎng)絡(luò)雙忙音多址接入?yún)f(xié)議的公平性改進[J].計算機與數(shù)字工程,2014,42(2):256-260.

YOU Wenjue, WANG Chenghua, et al. Improving of the DNTMA Protocol Fairness in Ad hoc Network[J]. Computer and Digital Engineering,2014,42(2):256-260.

[9] 蔡雪蓮.無線Ad Hoc網(wǎng)絡(luò)接入和路由關(guān)鍵技研究[D].西安:西安電子科技大學(xué),2013:23-41.

CAI Xuelian. Study on Multiple Access and Routing Technonlgy in Wireless Ad Hoc Networks[D]. Xi’an: Xi’an Electronic and Engineering University,2013:23-41.

[10] The Network Simulator-ns-2[OL]. http://www.isi.edu/nsnam/ns.

[11] Bharghavan V, Demers A, Sjenker S, et al. MACAW: A media access protocol for wireless LANs[C]//Proceedings of the ACM SIGCOMM Conference on Communications Architectures Protocols and Applications,2010:212-225.

中圖分類號TP393

DOI:10.3969/j.issn.1672-9722.2016.03.024

作者簡介:喬平安,男,副教授,研究方向:數(shù)據(jù)庫技術(shù)、計算機網(wǎng)絡(luò)。李峰杰,男,碩士研究生,研究方向:PC客戶端開發(fā)。顏景善,男,碩士研究生,研究方向:Web服務(wù)器開發(fā)。

收稿日期:2015年9月9日,修回日期:2015年10月24日