多速率ad hoc網(wǎng)絡(luò)的信道忙感知路由協(xié)議

吳國(guó)鳳， 魯頂芝

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

IEEE 802.11DCF［1］協(xié)議以其簡(jiǎn)易性與健壯性成為目前主流的無(wú)線(xiàn)ad hoc網(wǎng)絡(luò)的MAC協(xié)議，其基本思想是載波偵聽(tīng)與沖突避免。同時(shí)，DCF協(xié)議也提供了2種數(shù)據(jù)包傳輸機(jī)制、2次握手機(jī)制（又被稱(chēng)作為基本機(jī)制）和4次握手機(jī)制（又被稱(chēng)作為RTS／CTS機(jī)制）。許多當(dāng)前提出的無(wú)線(xiàn)網(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)的無(wú)線(xiàn)ad hoc網(wǎng)絡(luò)路由協(xié)議都是基于單速率環(huán)境下設(shè)計(jì)的，而且大多數(shù)路由協(xié)議都以源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的最少跳數(shù)為路由判據(jù)進(jìn)行路由選擇。由于高傳輸速率與有效的傳輸范圍之間存在固有的權(quán)衡，傳統(tǒng)路由傾向選擇長(zhǎng)距離低速率鏈路，且沒(méi)有考慮時(shí)變信道，造成部分鏈路不可用。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，TSLOT為一個(gè)物理時(shí)隙的大?。▽?duì)于物理層使用直接序列擴(kuò)頻技術(shù)DSSS而言，其值等于20μs）；Tcol為節(jié)點(diǎn)沖突時(shí)所經(jīng)歷的時(shí)間。在RTS／CTS機(jī)制和基本機(jī)制2種數(shù)據(jù)包傳輸方式下，可以分別得到：

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

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

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

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

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

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

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

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

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

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

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

MAC層采用802.11DCF機(jī)制，物理層使用802.11b。仿真場(chǎng)景設(shè)置為800m×800m的區(qū)域，隨機(jī)分配50個(gè)節(jié)點(diǎn)，仿真采用隨機(jī)?？糠绞健Ｃ總€(gè)節(jié)點(diǎn)隨機(jī)選擇鄰居節(jié)點(diǎn)發(fā)送UDP交通流量，每個(gè)節(jié)點(diǎn)的隊(duì)列長(zhǎng)度為8 000kb／s。通過(guò)設(shè)定UDP流的開(kāi)始時(shí)間來(lái)控制沖突概率，并不斷增加網(wǎng)絡(luò)流量負(fù)載來(lái)進(jìn)行比較。仿真時(shí)間為200s，IEEE 802.11所涉及的參數(shù)以及默認(rèn)值見(jià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ù)載較輕時(shí)，節(jié)點(diǎn)接入信道發(fā)生沖突概率較小，網(wǎng)絡(luò)飽和接收包隨網(wǎng)絡(luò)負(fù)載的增加而增加，3種判據(jù)下的分組投遞率均可達(dá)到90%以上。隨著網(wǎng)絡(luò)負(fù)載的增加，可看到min－MTM和min－DCB比min－h(huán)op有明顯提高。這是因?yàn)樵谙嗤磁c目的節(jié)點(diǎn)之間的路由，min－h(huán)op所選擇的路徑平均每跳之間的距離較長(zhǎng)，容易削弱信道強(qiáng)度，使丟包率增大，而 min－DCB和 min－MTM能夠選擇吞吐量高的鏈路。由于min－DCB兼顧高速率和信道繁忙程度，有時(shí)為了避開(kāi)選擇較繁忙的信道，會(huì)選擇速率較低鏈路，所以當(dāng)負(fù)載在500kb／s之前，min－DCB的分組投遞率比 min－MTM低。隨著網(wǎng)絡(luò)負(fù)載繼續(xù)增加，min－MTM會(huì)導(dǎo)致高速率鏈路局部擁塞，使網(wǎng)絡(luò)飽和接收包隨局部鏈路飽和而達(dá)到飽和。因此，min－DCB能均衡網(wǎng)絡(luò)負(fù)載，延長(zhǎng)網(wǎng)絡(luò)處于非飽和狀態(tài)的時(shí)間，其分組投遞率要比 min－h(huán)op提高了近25%，比min－MTM提高了5%。

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

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

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

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