吳國鳳， 魯頂芝

（合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009）

IEEE 802.11DCF［1］協(xié)議以其簡易性與健壯性成為目前主流的無線ad hoc網(wǎng)絡(luò)的MAC協(xié)議，其基本思想是載波偵聽與沖突避免。同時，DCF協(xié)議也提供了2種數(shù)據(jù)包傳輸機制、2次握手機制（又被稱作為基本機制）和4次握手機制（又被稱作為RTS／CTS機制）。許多當(dāng)前提出的無線網(wǎng)絡(luò)標(biāo)準(zhǔn)都具有多速率的能力，如802.11b支持1、2、5.5、11Mb／s 4種速率，而802.11a／g支持6、9、12、18、24、36、48、54Mb／s 8種速率。傳統(tǒng)的無線ad hoc網(wǎng)絡(luò)路由協(xié)議都是基于單速率環(huán)境下設(shè)計的，而且大多數(shù)路由協(xié)議都以源節(jié)點和目的節(jié)點之間的最少跳數(shù)為路由判據(jù)進行路由選擇。由于高傳輸速率與有效的傳輸范圍之間存在固有的權(quán)衡，傳統(tǒng)路由傾向選擇長距離低速率鏈路，且沒有考慮時變信道，造成部分鏈路不可用。

近年來，為了適應(yīng)ad hoc網(wǎng)絡(luò)的動態(tài)性，路由協(xié)議的跨層設(shè)計越來越引起人們的關(guān)注［2－4］。文獻［2］分別以鏈路速率倒數(shù)、MAC延遲、排隊延遲作為網(wǎng)絡(luò)狀態(tài)屬性，但沒有綜合考慮帶寬與延遲之間的關(guān)系；文獻［3］以加權(quán)期望傳輸時間WCETT進行路由，但不能準(zhǔn)確預(yù)測真實傳輸量，獨立于網(wǎng)絡(luò)負(fù)載，降低了吞吐量；文獻［4］在全干擾的假設(shè)前提下，提出媒體占用時間MTM路由判據(jù)，雖然算法簡單，但沒有考慮擁塞和負(fù)載的影響，容易產(chǎn)生局部擁塞。

本文提出了信道忙延遲路由判據(jù)，在選擇高速率的同時考慮信道的負(fù)載情況，進行擁塞控制，合理有效地利用網(wǎng)絡(luò)資源。

1 ad hoc網(wǎng)絡(luò)跨層路由協(xié)議

一個好的路由選擇由一個可靠的路由判據(jù)決定，路由判據(jù)是源節(jié)點選擇最佳路由的依據(jù)。若源節(jié)點有多個路由通向目的節(jié)點時，則其將根據(jù)路由協(xié)議中的判據(jù)值選擇通信的路由。為了防止網(wǎng)絡(luò)局部資源的過度利用，無線ad hoc網(wǎng)絡(luò)的路由選擇應(yīng)與網(wǎng)絡(luò)資源分配相互協(xié)調(diào)，并跨層影響鏈路的延遲、丟包等。因此，在多速率無線ad hoc網(wǎng)絡(luò)中，路由判據(jù)應(yīng)不僅能體現(xiàn)網(wǎng)絡(luò)信道質(zhì)量，而且能體現(xiàn)局部區(qū)域的繁忙程度并指導(dǎo)路由避開這些區(qū)域，最大化資源利用。

1.1 路由判據(jù)設(shè)計

當(dāng)網(wǎng)絡(luò)處于非飽和狀態(tài)時，沖突概率越小，在沖突中浪費的信道資源越少，可忽略。根據(jù)IEEE 802.11DCF協(xié)議的2種數(shù)據(jù)包傳輸機制，一個數(shù)據(jù)包傳輸時所經(jīng)歷的時間Te（期望傳輸時間，不含沖突時間）可以有效地衡量網(wǎng)絡(luò)在非飽和狀態(tài)下的傳輸延遲，是一個反映信道質(zhì)量的實時參數(shù)。

隨著網(wǎng)絡(luò)負(fù)載的增加以及節(jié)點的移動，導(dǎo)致內(nèi)部流量不平衡、數(shù)據(jù)傳輸沖突增多。沖突概率可以較準(zhǔn)確地體現(xiàn)信道的繁忙程度。在有多個節(jié)點競爭信道的鏈路上傳輸數(shù)據(jù)時，由于沖突重傳導(dǎo)致節(jié)點接入信道的時間開銷增加。競爭節(jié)點數(shù)越多，沖突的概率就越大。但是，在實際應(yīng)用中，沖突概率并不容易獲得，其需要完全掌握本地節(jié)點和網(wǎng)絡(luò)中其他節(jié)點流量的到達模型，且無法區(qū)別網(wǎng)絡(luò)沖突和信道衰減。

在IEEE 802.11DCF協(xié)議中，節(jié)點利用載波偵聽機制進行沖突退避重傳。當(dāng)發(fā)送節(jié)點偵聽到信道有載波（即共享信道上有其他相鄰節(jié)點發(fā)送數(shù)據(jù)或有沖突發(fā)生）時，則認(rèn)為信道忙，該節(jié)點將調(diào)用隨機退避規(guī)程。當(dāng)退避計時器遞減為零且物理信道空閑時，節(jié)點才能傳輸幀。信道忙率不僅考慮到接入信道后一個數(shù)據(jù)包成功接收所需要傳輸?shù)拇螖?shù)（包括重傳），而且是沖突概率的映射函數(shù)［5］。當(dāng)沖突概率pc≤0.1時，信道忙率等價于信道利用率。在沖突概率從0.1～0.2的變化中，吞吐量基本保持不變。吞吐量與信道利用率成正比，用信道忙率Rb能準(zhǔn)確估計網(wǎng)絡(luò)吞吐量，當(dāng)信道忙率Rb超過某一閾值，則有沖突發(fā)生。

本文結(jié)合期望傳輸時間Te和信道忙率Rb，引入信道忙延遲（Delay of Channel Busyness，簡稱DCB），即

其中，Te為期望傳輸時間是MAC層的傳輸延遲估計，體現(xiàn)了信道質(zhì)量，以適應(yīng)時變的信道條件。作為路由判據(jù)的一個參數(shù)，它能夠保證數(shù)據(jù)傳輸過程中總的信道占用時間最小化，減少分組端到端時延，使單位時間內(nèi)能進行較多的數(shù)據(jù)傳輸，以提高網(wǎng)絡(luò)吞吐量。

信道忙率Rb能體現(xiàn)周圍節(jié)點競爭信道情況，作為路由判據(jù)的另一參數(shù)，能夠有效控制沖突概率，提高網(wǎng)絡(luò)吞吐量。同時，信道忙率Rb還可以較好地體現(xiàn)網(wǎng)絡(luò)拓?fù)渥兓闆r，如由于ad hoc網(wǎng)絡(luò)中節(jié)點的移動，導(dǎo)致與本次數(shù)據(jù)傳送發(fā)生沖突。

由此可見，信道忙延遲DCB能夠有效衡量網(wǎng)絡(luò)信道狀態(tài)。給定一個包含n個節(jié)點的路徑P＝ ｛c1，c2，…，cn｝，ci是 路 徑P上 的 一 個 節(jié) 點（ci∈P），其中1≤i≤n。則路徑P成功傳輸能力可表示為：

其中，1≤i≤n－1，1≤j≤n－1，選用瓶頸鏈路更有利于對鏈路局部變化做出及時反應(yīng)。

（1）Te的計算。根據(jù)文獻［6］，對于IEEE 802.11DCF的RTS／CTS機制和基本機制2種數(shù)據(jù)包傳輸方式，可以分別得到：

其中，Tdata＝（Lhead＋Lpl）／rc，rc為信道速率，每個數(shù)據(jù)包中包括固定長度的MAC頭、IP頭和TCP頭及試圖發(fā)送的數(shù)據(jù)包長度；RTS、CTS和ACK控制幀是用基本速率1Mb／s傳送的；SIFS、DIFS為幀間空閑時間。因此，實際應(yīng)用中，有效數(shù)據(jù)速率并不與信道速率直接成正比，而與包大小和協(xié)議開銷緊密相關(guān)。

（2）Rb的計算。根據(jù)文獻［6］，在IEEE 802.11DCF網(wǎng)絡(luò)中，節(jié)點為了成功地傳輸一個數(shù)據(jù)包需要競爭信道，由此會帶來多次的沖突和退避。設(shè)網(wǎng)絡(luò)中有n個節(jié)點，pt表示節(jié)點的嘗試傳輸概率，pi表示沒有任何節(jié)點傳輸時的信道空閑概率，ps表示至少有一個節(jié)點成功傳輸?shù)母怕?，pc表示至少有2個節(jié)點同時傳輸時的沖突概率，則有：

令Ri表示信道空閑率，Rb表示信道忙率。則由（3）式（或（4）式）、（5）式可以得到：

其中，TSLOT為一個物理時隙的大?。▽τ谖锢韺邮褂弥苯有蛄袛U頻技術(shù)DSSS而言，其值等于20μs）；Tcol為節(jié)點沖突時所經(jīng)歷的時間。在RTS／CTS機制和基本機制2種數(shù)據(jù)包傳輸方式下，可以分別得到：

由以上公式可知，信道忙率是競爭節(jié)點數(shù)的函數(shù)。雖然由于無線ad hoc網(wǎng)絡(luò)的時變特性，不能動態(tài)地知道競爭節(jié)點的數(shù)目，但是在IEEE 802.11DCF協(xié)議中，載波偵聽機制使得一個主機很容易區(qū)分空閑時隙（沒有載波）和其他2種狀態(tài)（有載波）。所以利用2次連續(xù)成功傳輸之間的空閑時隙數(shù)ni來衡量信道空閑率Ri，則由（6）式可得發(fā)送節(jié)點到相鄰節(jié)點間信道忙率。

對于給定的具有相同源和目的節(jié)點的2個路徑，若P1＞P2，則認(rèn)為路徑P1比路徑P2的鏈路代價高，路徑選擇時應(yīng)該選擇P2。如果代價相同，則選擇跳數(shù)少的。

1.2 跨層路由協(xié)議（CBAR協(xié)議）實現(xiàn)

本文改進現(xiàn)今應(yīng)用最廣的AODV按需路由協(xié)議［7］，用信道忙延遲來進行跨層路由設(shè)計，提出信道忙感知路由CBAR協(xié)議，以實現(xiàn)動態(tài)優(yōu)化。在無線ad hoc網(wǎng)絡(luò)中，CBAR協(xié)議的物理層通過使用不同的調(diào)制方式和信道編碼方法來提供多速率能力，MAC層通過多速率自適應(yīng)機制來根據(jù)信道質(zhì)量選擇數(shù)據(jù)發(fā)送速率并計算期望傳輸延遲Te，同時節(jié)點記錄2次連續(xù)成功傳輸之間的空閑時隙數(shù)ni來計算信道空閑率Ri，并通過RREQ分組和RREP分組更新節(jié)點路由信息進行路由選擇。

與AODV協(xié)議比較，CBAR協(xié)議路由執(zhí)行過程的改動如下。

（1）路由發(fā)現(xiàn)過程。廣播id號和目的節(jié)點序列號唯一標(biāo)識一個數(shù)據(jù)包，在AODV路由協(xié)議的路由發(fā)現(xiàn)過程中，中間節(jié)點對同一個節(jié)點發(fā)送的相同數(shù)據(jù)包不予轉(zhuǎn)發(fā)，而CBAR協(xié)議在RREQ分組中添加到鄰居節(jié)點的期望傳輸時間Te和信道忙率Rb2個域，中間節(jié)點轉(zhuǎn)發(fā)是對同一個數(shù)據(jù)包不是簡單的丟棄而是比較2個參數(shù)更新為瓶頸值后再轉(zhuǎn)發(fā)。每個節(jié)點維護的路由表添加一個信道忙延遲DCB（P）路由表項，目的節(jié)點收到第1個RREQ分組后，將等待一段時間以獲取所有可能的路徑，比較不同路徑的代價，選擇代價最小路徑為最佳路由。當(dāng)數(shù)據(jù)發(fā)送的重傳次數(shù)超過7次后，認(rèn)為傳輸失敗。

在路由發(fā)現(xiàn)過程中，為了避免過時的路由信息，只有目的節(jié)點才可以回復(fù)RREP分組，不允許中間節(jié)點回復(fù)RREP分組，即使中間節(jié)點有到達目的節(jié)點的活動路由。同時，RREP分組中添加Te和Rb2個域，其值隨網(wǎng)絡(luò)實時狀態(tài)不斷變化，源節(jié)點收到RREP分組時，根據(jù)路徑代價DCB（P）和目的節(jié)點的序列號的新舊來選擇路由。

（2）路由維護過程。在路由維護階段，AODV協(xié)議通過廣播HELLO分組進行局部連接性的管理，而在CBAR協(xié)議中可通過MAC層的檢測信息來判斷鏈路的連接性。當(dāng)MAC層檢測到在2次連續(xù)成功傳輸?shù)目臻e時隙數(shù)ni超過一定值時，即信道雖然空閑但數(shù)據(jù)分組總不能成功傳輸，則認(rèn)為鏈路中斷，并在網(wǎng)絡(luò)層發(fā)送RRER分組通知源節(jié)點重路由。這樣做網(wǎng)絡(luò)層就不再需要發(fā)送HELLO分組，避免帶來了額外的開銷和對正常數(shù)據(jù)傳輸?shù)母蓴_。

2 協(xié)議仿真與分析

本文使用NS2［8］仿真工具，比較在最小信道忙延遲（min－DCB）、最少跳數(shù)（min－h(huán)op）、最小媒體占用時間（min－MTM）這3種路由判據(jù)下進行路由選擇的網(wǎng)絡(luò)性能。在仿真環(huán)境下生成節(jié)點間數(shù)據(jù)通信的跟蹤文件，通過編寫腳本程序計算網(wǎng)絡(luò)分組投遞率和平均端到端延遲，并運行腳本程序來分析記錄文件。

2.1 仿真環(huán)境設(shè)置

MAC層采用802.11DCF機制，物理層使用802.11b。仿真場景設(shè)置為800m×800m的區(qū)域，隨機分配50個節(jié)點，仿真采用隨機?？糠绞健Ｃ總€節(jié)點隨機選擇鄰居節(jié)點發(fā)送UDP交通流量，每個節(jié)點的隊列長度為8 000kb／s。通過設(shè)定UDP流的開始時間來控制沖突概率，并不斷增加網(wǎng)絡(luò)流量負(fù)載來進行比較。仿真時間為200s，IEEE 802.11所涉及的參數(shù)以及默認(rèn)值見表1所列。

表1 IEEE 802.11相關(guān)參數(shù)

2.2 仿真結(jié)果分析

（1）隨著網(wǎng)絡(luò)負(fù)載的變化比較分組投遞率，如圖1所示。

圖1 分組投遞率隨負(fù)載變化的比較

當(dāng)網(wǎng)絡(luò)負(fù)載較輕時，節(jié)點接入信道發(fā)生沖突概率較小，網(wǎng)絡(luò)飽和接收包隨網(wǎng)絡(luò)負(fù)載的增加而增加，3種判據(jù)下的分組投遞率均可達到90%以上。隨著網(wǎng)絡(luò)負(fù)載的增加，可看到min－MTM和min－DCB比min－h(huán)op有明顯提高。這是因為在相同源與目的節(jié)點之間的路由，min－h(huán)op所選擇的路徑平均每跳之間的距離較長，容易削弱信道強度，使丟包率增大，而 min－DCB和 min－MTM能夠選擇吞吐量高的鏈路。由于min－DCB兼顧高速率和信道繁忙程度，有時為了避開選擇較繁忙的信道，會選擇速率較低鏈路，所以當(dāng)負(fù)載在500kb／s之前，min－DCB的分組投遞率比 min－MTM低。隨著網(wǎng)絡(luò)負(fù)載繼續(xù)增加，min－MTM會導(dǎo)致高速率鏈路局部擁塞，使網(wǎng)絡(luò)飽和接收包隨局部鏈路飽和而達到飽和。因此，min－DCB能均衡網(wǎng)絡(luò)負(fù)載，延長網(wǎng)絡(luò)處于非飽和狀態(tài)的時間，其分組投遞率要比 min－h(huán)op提高了近25%，比min－MTM提高了5%。

（2）網(wǎng)絡(luò)平均端到端延遲隨著網(wǎng)絡(luò)負(fù)載的變化比較，如圖2所示。當(dāng)網(wǎng)絡(luò)負(fù)載較輕時，因為跨層信息交互導(dǎo)致延遲增大，所以min－DCB的端到端延遲較之min－h(huán)op要略大些。隨著網(wǎng)絡(luò)負(fù)載的增加，min－h(huán)op傾向選擇低速率鏈路，使端到端延遲增加，而min－MTM會選擇高速率鏈路，可明顯降低端到端延遲。隨著網(wǎng)絡(luò)負(fù)載的繼續(xù)增加，min－MTM導(dǎo)致高速率鏈路上網(wǎng)絡(luò)節(jié)點的隊列長度增大。當(dāng)緩沖隊列超過80%時，高速鏈路出現(xiàn)明顯的擁塞，服務(wù)時間呈指數(shù)上漲，使網(wǎng)絡(luò)延遲增大。min－DCB雖然前期延遲性能不如 min－MTM，但是可以較長時間維持較好的端到端延遲，從整體上看，其平均端到端延遲比min－MTM降低了4%。

圖2 平均端到端延遲隨負(fù)載變化的比較

3 結(jié)束語

本文改進了無線ad hoc網(wǎng)絡(luò)的AODV協(xié)議，以信道忙延遲為新的路由判據(jù)，跨層引入到網(wǎng)絡(luò)層進行路由選擇。同時，通過MAC層2次連續(xù)成功傳輸?shù)目臻e時隙數(shù)來檢測鏈路連接性，減少了HELLO分組的開銷。仿真比較最小信道忙延遲、最少跳數(shù)和最小媒體時間3種路由判據(jù)下的協(xié)議性能可知，信道忙感知路由協(xié)議不僅能夠動態(tài)適應(yīng)信道的物理狀態(tài)，充分利用多速率機制的帶寬，而且能夠?qū)崟r掌握信道競爭情況，均衡網(wǎng)絡(luò)負(fù)載，有效避免局部擁塞。

［1］ANSI／IEEE.802.11－2003，Wireless LAN medium access control（MAC）and physical layer（PHY）specifications［S］.

［2］Yuen W H，Lee H N，Andersen T D.A simple and effective cross layer networking system for mobile ad hoc networks［C］／／The l3th IEEE International Symposium on Persona1，Indoor and Mobile Radio Communications，Vol 4，2002：1952－1956.

［3］Draves R，Padhye J，Zill B.Routing in multi－radio，multihop wireless mesh networks［C／OL］／／Proceedings of the 10th Annual International Conference on Mobile Compu－ting and New working，New York，NY，USA，2004.http：／／citeseerx.ist.psu.edu／viewdoc／summary？doi＝10.1.1.160.7916.

［4］Awerbuch B，Holmer D，Rubens H.The medium time metric：high throughput route selection in multi－rate ad hoc wireless networks［J］.MONET，2006，11（2）：253—266.

［5］Zhai H Q，Chen X，F(xiàn)ang Y G.How well can the IEEE 802.11wireless LAN support quality of service［J］.IEEE Transactions on Wireless Communications，2005，4（6）：3084－3094.

［6］Bianchi G.Performance analysis of the IEEE 802.11distributed coordination function［J］.IEEE Journal of Selected Areas in Communications，2000，18（3）：535—547.

［7］Perkins C E，Royer E M.Ad－h(huán)oc on－demand distance vector routing［C］／／Proceeding of the 2nd IEEE Workshop on Mobile Computing Systems and Applications，1999：90－100.

［8］Kennedy J，Eberhart R.Particle swarm optimization［C］／／Proceedings of IEEE International Conference on Neural Networks，USA，1995：1942－1948.