高效的動(dòng)態(tài)按需時(shí)隙分配協(xié)議

李楊，韓志韌

(1.哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001;2.武漢船舶通信研究所，湖北武漢430079)

海上無(wú)線自組網(wǎng)是一種具有高度動(dòng)態(tài)特性的網(wǎng)絡(luò).在網(wǎng)絡(luò)運(yùn)行過(guò)程中，如網(wǎng)絡(luò)規(guī)模、拓?fù)浣Y(jié)構(gòu)等各種直接影響網(wǎng)絡(luò)性能的因素隨時(shí)會(huì)發(fā)生變化.因而要求適用于海上無(wú)線自組網(wǎng)的MAC層協(xié)議必須能夠適應(yīng)網(wǎng)絡(luò)的各種變化，并保持相對(duì)穩(wěn)定的性能.

以TDMA(time division maltiple access)為基礎(chǔ)的分配類(lèi)MAC層協(xié)議具有性能穩(wěn)定、可靠，平均傳輸時(shí)延等QoS指標(biāo)可控、便于管理等特點(diǎn)，近年來(lái)在對(duì)MANET(mobile Ad Hoc networks)的相關(guān)研究中受到廣泛的關(guān)注.其核心問(wèn)題是如何有效地為各節(jié)點(diǎn)分配時(shí)隙資源.針對(duì)該問(wèn)題，文獻(xiàn)[1-5]采用集中式的染色算法完成網(wǎng)內(nèi)對(duì)節(jié)點(diǎn)或鏈路的時(shí)隙分配，該算法必須首先獲得節(jié)點(diǎn)2～3跳范圍內(nèi)其他節(jié)點(diǎn)的拓?fù)浜蜖顟B(tài)信息，增加了協(xié)議的開(kāi)銷(xiāo)和復(fù)雜度.以FPRP(five-phase reservation protocol)為代表的動(dòng)態(tài)競(jìng)爭(zhēng)類(lèi)時(shí)隙分配協(xié)議[6-11]通過(guò)簡(jiǎn)單而可靠的握手機(jī)制與鄰居節(jié)點(diǎn)協(xié)調(diào)預(yù)留時(shí)隙資源，但此類(lèi)協(xié)議均以平均分配為原則，并沒(méi)有根據(jù)實(shí)際業(yè)務(wù)負(fù)載情況對(duì)有限的時(shí)隙資源進(jìn)行按需分配.文獻(xiàn)[11]提出一種新的ODSA(on-demand and dynamic slot assign-ment)協(xié)議，以按需的策略動(dòng)態(tài)分配時(shí)隙，改善了網(wǎng)絡(luò)效率，但引入了一定的協(xié)議開(kāi)銷(xiāo).文獻(xiàn)[12]提出采用動(dòng)態(tài)調(diào)整時(shí)幀長(zhǎng)度的方法匹配當(dāng)前業(yè)務(wù)量，具有一定的理論價(jià)值.

針對(duì)時(shí)隙分配中的預(yù)留沖突和網(wǎng)絡(luò)效率較低的問(wèn)題提出了一種新的動(dòng)態(tài)競(jìng)爭(zhēng)類(lèi)時(shí)隙分配協(xié)議，即按需隨機(jī)時(shí)隙分配協(xié)議(DRSA).該協(xié)議在時(shí)隙競(jìng)爭(zhēng)過(guò)程中采用全新的隨機(jī)化競(jìng)爭(zhēng)策略，可以有效減小競(jìng)爭(zhēng)分配過(guò)程中的碰撞概率.同時(shí)，本協(xié)議還能夠根據(jù)當(dāng)前業(yè)務(wù)量需求和拓?fù)淝闆r靈活地為網(wǎng)絡(luò)節(jié)點(diǎn)分配時(shí)隙資源，以適應(yīng)網(wǎng)絡(luò)及業(yè)務(wù)的變化，提高網(wǎng)絡(luò)效率.

1 DRSA協(xié)議設(shè)計(jì)

在典型的海上無(wú)線自組網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)節(jié)點(diǎn)通常具有較強(qiáng)的移動(dòng)性，因而導(dǎo)致網(wǎng)絡(luò)規(guī)模、節(jié)點(diǎn)分布密度、拓?fù)浣Y(jié)構(gòu)等網(wǎng)絡(luò)參數(shù)變化較快.其次，平臺(tái)上需要承載各種不同類(lèi)型的數(shù)據(jù)業(yè)務(wù)，導(dǎo)致網(wǎng)絡(luò)中業(yè)務(wù)負(fù)載的分布情況差異較大.為適應(yīng)海上自組網(wǎng)的特點(diǎn)，DRSA協(xié)議主要采用動(dòng)態(tài)競(jìng)爭(zhēng)的時(shí)隙分配策略，根據(jù)業(yè)務(wù)量的負(fù)載情況動(dòng)態(tài)地為各節(jié)點(diǎn)分配所需時(shí)隙資源，同時(shí)采用全新的按需跳躍預(yù)留算法(on-demand hop slot reservation，ODHR)有效地提高了時(shí)隙分配的效率和有效性.協(xié)議默認(rèn)全網(wǎng)時(shí)間同步.

1.1 協(xié)議幀結(jié)構(gòu)

DRSA協(xié)議幀格式如圖1所示.在DRSA協(xié)議中，基本的周期性時(shí)間單位為時(shí)元.時(shí)元內(nèi)包含1個(gè)競(jìng)爭(zhēng)幀和若干個(gè)信息幀，其中信息幀的個(gè)數(shù)可根據(jù)需要進(jìn)行裁剪.每個(gè)信息幀可分為N個(gè)信息時(shí)隙，分配給不同網(wǎng)絡(luò)節(jié)點(diǎn)用于傳輸數(shù)據(jù).競(jìng)爭(zhēng)幀可分為M個(gè)競(jìng)爭(zhēng)時(shí)隙.有需求的網(wǎng)絡(luò)節(jié)點(diǎn)需在競(jìng)爭(zhēng)幀內(nèi)隨機(jī)選擇某一競(jìng)爭(zhēng)時(shí)隙，以握手方式參與競(jìng)爭(zhēng).

協(xié)議的具體握手過(guò)程借鑒FPRP[6]協(xié)議中的5步握手機(jī)制，但采用全新的ODHR算法，通過(guò)在握手?jǐn)?shù)據(jù)包中增加攜帶競(jìng)爭(zhēng)標(biāo)識(shí)字段和采用跳躍預(yù)留策略，有效提高時(shí)隙分配的效率和有效性.競(jìng)爭(zhēng)標(biāo)識(shí)字段記錄了當(dāng)前握手?jǐn)?shù)據(jù)包的種類(lèi)和預(yù)留發(fā)起節(jié)點(diǎn)需求的目標(biāo)信息時(shí)隙編號(hào).

1.2 ODHR時(shí)隙預(yù)留算法

ODHR時(shí)隙預(yù)留算法主要分為業(yè)務(wù)量評(píng)估競(jìng)爭(zhēng)仲裁過(guò)程和跳躍時(shí)隙預(yù)留過(guò)程.算法默認(rèn)全網(wǎng)各節(jié)點(diǎn)擁有相同的協(xié)議參數(shù)配置.設(shè)整個(gè)時(shí)元共配置KF個(gè)信息幀，每個(gè)信息幀中有N個(gè)信息時(shí)隙，配置一個(gè)競(jìng)爭(zhēng)幀，包含M個(gè)競(jìng)爭(zhēng)時(shí)隙.

業(yè)務(wù)量評(píng)估競(jìng)爭(zhēng)仲裁過(guò)程負(fù)責(zé)評(píng)估當(dāng)前業(yè)務(wù)量及可獲得的時(shí)隙資源，以判定是否需要競(jìng)爭(zhēng)新的時(shí)隙.設(shè)當(dāng)前MAC層發(fā)送隊(duì)列中緩沖的實(shí)際業(yè)務(wù)量為Db.而根據(jù)協(xié)議評(píng)估，某節(jié)點(diǎn)在當(dāng)前時(shí)元內(nèi)能支持的業(yè)務(wù)量為已經(jīng)預(yù)留到的信息時(shí)隙資源Sp，計(jì)劃預(yù)留的信息時(shí)隙資源Pp，信息幀個(gè)數(shù)KF和信道帶寬B的函數(shù):

當(dāng)Db≤時(shí)，該節(jié)點(diǎn)已獲得足夠時(shí)隙資源，協(xié)議不允許該節(jié)點(diǎn)競(jìng)爭(zhēng)新的時(shí)隙;而當(dāng)Db＞時(shí)，協(xié)議允許該節(jié)點(diǎn)繼續(xù)競(jìng)爭(zhēng)新的時(shí)隙.

協(xié)議一般將競(jìng)爭(zhēng)幀內(nèi)的M個(gè)競(jìng)爭(zhēng)時(shí)隙分為n個(gè)競(jìng)爭(zhēng)組，每組m個(gè)競(jìng)爭(zhēng)時(shí)隙.當(dāng)某節(jié)點(diǎn)需要新的時(shí)隙時(shí)，跳躍時(shí)隙預(yù)留過(guò)程要在當(dāng)前競(jìng)爭(zhēng)組內(nèi)選定競(jìng)爭(zhēng)時(shí)隙號(hào)ci和目標(biāo)信息時(shí)隙號(hào)rj:

式中:Rf為空閑時(shí)隙集，若Rf=?則當(dāng)前時(shí)元內(nèi)無(wú)可用時(shí)隙.當(dāng)時(shí)間到達(dá)選定的競(jìng)爭(zhēng)時(shí)隙時(shí)，協(xié)議在握手?jǐn)?shù)據(jù)包競(jìng)爭(zhēng)標(biāo)識(shí)字段中填入選定的目標(biāo)信息時(shí)隙rj，開(kāi)始競(jìng)爭(zhēng).

設(shè)在當(dāng)前競(jìng)爭(zhēng)組內(nèi)有k個(gè)節(jié)點(diǎn)同時(shí)參與競(jìng)爭(zhēng)，每個(gè)節(jié)點(diǎn)選定的競(jìng)爭(zhēng)時(shí)隙為

當(dāng)某節(jié)點(diǎn)選定競(jìng)爭(zhēng)時(shí)隙cl滿足式(4)條件時(shí)，

協(xié)議即可為該節(jié)點(diǎn)完成其對(duì)目標(biāo)時(shí)隙的預(yù)留，并在隨后的每個(gè)信息幀內(nèi)均有權(quán)使用該信息時(shí)隙.在預(yù)留完成后需要更新Sp、Pp、Rf和時(shí)隙預(yù)留表.

在隨后的競(jìng)爭(zhēng)組內(nèi)，重復(fù)該算法，繼續(xù)為有需求的節(jié)點(diǎn)分配空閑的信息時(shí)隙.當(dāng)整個(gè)競(jìng)爭(zhēng)幀完成時(shí)，仍空閑的時(shí)隙將無(wú)法被使用，造成時(shí)隙浪費(fèi).設(shè)已經(jīng)完成分配的時(shí)隙總數(shù)為wcell，則協(xié)議在當(dāng)前時(shí)元內(nèi)的時(shí)隙分配效率為

1.3 協(xié)議流程

DRSA協(xié)議共有5個(gè)主要狀態(tài)，狀態(tài)轉(zhuǎn)移圖如圖2所示.當(dāng)協(xié)議檢測(cè)到MAC層隊(duì)列中有業(yè)務(wù)數(shù)據(jù)緩沖時(shí)，從等待狀態(tài)進(jìn)入競(jìng)爭(zhēng)準(zhǔn)備狀態(tài)，并完成業(yè)務(wù)量評(píng)估及競(jìng)爭(zhēng)仲裁過(guò)程，根據(jù)仲裁結(jié)果決定是否需要預(yù)留新的時(shí)隙資源;若需要，協(xié)議開(kāi)啟跳躍時(shí)隙預(yù)留過(guò)程，根據(jù)時(shí)隙預(yù)留表隨機(jī)選擇當(dāng)前空閑的信息時(shí)隙和競(jìng)爭(zhēng)時(shí)隙，準(zhǔn)備參與競(jìng)爭(zhēng).待時(shí)間到達(dá)選定的競(jìng)爭(zhēng)時(shí)隙，協(xié)議即可進(jìn)入競(jìng)爭(zhēng)狀態(tài).當(dāng)協(xié)議在等待狀態(tài)時(shí)，若收到其他節(jié)點(diǎn)的時(shí)隙預(yù)留請(qǐng)求，會(huì)被動(dòng)進(jìn)入競(jìng)爭(zhēng)狀態(tài)配合預(yù)留發(fā)起節(jié)點(diǎn)完成競(jìng)爭(zhēng)過(guò)程.在競(jìng)爭(zhēng)完成后，協(xié)議進(jìn)入更新預(yù)留狀態(tài)，記錄預(yù)留結(jié)果更新時(shí)隙預(yù)留表.而后，協(xié)議回到等待狀態(tài).當(dāng)時(shí)間進(jìn)行到本節(jié)點(diǎn)成功預(yù)留的信息時(shí)隙時(shí)，協(xié)議即進(jìn)入業(yè)務(wù)數(shù)據(jù)發(fā)送狀態(tài)，發(fā)送MAC層隊(duì)列中緩沖的業(yè)務(wù)數(shù)據(jù).

圖2 DRSA協(xié)議狀態(tài)轉(zhuǎn)移Fig.2 The state machine of DRSA

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

2.1 協(xié)議時(shí)隙分配效率分析與仿真

根據(jù)DRSA協(xié)議，時(shí)隙的分配過(guò)程完全獨(dú)立.容易證明Ωg的統(tǒng)計(jì)平均值可以成為 E[Ωg]的無(wú)偏估計(jì).由此，定義協(xié)議時(shí)隙分配效率Ωp為

設(shè)競(jìng)爭(zhēng)幀的第Gj個(gè)競(jìng)爭(zhēng)組中共有K個(gè)節(jié)點(diǎn)利用組內(nèi)的m個(gè)競(jìng)爭(zhēng)時(shí)隙參與競(jìng)爭(zhēng).各節(jié)點(diǎn)選擇競(jìng)爭(zhēng)時(shí)隙的所有結(jié)果可以表示為如下數(shù)學(xué)模型:

式中:a1、a2、…、am分別代表編號(hào)為1～m的競(jìng)爭(zhēng)時(shí)隙.將該表達(dá)式逐步完全展開(kāi)為多項(xiàng)式形式可得:

式中:

將所有同類(lèi)項(xiàng)合并，可將式(8)簡(jiǎn)化為

式中:每項(xiàng)都代表所有K個(gè)節(jié)點(diǎn)隨機(jī)選定競(jìng)爭(zhēng)時(shí)隙的一種結(jié)果，指數(shù)k1、k2、…、km代表該結(jié)果中選擇相應(yīng)競(jìng)爭(zhēng)時(shí)隙的節(jié)點(diǎn)數(shù)，系數(shù) Ak1，k2，…，km代表產(chǎn)生相應(yīng)結(jié)果的情況總數(shù).根據(jù)式(4)定義的條件，當(dāng)?kj∈{k1，k2，…，km}∪kj=1時(shí)，在該競(jìng)爭(zhēng)時(shí)隙內(nèi)不會(huì)發(fā)生競(jìng)爭(zhēng)碰撞，節(jié)點(diǎn)可完成預(yù)留.則在當(dāng)前競(jìng)爭(zhēng)組內(nèi)能成功分配d個(gè)時(shí)隙的概率為

式中:

由此，在當(dāng)前第Gj個(gè)競(jìng)爭(zhēng)組內(nèi)能夠成功分配的時(shí)隙數(shù)的期望為wgroup(Gj):

假設(shè)，平均每個(gè)競(jìng)爭(zhēng)組內(nèi)均有K個(gè)節(jié)點(diǎn)參與競(jìng)爭(zhēng)，則在當(dāng)前時(shí)元內(nèi)，能夠成功分配時(shí)隙總數(shù)的期望為

將式(14)代入式(6)，即可得到協(xié)議的時(shí)隙分配效率.

通過(guò)蒙特卡洛仿真，圖3給出了在同一競(jìng)爭(zhēng)域內(nèi)，不同數(shù)量節(jié)點(diǎn)同時(shí)參與競(jìng)爭(zhēng)情況下的協(xié)議時(shí)隙分配效率Ωp.圖中m×n代表不同競(jìng)爭(zhēng)時(shí)隙總數(shù)及其分組方法，K為在同一競(jìng)爭(zhēng)域內(nèi)參與競(jìng)爭(zhēng)的節(jié)點(diǎn)總數(shù).

圖3 不同參數(shù)配置下時(shí)隙分配效率Fig.3 The efficiency of slot assignment under different parameters

從圖3中可以看出，競(jìng)爭(zhēng)時(shí)隙總數(shù)對(duì)Ωp有直接影響.隨著競(jìng)爭(zhēng)時(shí)隙總數(shù)的增加，協(xié)議可有效支持更多節(jié)點(diǎn)同時(shí)參與競(jìng)爭(zhēng)并保持協(xié)議時(shí)隙分配效率穩(wěn)定在85%以上，但同時(shí)會(huì)增加協(xié)議的開(kāi)銷(xiāo).在競(jìng)爭(zhēng)時(shí)隙總數(shù)一定時(shí)，不同的分組方法也會(huì)對(duì)協(xié)議時(shí)隙分配效率造成影響.適當(dāng)調(diào)整競(jìng)爭(zhēng)組數(shù)n和每組競(jìng)爭(zhēng)時(shí)隙數(shù)m可以在不增加協(xié)議開(kāi)銷(xiāo)的基礎(chǔ)上進(jìn)一步提高協(xié)議時(shí)隙分配效率.

同時(shí)通過(guò)圖3還可以看到，適當(dāng)選定競(jìng)爭(zhēng)時(shí)隙總數(shù)及分組方法后，協(xié)議可以保證競(jìng)爭(zhēng)節(jié)點(diǎn)總數(shù)K的值在較寬范圍內(nèi)變化時(shí)仍然有較高的協(xié)議時(shí)隙分配效率.這說(shuō)明本協(xié)議具有較強(qiáng)的適應(yīng)性和健壯性，對(duì)于因節(jié)點(diǎn)移動(dòng)、業(yè)務(wù)分布變化而引起的網(wǎng)絡(luò)環(huán)境變化，仍然能夠保證網(wǎng)絡(luò)的高效運(yùn)行.

2.2 DRSA協(xié)議在海上自組網(wǎng)中的性能

使用Qualnet網(wǎng)絡(luò)仿真軟件，在典型海上自組網(wǎng)應(yīng)用場(chǎng)景下，對(duì)DRSA協(xié)議、802.11以及靜態(tài)TDMA協(xié)議在不同的業(yè)務(wù)負(fù)載情況下的平均吞吐量性能進(jìn)行充分地仿真.仿真場(chǎng)景的相關(guān)主要參數(shù)如表1所示.

表1 仿真場(chǎng)景主要參數(shù)Table 1 The main parameters of simulation scenario

吞吐量仿真結(jié)果如圖4所示.從圖4中可以看出，當(dāng)網(wǎng)絡(luò)處于輕負(fù)載時(shí)，3種協(xié)議吞吐量性能相當(dāng).當(dāng)網(wǎng)絡(luò)處于中度負(fù)載時(shí)，由于靜態(tài)TDMA協(xié)議服從固定的時(shí)隙分配方案，不能在空間中形成有效的時(shí)隙復(fù)用，導(dǎo)致靜態(tài)TDMA協(xié)議的平均吞吐量性能出現(xiàn)瓶頸;而DRSA與802.11協(xié)議在中度負(fù)載時(shí)的吞吐量性能相當(dāng)，均明顯優(yōu)于靜態(tài)TDMA.隨著網(wǎng)絡(luò)中業(yè)務(wù)負(fù)載的進(jìn)一步加重，DRSA協(xié)議與802.11協(xié)議的平均吞吐量性能開(kāi)始分化.借助于ODHR時(shí)隙預(yù)留算法，DRSA協(xié)議可以在擁擠的網(wǎng)絡(luò)環(huán)境和密集的業(yè)務(wù)環(huán)境下根據(jù)業(yè)務(wù)需求有效地協(xié)調(diào)各發(fā)送節(jié)點(diǎn)，高效地分配和利用空閑的時(shí)隙資源，在空間上形成有效復(fù)用，使平均吞吐量性能得到進(jìn)一步提高.最終DRSA協(xié)議的平均吞吐量穩(wěn)定在4×105bit/s水平，而802.11協(xié)議的平均吞吐量穩(wěn)定在2.5×105bit/s水平.DRSA協(xié)議的吞吐量較802.11協(xié)議提高約60%.

圖4 吞吐量對(duì)比仿真結(jié)果Fig.4 The performance comparison on throughput

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

根據(jù)建模分析和仿真驗(yàn)證，DRSA協(xié)議能夠根據(jù)當(dāng)前網(wǎng)絡(luò)中各節(jié)點(diǎn)的業(yè)務(wù)負(fù)載情況，以完全分布式的方式按各節(jié)點(diǎn)的業(yè)務(wù)需求高效地為各節(jié)點(diǎn)分配時(shí)隙資源，而不依賴(lài)任何關(guān)于當(dāng)前網(wǎng)絡(luò)拓?fù)淝闆r的先驗(yàn)信息，使得協(xié)議具有較強(qiáng)的適應(yīng)性、健壯性和可擴(kuò)展性.

[1]MOSCIBRODA T，WATTENHOFER R.Coloring unstructured radio networks[C]//Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures.New York，USA，2005:39-48.

[2]SAGDUYU Y E，EPHREMIDES A.On joint MAC and network coding in wireless Ad Hoc networks[J].IEEE Transactions on Information Theory，2010，53(10):3697-3713.

[3]SRINIVASAN P，RAJIV G.Distributed algorithms for coloring and domination in wireless Ad Hoc networks[C]//Proceedings of FSTTCS＇04.Chennai，India，2004:447-459.

[4]胡致遠(yuǎn)，郭建丁，王景，等.多接口無(wú)線mesh網(wǎng)絡(luò)的信道時(shí)空分配[J].重慶大學(xué)學(xué)報(bào)，2011，34(2):26-31.HU Zhiyuan，GUO Jianding，WANG Jing，et al.Spatiotemporal channel assignment in multi-radio wireless mesh networks[J].Journal of Chongqing University，2011，34(2):26-31.

[5]RHEE I，WARRIER A，JEONGKI M，et al.DRAND:distributed randomized TDMA scheduling for wireless Ad Hoc networks[J].IEEE Transactions on Mobile Computing，2009，8(10):1384-1396.

[6]ZHU C X，CORSON M S.A five-phase reservation protocol(FPRP)for mobile ad hoc networks[C]//Proceedings of Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies.San Francisco，USA 1998:322-331.

[7]SAYADI A，WEHBI B，LAOUITI A.One shot TDMA-based reservation MAC protocol for wireless Ad Hoc networks[C]//Proceedings of Vehicular Technology Conference.Evry，F(xiàn)rance，2011:1-5.

[8]ZHU C X，CORSON M S.An evolutionary-TDMA scheduling protocol(E-TDMA)for mobile Ad Hoc networks[R].Baltimore:University of Maryland，2000.

[9]VALLATI C.Dynamic resources allocation in wireless mesh networks[C]//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.Pisa，Italy，2011:1-3.

[10]LI Hongyan，VALAEE S.An efficient algorithm for time slot assignment in Ad Hoc networks[C]//Proceedings of 22nd Biennial Symposium in Commucications.Kingston，Canada，2004:225-227.

[11]XU Mingxia，ZHAO Minjian，SONG Zhengwei，et al.An on-demand and dynamic slot assignment protocol for Ad Hoc networks[C]//Proceedings of APCC＇06.Busan，Korea，2006:1-5.

[12]馬柯，俞能海，楊福榮.EASA:一種分簇Ad Hoc網(wǎng)絡(luò)高效自適應(yīng)TDMA時(shí)隙分配算法[J].電子學(xué)，2010，38(7):1678-1682.MA Ke，YU Nenghai，YANG Furong.EASA:an efficient adaptive TDMA slot assignment protocol for clustered Ad Hoc network[J].Acta Electronica Sinica，2010，38(7):1678-1682.