Ａｄ ｈｏｃ網(wǎng)絡(luò)中一種新的基于預(yù)約調(diào)度和ＭＰＲ的媒體接入控制算法

摘要：提出了一種新的適用于Ad hoc網(wǎng)絡(luò)的媒體接入控制算法，該算法通過(guò)五次握手預(yù)約調(diào)度資源，利用節(jié)點(diǎn)底層的多包接收(MPR)能力，保證高概率的接入和提高并行傳輸率，從而提高網(wǎng)絡(luò)吞吐率。對(duì)算法進(jìn)行了理論分析和仿真，分析結(jié)果表明與FPRP相比，有效地提高了Ad hoc網(wǎng)絡(luò)的吞吐率。

關(guān)鍵詞：Ad hoc網(wǎng);媒體接入控制;多包接收

中圖分類(lèi)號(hào)：TN925.93

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1872－05

0引言

在多跳無(wú)線網(wǎng)絡(luò)中，鏈路層的主要功能是如何高效地接入無(wú)線信道，保障網(wǎng)絡(luò)的服務(wù)質(zhì)量(quality of service，QoS)。在傳統(tǒng)的方式下，主要由數(shù)據(jù)鏈路層的媒體接入控制子層來(lái)實(shí)現(xiàn)這一機(jī)制?？紤]在傳統(tǒng)的無(wú)線信道沖突模型中，物理層處理沖突數(shù)據(jù)包的方法就是丟棄，節(jié)點(diǎn)必須隨后進(jìn)行重傳。當(dāng)前信號(hào)處理技術(shù)的發(fā)展使得報(bào)文沖突能夠在物理層被解決，這種能力稱為物理層的多包接收(multi－packet reception，MPR)能力，節(jié)點(diǎn)能夠分辨出沖突的數(shù)據(jù)報(bào)文，它能明顯提高網(wǎng)絡(luò)的吞吐率。利用層間的交互協(xié)作才能更滿足苛刻的無(wú)線網(wǎng)絡(luò)環(huán)境，設(shè)計(jì)MAC層協(xié)議時(shí)充分考慮物理層的這種分辨沖突數(shù)據(jù)包的能力，以達(dá)到較好的網(wǎng)絡(luò)性能。

在無(wú)線信道的環(huán)境中，一方面存在噪聲和信道衰減；另一方面空間自由度又增加了分辨出沖突數(shù)據(jù)包的概率。典型的是在基于發(fā)射碼的CDMA系統(tǒng)中，接收節(jié)點(diǎn)能夠利用發(fā)送方的不同擴(kuò)頻碼在沖突的數(shù)據(jù)報(bào)文中解出正確的報(bào)文。在文獻(xiàn)[1]中，提出了一種在分時(shí)ALOHA系統(tǒng)中的MPR信道模型，一個(gè)節(jié)點(diǎn)的MPR能力被一個(gè)MPR矩陣所描述，矩陣中的元素 ck，n代表節(jié)點(diǎn)從收到的 k個(gè)報(bào)文中成功恢復(fù)出n個(gè)報(bào)文的概率。文獻(xiàn)[2]分析了擁有無(wú)窮個(gè)節(jié)點(diǎn)，但每個(gè)節(jié)點(diǎn)只有一個(gè)報(bào)文緩沖區(qū)的ALOHA系統(tǒng)的穩(wěn)定性。在文獻(xiàn)[3]中把文獻(xiàn)[1]中提出的MPR矩陣擴(kuò)展到了鏈路層，提出了鏈路層的接收矩陣模型。文獻(xiàn)[4]分析了一些特殊的網(wǎng)絡(luò)拓?fù)涞腁LOHA系統(tǒng)的穩(wěn)定性和網(wǎng)絡(luò)容量。文獻(xiàn)[5]給出了時(shí)隙ALOHA系統(tǒng)的吞吐量、容量和穩(wěn)定域的一般表達(dá)式。文獻(xiàn)[6，7]分別分析了MIMO(multiple－input multiple－output)和SIMO(single－input multiple－output)系統(tǒng)中，集中式的時(shí)隙ALOHA系統(tǒng)的性能，但是沒(méi)有屏蔽物理層的細(xì)節(jié)，鏈路層要用到物理層的一些具體調(diào)制方式等參數(shù)來(lái)描述。在文獻(xiàn)[8]中，提出了一種動(dòng)態(tài)序列的MAC協(xié)議，考慮收方的狀態(tài)多于發(fā)方，造成MPR能力不能完全利用。文獻(xiàn)[9]中提出一種混合CDMA－TDMA的MAC協(xié)議，采用為每個(gè)節(jié)點(diǎn)固定分配一個(gè)時(shí)隙的方法，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較多時(shí)，幀的長(zhǎng)度也相應(yīng)增加，效率不高且可擴(kuò)充性差。文獻(xiàn)[10]提出了一種基于IEEE 802.11DCF改進(jìn)的MAC協(xié)議，主要是收方接收?qǐng)?bào)文前根據(jù)自身的MPR能力來(lái)確定發(fā)送的節(jié)點(diǎn)個(gè)數(shù)，但是這種方式延遲了收方覆蓋范圍內(nèi)的暴露終端接入信道。由于時(shí)隙ALOHA和802.11都是基于競(jìng)爭(zhēng)的接入?yún)f(xié)議，競(jìng)爭(zhēng)接入?yún)f(xié)議在高負(fù)載的情況下都有較低的效率，MPR能力也不能被充分利用。

目前，典型的應(yīng)用于同步網(wǎng)絡(luò)的基于調(diào)度的MAC層協(xié)議有FPRP（five－phase reservation protocol）[11]、E(evolutionary)－TDMA[12]和RR－ALOHA[13]等。FPRP只是一個(gè)廣播調(diào)度協(xié)議，如果調(diào)度單播將導(dǎo)致其效率不高，而E－TDMA是基于FPRP改進(jìn)版本，它和FPRP一樣需要五次握手實(shí)現(xiàn)節(jié)點(diǎn)的接入。因此，該協(xié)議雖然能保證實(shí)時(shí)業(yè)務(wù)無(wú)沖突地發(fā)送，同時(shí)也能避免時(shí)延抖動(dòng)，但控制開(kāi)銷(xiāo)較大，實(shí)現(xiàn)復(fù)雜，效率不高。在RR－ALOHA中，每個(gè)節(jié)點(diǎn)都要求占用一個(gè)basic channel(BC)，因此網(wǎng)絡(luò)中每幀所包含的時(shí)隙數(shù)N應(yīng)大于網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，同樣當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較多時(shí)，效率不高且可擴(kuò)充性差。基于調(diào)度的MAC協(xié)議可以保證節(jié)點(diǎn)在預(yù)約成功的情況下無(wú)沖突地傳輸數(shù)據(jù)報(bào)文。其協(xié)議性能取決于預(yù)約算法的開(kāi)銷(xiāo)，可以實(shí)現(xiàn)QoS保障，結(jié)合物理層的MPR能力來(lái)跨層設(shè)計(jì)基于調(diào)度的MAC協(xié)議能夠提高和優(yōu)化系統(tǒng)的性能。

1多包接收

無(wú)線環(huán)境中的節(jié)點(diǎn)使用的是共享信道，因此它們的傳輸將互相影響，并且還將受到環(huán)境噪聲干擾。如果一個(gè)節(jié)點(diǎn)能夠從多個(gè)發(fā)送者的發(fā)出信號(hào)中正確地恢復(fù)報(bào)文。這個(gè)節(jié)點(diǎn)就稱為MPR節(jié)點(diǎn)[14]。

文獻(xiàn)[1]中提出了多包接收的思想，指出在一個(gè)分時(shí)網(wǎng)絡(luò)中，節(jié)點(diǎn)能夠通過(guò)信號(hào)處理的辦法，分辨出沖突的數(shù)據(jù)報(bào)文，其節(jié)點(diǎn)的分辨沖突數(shù)據(jù)報(bào)文的能力由接收MPR矩陣C來(lái)描述，如式(1)的左邊所示。其中：元素 ck，n代表節(jié)點(diǎn)從收到的 k個(gè)報(bào)文中成功恢復(fù)出n個(gè)報(bào)文的概率。

由于無(wú)線環(huán)境是一個(gè)廣播的信道，節(jié)點(diǎn)的數(shù)據(jù)鏈路層收到的數(shù)據(jù)報(bào)文不一定是發(fā)給本節(jié)點(diǎn)的數(shù)據(jù)報(bào)文，但是這些報(bào)文同樣要占用節(jié)點(diǎn)的帶寬。文獻(xiàn)[3]中將節(jié)點(diǎn)的接收矩陣C擴(kuò)展成了網(wǎng)絡(luò)鏈路層的接收矩陣R，如式(1)的右邊所示。其中：元素rL，n代表節(jié)點(diǎn)從收到的L個(gè)報(bào)文中成功恢復(fù)出屬于本節(jié)點(diǎn)的n個(gè)報(bào)文的概率。于是rL，n是由 ck，n定義的函數(shù)，具體參見(jiàn)文獻(xiàn)[3]。

由此可以定義η維的沖突信道 Cη[4]，在 Cη信道中，能夠正確接收不大于 η個(gè)的數(shù)據(jù)報(bào)文，如果有大于 η個(gè)的數(shù)據(jù)報(bào)文傳輸，全部數(shù)據(jù)報(bào)文均不能正確接收。為了簡(jiǎn)化分析，考慮屏蔽物理層實(shí)現(xiàn)MPR的細(xì)節(jié)，對(duì)于鏈路層認(rèn)為節(jié)點(diǎn)的多包接收能力是一樣，即是具有相同的多包接收矩陣。更進(jìn)一步地表示每個(gè)節(jié)點(diǎn)的多包接收能力為 Ck。定義Ck=∑kn=1nCk，n，其物理含義是當(dāng)節(jié)點(diǎn)偵聽(tīng)到 k個(gè)數(shù)據(jù)報(bào)文時(shí)，節(jié)點(diǎn)成功接收?qǐng)?bào)文數(shù)目的期望值?？紤]在 η維的沖突信道Cη中實(shí)現(xiàn)，則Ck=k，k＜ηη，k=η0，k＞η。

在實(shí)際系統(tǒng)中，如考慮一個(gè)擁有 η個(gè)碼字的CDMA系統(tǒng)，在同步且不考慮遠(yuǎn)近效應(yīng)等干擾的情況下，節(jié)點(diǎn)總是能夠從收到的不大于 η個(gè)報(bào)文中成功恢復(fù)出數(shù)據(jù)報(bào)文，當(dāng)然這里要求每個(gè)報(bào)文使用一個(gè)碼字且節(jié)點(diǎn)收到的報(bào)文中沒(méi)有碼字是重復(fù)的。所以這種假設(shè)應(yīng)該是合理且能夠?qū)崿F(xiàn)的。

2算法描述

本文所設(shè)計(jì)的協(xié)議適用于全網(wǎng)同步劃分時(shí)隙的多跳無(wú)線網(wǎng)絡(luò)。系統(tǒng)同步可以有兩種實(shí)現(xiàn)方式：a)通過(guò)GPS接收機(jī)從空間取得的高精度的頻率標(biāo)準(zhǔn)與受控時(shí)鐘相配合，節(jié)點(diǎn)可以獲得與世界協(xié)調(diào)時(shí)（UTC）為參照的時(shí)間基準(zhǔn)的時(shí)間同步。b)通過(guò)自校時(shí)的方式，實(shí)現(xiàn)一定精度的時(shí)鐘同步。另一方面FPRP是一種通過(guò)五次握手完成兩跳范圍內(nèi)高概率、無(wú)沖突的分布式預(yù)約調(diào)度機(jī)制。本文所設(shè)計(jì)的協(xié)議的預(yù)約調(diào)度就是參考和借鑒了FPRP的五次握手思想，利用這種握手算法保證高概率的接入，交互節(jié)點(diǎn)的MPR能力，以提高網(wǎng)絡(luò)的吞吐率。

2．1信道劃分

無(wú)線網(wǎng)絡(luò)發(fā)展之初受到硬件和軟件環(huán)境的限制，主要是使用單信道，由此而發(fā)展出了一批典型的有實(shí)用價(jià)值的MAC協(xié)議，在民用領(lǐng)域使用最廣泛的就是IEEE的802.11系列。但是單信道無(wú)法完全解決隱藏終端和暴露終端問(wèn)題，并且QoS保障困難，所以后來(lái)的MAC協(xié)議均向著多信道方向進(jìn)行發(fā)展。實(shí)現(xiàn)多信道的方式有多種辦法，當(dāng)解決了全網(wǎng)同步時(shí)，TDMA以硬件實(shí)現(xiàn)簡(jiǎn)單成為一種有效的劃分方式。

本文所設(shè)計(jì)的協(xié)議把信道劃分為一個(gè)個(gè)時(shí)幀，每個(gè)時(shí)幀都是一次獨(dú)立的信道預(yù)約和數(shù)據(jù)傳送過(guò)程。如圖1 ，每個(gè)時(shí)幀又分為一個(gè)控制信道和業(yè)務(wù)信道，每個(gè)業(yè)務(wù)信道分為K個(gè)信息幀，每個(gè)信息幀又分為N個(gè)信息時(shí)隙；每個(gè)控制信道是一次預(yù)約過(guò)程，預(yù)約過(guò)程分為N個(gè)預(yù)約時(shí)隙，分別預(yù)約對(duì)應(yīng)序號(hào)的業(yè)務(wù)時(shí)隙，每一次成功的預(yù)約將使其占用其后業(yè)務(wù)信道中序號(hào)相同的K個(gè)信息時(shí)隙，而每個(gè)預(yù)約時(shí)隙包含M次相同的五次握手的預(yù)約周期，主要目的是解決暴露終端問(wèn)題，讓網(wǎng)絡(luò)承載更多的并行傳輸。

2．2協(xié)議的工作方式

基于多信道的自組網(wǎng)MAC協(xié)議用于具有多個(gè)信道的自組網(wǎng)絡(luò)，主要研究信道分配和接入控制兩個(gè)方面的內(nèi)容。前者負(fù)責(zé)為通信節(jié)點(diǎn)對(duì)分配相應(yīng)的信道，使盡量多的節(jié)點(diǎn)可以無(wú)沖突地同時(shí)通信；后者負(fù)責(zé)確定節(jié)點(diǎn)接入信道的時(shí)機(jī)、沖突的避免和解決方式。本文的MAC協(xié)議主要實(shí)現(xiàn)上述兩種功能，而TDMA系統(tǒng)中的信道分配就是為網(wǎng)絡(luò)中的節(jié)點(diǎn)分配發(fā)送時(shí)隙，實(shí)現(xiàn)相鄰節(jié)點(diǎn)之間分組的無(wú)碰撞傳送，獲得盡可能高的無(wú)線信道的利用率和空分重用，接入控制主要采用多次握手預(yù)約方式。

FPRP預(yù)約方式是專(zhuān)門(mén)針對(duì)廣播的調(diào)度式接入?yún)f(xié)議，通過(guò)五次握手過(guò)程實(shí)現(xiàn)時(shí)隙的預(yù)留。本文所設(shè)計(jì)的協(xié)議在采納了FPRP的五次握手思想，通過(guò)五次握手使其能夠預(yù)約單播、組播和廣播，其預(yù)留過(guò)程只涉及其兩跳范圍內(nèi)的站點(diǎn)，是一個(gè)本地過(guò)程，能夠支持信道在空間上的重用。其算法主要步驟為：

a)預(yù)約請(qǐng)求階段(reservation request phase，RR)。在該階段中，當(dāng)節(jié)點(diǎn)緩沖區(qū)內(nèi)有滿足激活預(yù)約條件的數(shù)據(jù)報(bào)文時(shí)，節(jié)點(diǎn)需要預(yù)約資源。此時(shí)節(jié)點(diǎn)以接入概率 PRR向一跳鄰節(jié)點(diǎn)廣播一個(gè)預(yù)約請(qǐng)求RR分組。在RR分組中必須包括發(fā)送節(jié)點(diǎn)的ID和K個(gè)數(shù)據(jù)報(bào)文的目的節(jié)點(diǎn)的ID，不需要進(jìn)行資源預(yù)約的節(jié)點(diǎn)在該階段進(jìn)行偵聽(tīng)。假設(shè)節(jié)點(diǎn)均具有MPR能力，節(jié)點(diǎn)可能從鄰居節(jié)點(diǎn)那里收不到RR分組，也可能會(huì)收到一個(gè)或多個(gè)RR分組。當(dāng)有多個(gè)RR分組到達(dá)且正確接收后，節(jié)點(diǎn)將在自己的接收緩沖區(qū)緩沖這些報(bào)文。發(fā)送RR分組的節(jié)點(diǎn)在協(xié)議中稱為預(yù)約節(jié)點(diǎn)(reservation node，RN)。如果非預(yù)約節(jié)點(diǎn)在這個(gè)階段偵聽(tīng)到超過(guò) η個(gè)RR報(bào)文，則非預(yù)約節(jié)點(diǎn)一個(gè)報(bào)文均不能正確恢復(fù)，當(dāng)前預(yù)約循環(huán)被浪費(fèi)，節(jié)點(diǎn)只能在下一次預(yù)約循送發(fā)送RR報(bào)文。

b)傳輸報(bào)告階段(transmission report phase，TR)。如果非預(yù)約節(jié)點(diǎn)在階段l收到兩個(gè)或兩個(gè)以上的預(yù)約請(qǐng)求分組，則節(jié)點(diǎn)就知道在該預(yù)約周期中有多個(gè)預(yù)約節(jié)點(diǎn)同時(shí)進(jìn)行競(jìng)爭(zhēng)預(yù)約，于是節(jié)點(diǎn)在階段2根據(jù)收到的RR分組進(jìn)行判斷如何回復(fù)傳輸報(bào)告TR分組。這時(shí)節(jié)點(diǎn)根據(jù)接收到的單個(gè)或多個(gè)RR報(bào)文的目的地址ID統(tǒng)計(jì)這些數(shù)據(jù)報(bào)文的目的節(jié)點(diǎn)。非預(yù)約節(jié)點(diǎn)將查看節(jié)點(diǎn)接收時(shí)隙表，如表1所示。

節(jié)點(diǎn)接收時(shí)隙表每個(gè)時(shí)幀更新一次。其中記錄了節(jié)點(diǎn)的ID號(hào)、每個(gè)節(jié)點(diǎn)當(dāng)前時(shí)隙預(yù)約成功的鄰居節(jié)點(diǎn)ID號(hào)。當(dāng)節(jié)點(diǎn)接收到超過(guò)η個(gè)數(shù)據(jù)報(bào)文時(shí)，所有報(bào)文均不能正確接收，所以采用比較保守方式，即節(jié)點(diǎn)要保證屬于本節(jié)點(diǎn)和屬于鄰居節(jié)點(diǎn)的數(shù)據(jù)報(bào)文總數(shù)不能超過(guò)η個(gè)，則每個(gè)時(shí)隙最多只能有η個(gè)鄰居節(jié)點(diǎn)預(yù)約成功，所以接收時(shí)隙表構(gòu)成一個(gè)η×N的矩陣。當(dāng)節(jié)點(diǎn)在某個(gè)時(shí)隙處于發(fā)送狀態(tài)且預(yù)約成功時(shí)，其對(duì)應(yīng)的接收時(shí)隙表的列為空。

這時(shí)非預(yù)約節(jié)點(diǎn)將計(jì)算已經(jīng)預(yù)約成功而占用的MPR能力和當(dāng)前的RR報(bào)文中的目的地址數(shù)之和，當(dāng)這個(gè)結(jié)果超過(guò)η時(shí)，則丟棄多余的RR報(bào)文。丟棄的算法是先丟棄緊急業(yè)務(wù)和實(shí)時(shí)業(yè)務(wù)較少的預(yù)約節(jié)點(diǎn)的RR報(bào)文。如果剩余的預(yù)約節(jié)點(diǎn)個(gè)數(shù)和非預(yù)約節(jié)點(diǎn)被占用的MPR能力之和還超過(guò)η，則隨機(jī)丟棄其中部分RR報(bào)文，保證當(dāng)前時(shí)隙最大只有η個(gè)預(yù)約節(jié)點(diǎn)。這時(shí)非預(yù)約節(jié)點(diǎn)廣播一個(gè)傳輸報(bào)告TR分組。其中包含本次保留的RR報(bào)文的源節(jié)點(diǎn)ID。通過(guò)在該階段對(duì)TR的偵聽(tīng)，RN判斷它的RR是否被非預(yù)約節(jié)點(diǎn)接納。如果接收到TR，且TR中包含自己的ID，RN認(rèn)為它所發(fā)送的RR被非預(yù)約鄰節(jié)點(diǎn)正確接收。這樣，一個(gè)RN節(jié)點(diǎn)就變成了一個(gè)傳遞節(jié)點(diǎn)(transmission node，TN)，在下面的預(yù)約證實(shí)階段就可以預(yù)約時(shí)隙。很明顯，RR/TR交互消除了MPR節(jié)點(diǎn)的隱藏終端問(wèn)題。

如果RN沒(méi)有相連節(jié)點(diǎn)，它就收不到傳輸報(bào)告分組，由此就可以知道RN是一孤立節(jié)點(diǎn)，RN就沒(méi)必要進(jìn)行信息的發(fā)送。

c)預(yù)約證實(shí)階段(reservation confirmation phase，RC)。在這個(gè)階段中，子廣播一個(gè)預(yù)約證實(shí)RC分組通知一跳鄰節(jié)點(diǎn)相應(yīng)的時(shí)隙被預(yù)約，每一個(gè)正確接收到這個(gè)RC的一跳鄰節(jié)點(diǎn)均知道了該時(shí)隙已被預(yù)約，非傳輸節(jié)點(diǎn)將更新自己的接收時(shí)隙表，它們將在接收時(shí)隙表的相應(yīng)時(shí)隙中加上RC分組的源節(jié)點(diǎn)ID。

d)預(yù)約否認(rèn)/確認(rèn)階段(reservation negative/acknowledgement phase，RNA)。收到預(yù)約證實(shí)RC分組的非傳輸節(jié)點(diǎn)將檢查自己的接收時(shí)隙表，因?yàn)檫@時(shí)預(yù)約的節(jié)點(diǎn)個(gè)數(shù)有可能超過(guò)η個(gè)節(jié)點(diǎn)。如果超過(guò)η個(gè)節(jié)點(diǎn)，非傳輸節(jié)點(diǎn)將發(fā)送RNA分組，分組中包含對(duì)超過(guò)部分的節(jié)點(diǎn)本次預(yù)約的否認(rèn)和對(duì)未超過(guò)的部分節(jié)點(diǎn)本次預(yù)約的確認(rèn)；如果未超過(guò)η個(gè)節(jié)點(diǎn)，則RNA分組中只有對(duì)未超過(guò)的部分節(jié)點(diǎn)本次預(yù)約的確認(rèn)。其中的確認(rèn)部分將通知TN及TN的兩跳鄰節(jié)點(diǎn)，從而使兩跳鄰節(jié)點(diǎn)知道兩跳遠(yuǎn)處有節(jié)點(diǎn)預(yù)約資源成功。

e)填充階段(packing phase，PP)。在該階段中，TN節(jié)點(diǎn)將根據(jù)收到的RNA分組更新自己的發(fā)送調(diào)度。如果被否認(rèn)則不會(huì)在對(duì)應(yīng)時(shí)隙發(fā)送數(shù)據(jù)報(bào)文，節(jié)點(diǎn)將競(jìng)爭(zhēng)下一次預(yù)約循環(huán)。這時(shí)TN的兩跳節(jié)點(diǎn)將根據(jù)收到的RNA分組發(fā)送PP(packing packet)報(bào)文，PP報(bào)文中包含本時(shí)隙成功預(yù)約節(jié)點(diǎn)的ID、收到PP的節(jié)點(diǎn)，因此知道三跳遠(yuǎn)的節(jié)點(diǎn)預(yù)約成功。相應(yīng)地，部分節(jié)點(diǎn)將消耗一部分MPR能力。利用這一點(diǎn)可相應(yīng)提高三跳鄰節(jié)點(diǎn)的接入概率PRR，增加距離TN三跳遠(yuǎn)節(jié)點(diǎn)的預(yù)約成功率，加快預(yù)約收斂速度。

經(jīng)過(guò)上述的一個(gè)完整預(yù)約過(guò)程后，節(jié)點(diǎn)的可能狀態(tài)為：一跳鄰節(jié)點(diǎn)的狀態(tài)為接收狀態(tài)；預(yù)約成功的節(jié)點(diǎn)為傳遞狀態(tài)，兩跳節(jié)點(diǎn)如果通過(guò)MPR檢測(cè)的也將處于傳遞狀態(tài)。其余節(jié)點(diǎn)的狀態(tài)為空閑狀態(tài)。只有處于傳遞狀態(tài)的節(jié)點(diǎn)才能在相應(yīng)的信息時(shí)隙里進(jìn)行數(shù)據(jù)傳送。

3算法性能

在集中式的無(wú)線通信系統(tǒng)中，基站節(jié)點(diǎn)的MPR能力和網(wǎng)絡(luò)的MPR有一一對(duì)應(yīng)的關(guān)系。因?yàn)樗械木W(wǎng)絡(luò)負(fù)載都要通過(guò)基站且基站接收到的報(bào)文都是屬于它的。但是在多跳無(wú)線網(wǎng)中通常不是這樣，即使節(jié)點(diǎn)成功接收到多個(gè)報(bào)文，其中一部分很可能不是屬于這個(gè)節(jié)點(diǎn)的。所以要計(jì)算網(wǎng)絡(luò)的吞吐率，必須考慮鏈路層的MPR矩陣。本文所設(shè)計(jì)的協(xié)議采用了FPRP五次握手的思想，F(xiàn)PRP在同步網(wǎng)絡(luò)中通過(guò)節(jié)點(diǎn)間的競(jìng)爭(zhēng)能夠?qū)崿F(xiàn)全分布式的信道接入控制。通過(guò)仿真表明，可應(yīng)用于各種規(guī)模的移動(dòng)自組織網(wǎng)絡(luò)，節(jié)點(diǎn)的預(yù)約過(guò)程收斂快速、穩(wěn)定[15]。為了簡(jiǎn)化分析，研究MAC接入算法主要是計(jì)算協(xié)議的吞吐率，且需要一些事先的假設(shè)。這些假設(shè)建立在收斂采用FPRP協(xié)議的網(wǎng)絡(luò)之上。本文假定下面幾種情況：

a)每個(gè)節(jié)點(diǎn)的上層獨(dú)立產(chǎn)生報(bào)文，節(jié)點(diǎn)的報(bào)文緩沖區(qū)大小恰好為信息幀的長(zhǎng)度K，且節(jié)點(diǎn)始終有數(shù)據(jù)報(bào)文要發(fā)送，考慮在飽和情況下的網(wǎng)絡(luò)性能；

b)忽略噪聲，接收?qǐng)?bào)文中的誤碼主要來(lái)自多址接入的干擾(multiple－access interference， MAI)；

c)五次握手FPRP的性能較好，經(jīng)過(guò)M次循環(huán)后，節(jié)點(diǎn)能夠高概率地接入信道；

d)每個(gè)節(jié)點(diǎn)都是以相等的概率向它的鄰居發(fā)送報(bào)文；

e)網(wǎng)絡(luò)中的節(jié)點(diǎn)均勻分布。

設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)總個(gè)數(shù)為Node_num，全體節(jié)點(diǎn)分布的總面積是S，節(jié)點(diǎn)的通信半徑為R，則節(jié)點(diǎn)的密度為λ=Node_num/S，且節(jié)點(diǎn)之間通信采用雙向信道。節(jié)點(diǎn)的多包接收能力考慮η維的沖突信道 Cη，則節(jié)點(diǎn)成功接收?qǐng)?bào)文數(shù)目的期望值Ck=∑kn=1nCk，n。設(shè)每個(gè)FPRP的小時(shí)隙長(zhǎng)度為ls_slot_size，單位是bit；設(shè)報(bào)文長(zhǎng)度為ldata，單位是bit；設(shè)網(wǎng)絡(luò)的吞吐率為T(mén)h，單位是bps；設(shè)節(jié)點(diǎn)發(fā)送RR報(bào)文的概率為PRR；設(shè)節(jié)點(diǎn)底層信道速率為Vdata_rate，單位是bps。假設(shè)網(wǎng)絡(luò)只考察MAC協(xié)議的性能，即主要考慮單跳鄰居之間的通信，并且假設(shè)某個(gè)節(jié)點(diǎn)前后兩次預(yù)約信道是獨(dú)立的，每次是否參與預(yù)約信道只受自己緩沖區(qū)是否有數(shù)據(jù)待發(fā)決定，所以可以將上層遞交給下層的數(shù)據(jù)報(bào)文的目的地址在鄰居節(jié)點(diǎn)中等概率產(chǎn)生，并且每發(fā)送Des個(gè)報(bào)文就轉(zhuǎn)換一次目的地址。

考慮一個(gè)普通節(jié)點(diǎn)A，其鄰居個(gè)數(shù)設(shè)為N(A)，則N(A)的平均值可以記為N(A)=λπR2-1；考慮節(jié)點(diǎn)A的某個(gè)鄰居節(jié)點(diǎn)緩沖區(qū)內(nèi)待發(fā)送的K個(gè)數(shù)據(jù)報(bào)文，定義這K個(gè)數(shù)據(jù)報(bào)文的目的地址域包含A的概率為PA(K，Des)，則

式(3)中[·]表示取整函數(shù)。

假設(shè)節(jié)點(diǎn)A及其鄰居處在某個(gè)時(shí)幀的第一個(gè)時(shí)隙的預(yù)留循環(huán)的第一次預(yù)留循環(huán)中，節(jié)點(diǎn)總是有數(shù)據(jù)待發(fā)，考察節(jié)點(diǎn)A此時(shí)的飽和吞吐率。

很明顯從網(wǎng)絡(luò)的吞吐率公式上看，Th是五次握手的FPRP的時(shí)幀參數(shù)N、K、M的函數(shù)，式(7)是在假設(shè)FPRP性能很好的情況下得出的結(jié)果，Th函數(shù)的非線性的復(fù)雜函數(shù)。通過(guò)解析的方法求出極值比較困難，所以通過(guò)仿真驗(yàn)證網(wǎng)絡(luò)的吞吐率。

4仿真結(jié)果

本文所設(shè)計(jì)的協(xié)議采用OPNET仿真平臺(tái)實(shí)現(xiàn)，并對(duì)協(xié)議性能作了分析。吞吐率是表征MAC層為上層所提供的通信性能的重要指標(biāo)，因此協(xié)議將仿真結(jié)果中的吞吐率與式(7)所計(jì)算出的飽和吞吐率進(jìn)行對(duì)比，以得出網(wǎng)絡(luò)中的參數(shù)N、K、M、Des和PRR應(yīng)該如何設(shè)置，才能逼近飽和吞吐率。另一方面底層所提供的MPR能力是由系統(tǒng)事先決定的，所以參數(shù)η在仿真中取固定值。

文獻(xiàn)[11]仿真結(jié)果表明，在Node_num=100，分布總面積為S=10×10單位面積，節(jié)點(diǎn)通信半徑R=1．5單位長(zhǎng)度的網(wǎng)絡(luò)拓?fù)湎?，為N=16個(gè)時(shí)隙分配通信任務(wù)時(shí)，最多只需要M=9次預(yù)約循環(huán)就可以以高于99％的概率為節(jié)點(diǎn)成功分配時(shí)隙。參照文獻(xiàn)[11]中的方式，為每個(gè)單位面積平均分配一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)通信距離是單位長(zhǎng)度的1.5倍，在仿真環(huán)境中設(shè)置了49個(gè)節(jié)點(diǎn)，均勻分布在700×700 m2的范圍內(nèi)，每個(gè)節(jié)點(diǎn)的傳輸范圍為150 m；上層業(yè)務(wù)發(fā)送報(bào)文模塊為100 packets/s，目的節(jié)點(diǎn)均勻分布到鄰居節(jié)點(diǎn)，報(bào)文長(zhǎng)度為1 024 bit；底層物理信道速率為1 Mbps；節(jié)點(diǎn)隨機(jī)移動(dòng)，移動(dòng)速率為25 m/s；假設(shè)節(jié)點(diǎn)的MPR能力的參數(shù)η=5，每個(gè)時(shí)幀包含的時(shí)隙數(shù)N取固定值；仿真時(shí)長(zhǎng)為30 s。經(jīng)過(guò)多次仿真得到不同參數(shù)下的吞吐率。其中：theory代表理論計(jì)算的吞吐率；而result代表實(shí)際仿真結(jié)果得出的吞吐率。

從圖2、3的吞吐率仿真結(jié)果可以看出，吞吐率的理論值隨著信息幀長(zhǎng)度K的增大而增大，而隨著M的增大而減小，這主要是因?yàn)槔碚撝档耐茖?dǎo)是建立在FPRP性能很好、能夠高概率地將節(jié)點(diǎn)預(yù)約到資源假設(shè)之上，而K的增大使得每個(gè)時(shí)幀傳輸?shù)男畔⒘吭龃?，借助于?jié)點(diǎn)的MPR能力，吞吐率將增大，而M的增大將使每個(gè)時(shí)幀的控制信道部分開(kāi)銷(xiāo)增大，因而吞吐率下降。另一方面仿真結(jié)果中的吞吐率都是在M=8時(shí)取得最大吞吐率，說(shuō)明協(xié)議在M=8附近時(shí)達(dá)到一個(gè)平衡，協(xié)議開(kāi)銷(xiāo)和協(xié)議預(yù)約資源成功率之間的平衡。仿真結(jié)果與理論吞吐率之間的偏離最大沒(méi)有超過(guò)15％，并且均是出現(xiàn)在M=6時(shí)，說(shuō)明在節(jié)點(diǎn)能夠充分預(yù)約到資源時(shí)，式（7）能夠估計(jì)和計(jì)算出網(wǎng)絡(luò)的吞吐率。從圖3、4的仿真結(jié)果綜合可以看出，在Des=K時(shí)，協(xié)議性能比較好，此時(shí)緩沖區(qū)內(nèi)的報(bào)文均是指向同一目的地址，協(xié)議開(kāi)銷(xiāo)較小，因此吞吐率能夠得到提高。 圖5中比較了帶有MPR能力的MAC協(xié)議與傳統(tǒng)的FPRP在相同仿真場(chǎng)景下的吞吐率。在網(wǎng)絡(luò)負(fù)載飽和的情況下，考慮不同的信息幀長(zhǎng)度K和不同的目的地址轉(zhuǎn)換頻率Des，帶MPR能力的MAC協(xié)議的吞吐率均較FPRP的吞吐率平均有25％左右的提升。

5結(jié)束語(yǔ)

本文提出了一種在無(wú)線Ad hoc網(wǎng)絡(luò)中，基于多包接收的媒體接入控制算法。本算法通過(guò)節(jié)點(diǎn)之間的五次握手，交互地利用節(jié)點(diǎn)的MPR能力，用于保證高概率地接入，提高網(wǎng)絡(luò)數(shù)據(jù)報(bào)文的并行傳輸。通過(guò)理論和仿真結(jié)果的比較可以發(fā)現(xiàn)，利用底層的多包接收能力，本文所提出的算法能夠獲得比FPRP更大的網(wǎng)絡(luò)吞吐率。

參考文獻(xiàn):

［1］GHEZ S， VERDU S， SCHWARTZ S C.Stability properties of slotted ALOHA with multipacket reception capability[J]. Automatic Control， 1988，33(7):640－649.

［2］GHEZ S， VERDU S， SCHWARTZ S C. Optimal decentralized control in the random access multipacket channel[J].Automatic Control， 1989， 34(11):1153－1163.

［3］BAO J Q， TONG Lang. A performance comparison between Ad hoc and centrally controlled CDMA wireless LANs[J].Wireless Communications， 2002， 1（4）:829－841.

［4］MERGEN G， TONG Lang. Stability and capacity of regular wireless networks[J]. Information Theory， 2005，51(6):1938－1953.

［5］LUO Jie， EPHREMIDES A. On the throughput，capacity，and stabi－lity regions of random multiple access[J].Information Theory， 2006，52(6):2593－2607.

［6］PAN Cheng－kang，CAI Yue－ming，XU You－yun. Multipacket reception in MIMO－OFDM systems[C] //Proc of Communications and Information Technology. 2005: 1156－1159.

［7］PAN Cheng－kang， CAI Yue－ming， XU You－yun. Multipacket reception in SIMO－OFDM systems[C] //Proc of Vehicular Technology Conference. [S.l.]: Springer， 2006:1536－1540.

［8］ZHAO Qing，LONG Tang. Amultiqueueservice room MAC protocol for wireless networks with multipacket reception[J].IEEE/ACM Trans on Networking，2003，11(1):125－137.

［9］REALP M， PEREZ－NEIRA A I. Decentralized multiaccess MAC protocol for Ad hoc networks[C] //Proc of the 14th Personal， Indoor and Mobile Radio Communications. 2003:1634－1638.

［10］許力. 無(wú)線Ad hoc環(huán)境下基于跨層設(shè)計(jì)和多包接收的媒體接入控制算法[J]. 計(jì)算機(jī)應(yīng)用， 2005， 25(6): 1227－1229.

［11］ZHU Chen－xi， CORSON M S. A five－phase reservation protocol (FPRP) for mobile Ad hoc networks[C] //Proc of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies. 1998:322－331.

［12］ZHU Chen－xi， CORSON M S. An evolutionary－TDMA scheduling protocol(E－TDMA) for mobile Ad hoc networks， ISR CSHCN TR 98－14[R]. Maryland: [s.n.]， 2001.

［13］BORGONOVO F， CAPONE A， CESANA M， et al. RR－ALOHA， areliable R－ALOHA broadcast channel for Adhoc inter－vehicle communication networks[C] //Proc of Med－Hoc－Net. 2002.

［14］TONG Lang， ZHAO Qing， MERGEN G. Multipacket reception in random access wireless networks: from signal processing to optimal medium access control[J].Communications Magazine， 2001， 39(11):108－112.

［15］于宏毅. 無(wú)線移動(dòng)自組織網(wǎng)[M].北京:人民郵電出版社， 2005:97－102.

［16］BERTSEKAS D， GALLAGER R. Data networks[M].2nd ed.[S.l.]: Prentice Hall，1992:304－310.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文