基于鄰居監(jiān)測(cè)的時(shí)隙動(dòng)態(tài)復(fù)用算法

田永春

(中國(guó)電子科技集團(tuán)公司第30研究所，成都 610041)

0 引言

在以無(wú)線通信為主的高動(dòng)態(tài)戰(zhàn)術(shù)通信環(huán)境中，一般采用多跳的Ad hoc網(wǎng)絡(luò)結(jié)構(gòu)，沒(méi)有一個(gè)可靠的中心控制點(diǎn)，節(jié)點(diǎn)間分布式協(xié)調(diào)困難，存在隱藏終端和暴露終端等問(wèn)題，導(dǎo)致進(jìn)行全局資源優(yōu)化的難度較大。較低的通信帶寬和低下的信道利用率一直是戰(zhàn)術(shù)通信發(fā)展的主要瓶頸，因此動(dòng)態(tài)信道分配與復(fù)用技術(shù)一直是戰(zhàn)役/戰(zhàn)術(shù)通信系統(tǒng)的主要研究難點(diǎn)。

戰(zhàn)術(shù)業(yè)務(wù)類型通常可分為周期性和突發(fā)性業(yè)務(wù)，為了保證周期性業(yè)務(wù)的及時(shí)、可靠傳輸，要求節(jié)點(diǎn)必須具有無(wú)沖突的周期性信道資源;而為了滿足突發(fā)性業(yè)務(wù)及大報(bào)文業(yè)務(wù)的及時(shí)傳輸，要求節(jié)點(diǎn)具有可動(dòng)態(tài)使用的額外信道資源。這給信道分配帶來(lái)了新的困難。

為了滿足戰(zhàn)術(shù)業(yè)務(wù)的傳輸需要，提高信道資源利用率，有兩個(gè)基本解決途徑:一是增加單個(gè)節(jié)點(diǎn)可用信道資源，在戰(zhàn)術(shù)環(huán)境下，該途徑會(huì)帶來(lái)較大的代價(jià);二是提高信道的利用率，結(jié)合多種信道分配方式，在保證節(jié)點(diǎn)一定固定信道資源的同時(shí)，進(jìn)行資源的動(dòng)態(tài)復(fù)用，充分利用戰(zhàn)術(shù)通信網(wǎng)的多跳特性，進(jìn)行空間復(fù)用。

信道分配方式主要可以分為競(jìng)爭(zhēng)協(xié)議和預(yù)留協(xié)議[1]。由于戰(zhàn)術(shù)環(huán)境對(duì)信息傳輸?shù)募皶r(shí)性和可靠性要求較高，因此競(jìng)爭(zhēng)協(xié)議不能作為主要的信道接入手段;FDMA、CDMA均無(wú)法有效避免隱藏終端和暴露終端等問(wèn)題，采用固定分配TDMA方式時(shí)，又存在效率較低等問(wèn)題;而基于波形成形技術(shù)的信道空間復(fù)用技術(shù)還在研究階段[2]。

將單信道固定分配TDMA方式與動(dòng)態(tài)時(shí)隙競(jìng)爭(zhēng)協(xié)議結(jié)合起來(lái)，通過(guò)信道監(jiān)測(cè)與節(jié)點(diǎn)的鄰居關(guān)系，實(shí)現(xiàn)信道的空間復(fù)用，試圖以較小的代價(jià)與算法復(fù)雜度，獲得較高的信道利用率。第1節(jié)將對(duì)算法模型進(jìn)行描述，并在第2節(jié)對(duì)算法進(jìn)行仿真分析，最后對(duì)算法進(jìn)行總結(jié)。

1 算法描述

1.1 算法前提

本文的算法以單信道固定分配TDMA協(xié)議為基礎(chǔ)，假設(shè)信道具有較高的通信速率，能進(jìn)行較精確的時(shí)間和跳頻同步，支持TDMA和CSMA方式，支持動(dòng)態(tài)信道占用。

為了滿足周期性和突發(fā)性業(yè)務(wù)的傳輸需要，采用TDMA+CSMA組合的信道訪問(wèn)方式，將信道劃分為時(shí)幀T，每個(gè)時(shí)幀包括固定分配時(shí)隙FS和競(jìng)爭(zhēng)時(shí)隙CS，則T={FS CS}。幀結(jié)構(gòu)如圖1所示。

圖1 信道幀結(jié)構(gòu)示意圖

其中FS的時(shí)隙數(shù)量與網(wǎng)內(nèi)節(jié)點(diǎn)數(shù)n一致，每個(gè)節(jié)點(diǎn)固定占用一個(gè)時(shí)隙，用于節(jié)點(diǎn)初始組網(wǎng)和周期性信息的傳遞;CS的時(shí)隙數(shù)量c主要作為緊急突發(fā)業(yè)務(wù)的傳輸及臨時(shí)入網(wǎng)用戶的隨機(jī)接入信道。為了提高突發(fā)業(yè)務(wù)傳輸速度，CS可與FS進(jìn)行交錯(cuò)排列。復(fù)用算法針對(duì)整個(gè)時(shí)幀T進(jìn)行。

每個(gè)節(jié)點(diǎn)Ni保持一個(gè)信道監(jiān)測(cè)矢量CULi=(s1，…，sn，…，sn+c)i，其中每個(gè) sj，j=1…(n+c)代表節(jié)點(diǎn)Ni所監(jiān)測(cè)到的信道狀態(tài)。在統(tǒng)一時(shí)隙分配協(xié)議(USAP)[3]中，sj有三種狀態(tài):發(fā)送、接收、鄰居傳輸或沖突。為了簡(jiǎn)化協(xié)議，只設(shè)定兩種狀態(tài)，時(shí)隙忙和閑。假如節(jié)點(diǎn)Ni監(jiān)測(cè)到時(shí)隙忙，即該時(shí)隙已經(jīng)被占用，則sj=1;否則sj=0。因此每個(gè)sj用1 bit就可以標(biāo)識(shí)。

信道復(fù)用是為了在有效避免隱藏終端與暴露終端等問(wèn)題的情況下，最大限度地利用信道資源，避免沖突。隱藏終端與暴露終端還可根據(jù)發(fā)送或接收再進(jìn)行細(xì)分[4]，其中隱藏發(fā)射終端和暴露接收終端主要引起接收沖突，而隱藏接收終端與暴露發(fā)送終端主要引起資源浪費(fèi)。為了保證信息的可靠傳輸，必須避免沖突;但為了解決隱藏接收終端與暴露發(fā)送終端引起的資源浪費(fèi)，會(huì)給算法帶來(lái)很大的復(fù)雜度和動(dòng)態(tài)性，所引起的開(kāi)銷會(huì)抵消所帶來(lái)的好處，因此本算法對(duì)這部分資源不進(jìn)行利用。

1.2 復(fù)用算法

在網(wǎng)絡(luò)初始化時(shí)，為每個(gè)節(jié)點(diǎn)Ni指定一個(gè)時(shí)隙FSi作為固定的時(shí)隙，如果在復(fù)用后發(fā)生沖突時(shí)，其余節(jié)點(diǎn)應(yīng)進(jìn)行退避。節(jié)點(diǎn)在該時(shí)隙上進(jìn)行初始化，建立鄰居關(guān)系表和路由表。在網(wǎng)絡(luò)初始化完成后，根據(jù)監(jiān)測(cè)到的信道狀況生成 CULi，并進(jìn)行CULi的維護(hù)與更新。當(dāng)節(jié)點(diǎn)檢測(cè)到某個(gè)時(shí)隙被使用后，將對(duì)應(yīng)的位狀態(tài)置1;如果檢測(cè)到某個(gè)使用的時(shí)隙在某個(gè)時(shí)間內(nèi)一直處于空閑狀態(tài)，則將對(duì)應(yīng)的位狀態(tài)置0。生成 CULi后，節(jié)點(diǎn)即可進(jìn)行信道復(fù)用。

復(fù)用算法拓?fù)涫疽鈭D，如圖2所示。進(jìn)行分析可以發(fā)現(xiàn)，節(jié)點(diǎn)1與節(jié)點(diǎn)11～14無(wú)論是發(fā)送還是接收，都不會(huì)互相影響，同樣，節(jié)點(diǎn)2與節(jié)點(diǎn)9、10、11、14等都不會(huì)互相影響。因此節(jié)點(diǎn)1可以復(fù)用節(jié)點(diǎn)11～14的時(shí)隙，達(dá)到類似空分復(fù)用的效果。

圖2 復(fù)用算法拓?fù)涫疽鈭D

根據(jù)上面的分析，可推得如下結(jié)論。

設(shè)節(jié)點(diǎn)Ni與Nj之間的跳數(shù)為h，則節(jié)點(diǎn)Ni可以復(fù)用的時(shí)隙集合RSi為

式中，F(xiàn)Sj是節(jié)點(diǎn)Nj的固有時(shí)隙。

由于競(jìng)爭(zhēng)時(shí)隙CS也可以與FS一樣進(jìn)行信道復(fù)用，一般地，設(shè)節(jié)點(diǎn)Ni的鄰居節(jié)點(diǎn)集合為Nbi，則可推得RSi為

為了保證每個(gè)節(jié)點(diǎn)都能獲得公平的復(fù)用機(jī)會(huì)，在獲得可復(fù)用時(shí)隙集合RSi以后，節(jié)點(diǎn)Ni并不立即占用該集合中的所有時(shí)隙，而是從中選擇出Tr個(gè)時(shí)隙進(jìn)行占用。每個(gè)節(jié)點(diǎn)的Tr與節(jié)點(diǎn)的優(yōu)先級(jí)、業(yè)務(wù)量大小有關(guān)。在某個(gè)節(jié)點(diǎn)進(jìn)行復(fù)用時(shí)，其鄰居節(jié)點(diǎn)將凍結(jié)其他的復(fù)用請(qǐng)求，在同時(shí)進(jìn)行復(fù)用時(shí)，高優(yōu)先級(jí)節(jié)點(diǎn)首先進(jìn)行復(fù)用。在首次復(fù)用完成后，如果時(shí)隙資源仍不能滿足節(jié)點(diǎn)傳輸需求，則進(jìn)行第二次復(fù)用。選擇的時(shí)隙位置應(yīng)盡可能地間隔均勻，降低突發(fā)業(yè)務(wù)的接入時(shí)延。

采用該算法后，在初始化過(guò)程中，在一個(gè)時(shí)幀內(nèi)每個(gè)節(jié)點(diǎn)只有一個(gè)固有時(shí)隙(與固定分配TDMA一樣)，在完成復(fù)用后，每個(gè)節(jié)點(diǎn)在一個(gè)時(shí)幀內(nèi)將獲得多個(gè)動(dòng)態(tài)復(fù)用時(shí)隙。

1.3 算法實(shí)現(xiàn)

從上述算法可設(shè)計(jì)出算法的實(shí)現(xiàn)。為了實(shí)現(xiàn)對(duì)空閑時(shí)隙的復(fù)用，每個(gè)節(jié)點(diǎn)或新加入的節(jié)點(diǎn)在通信過(guò)程中持續(xù)監(jiān)視信道。假如節(jié)點(diǎn)需要增加時(shí)隙以滿足業(yè)務(wù)傳輸?shù)男枰?，它首先發(fā)送復(fù)用請(qǐng)求(Req_resume)，鄰居節(jié)點(diǎn)將傳輸它當(dāng)前的信道監(jiān)測(cè)矢量CULi給請(qǐng)求的節(jié)點(diǎn)，進(jìn)行“位或”運(yùn)算后，選擇Tr個(gè)空閑時(shí)隙進(jìn)行占用，并向鄰居發(fā)送占用消息(Slot_Occup_NUM)，指定占用的時(shí)隙位。假如在移動(dòng)過(guò)程中，有節(jié)點(diǎn)發(fā)現(xiàn)了沖突，則發(fā)送否認(rèn)消息(NAK_NUM)，所有占用了否認(rèn)消息內(nèi)指示時(shí)隙的節(jié)點(diǎn)將釋放這些時(shí)隙，并重新進(jìn)行復(fù)用。如果沖突時(shí)隙是自己的固有時(shí)隙，則拒絕釋放。節(jié)點(diǎn)在占用了除固有時(shí)隙以外的時(shí)隙時(shí)，如果節(jié)點(diǎn)業(yè)務(wù)量較小，應(yīng)釋放不用的時(shí)隙資源，發(fā)送釋放消息(Slot_Rel_NUM)，鄰居節(jié)點(diǎn)更新自己的CULi。

算法實(shí)現(xiàn)流程如圖3所示。

圖3 動(dòng)態(tài)時(shí)隙占用

2 仿真結(jié)果

為了對(duì)算法的復(fù)用效果進(jìn)行分析，建立仿真場(chǎng)景進(jìn)行分析。場(chǎng)景設(shè)置如下:節(jié)點(diǎn)個(gè)數(shù)100個(gè)，均勻隨機(jī)分布在覆蓋范圍內(nèi)，信道設(shè)為UHF信道，通信距離設(shè)置為10 km，每個(gè)時(shí)隙長(zhǎng)度設(shè)為16 ms，競(jìng)爭(zhēng)時(shí)隙CS個(gè)數(shù)設(shè)為0，每次最大復(fù)用時(shí)隙個(gè)數(shù)Tr=10，可重復(fù)復(fù)用。因此一時(shí)幀長(zhǎng)度就為1.6 s，F(xiàn)S個(gè)數(shù)為100。針對(duì)靜止時(shí)信道復(fù)用情況、信道接入時(shí)延以及運(yùn)動(dòng)時(shí)時(shí)隙復(fù)用的變化情況進(jìn)行仿真，仿真結(jié)果如圖4所示。

圖4 靜止時(shí)動(dòng)態(tài)時(shí)隙占用情況

由圖4可見(jiàn)，在靜止時(shí)，節(jié)點(diǎn)復(fù)用時(shí)隙的個(gè)數(shù)與節(jié)點(diǎn)所處的位置、鄰居關(guān)系及復(fù)用的時(shí)機(jī)有較大的關(guān)系。不同的位置分布與不同的起始復(fù)用節(jié)點(diǎn)，節(jié)點(diǎn)可復(fù)用到的時(shí)隙數(shù)量是有差異的。而不同的節(jié)點(diǎn)分布密度對(duì)復(fù)用的時(shí)隙數(shù)量有較大的影響，越密集復(fù)用率越低，在本次仿真中，當(dāng)節(jié)點(diǎn)分布在60 km×60 km時(shí)，節(jié)點(diǎn)平均復(fù)用時(shí)隙748/100=7.48個(gè);在100 km×100 km時(shí)，節(jié)點(diǎn)平均復(fù)用時(shí)隙1815/100=18.15個(gè);在120 km×120 km時(shí)，節(jié)點(diǎn)平均復(fù)用時(shí)隙2112/100=21.12個(gè)。而不進(jìn)行復(fù)用時(shí)，每個(gè)節(jié)點(diǎn)僅有1個(gè)時(shí)隙。由此可見(jiàn)，復(fù)用對(duì)提高信道利用率的提高效果顯著。

信道平均接入時(shí)延的變化情況，如圖5所示。在不復(fù)用時(shí)，節(jié)點(diǎn)的平均信道接入時(shí)延在0.69 s左右，復(fù)用后減少到0.44 s左右?？梢?jiàn)復(fù)用也可降低信道接入時(shí)延。

圖5 靜止時(shí)信道平均接入時(shí)延

為了分析運(yùn)動(dòng)過(guò)程中信道復(fù)用情況，設(shè)置100個(gè)節(jié)點(diǎn)分布在60 km×60 km，運(yùn)動(dòng)速度設(shè)為5～50 km/h，平均30 km/h，不同方向運(yùn)動(dòng)速度有較大差異，用于模擬戰(zhàn)術(shù)使用場(chǎng)景。節(jié)點(diǎn)在運(yùn)動(dòng)過(guò)程中會(huì)經(jīng)歷稀疏到稠密然后再稀疏的過(guò)程。仿真結(jié)果表明，在節(jié)點(diǎn)運(yùn)動(dòng)過(guò)程中，網(wǎng)絡(luò)平均時(shí)隙復(fù)用個(gè)數(shù)隨著節(jié)點(diǎn)的分布密度而變化。當(dāng)節(jié)點(diǎn)較密時(shí)，平均復(fù)用個(gè)數(shù)下降，但當(dāng)節(jié)點(diǎn)較稀疏時(shí)，平均復(fù)用個(gè)數(shù)將增加。由于篇幅限制，這里不詳細(xì)列出。因此，本文的算法在網(wǎng)絡(luò)分布較稀疏時(shí)，空間復(fù)用效果更加明顯，在動(dòng)態(tài)過(guò)程中，算法也有較好的效果。

3 結(jié)語(yǔ)

本算法適應(yīng)于以時(shí)隙為基本傳輸單元的戰(zhàn)術(shù)電臺(tái)，結(jié)合了固定分配TDMA與動(dòng)態(tài)時(shí)隙分配的優(yōu)勢(shì)，在保證每個(gè)節(jié)點(diǎn)都獲得周期性時(shí)隙資源的同時(shí)，盡可能進(jìn)行信道復(fù)用，保證每個(gè)節(jié)點(diǎn)在固定時(shí)隙之外，獲得額外的時(shí)隙資源。仿真表明，復(fù)用對(duì)節(jié)點(diǎn)可用資源的提高效果是明顯的。算法對(duì)戰(zhàn)術(shù)通信的特點(diǎn)也能很好的適應(yīng)，通過(guò)分配時(shí)隙數(shù)量、優(yōu)先級(jí)、復(fù)用次序及單次最大復(fù)用時(shí)隙數(shù)等，可以保證重要的或大業(yè)務(wù)量的節(jié)點(diǎn)獲得更多的時(shí)隙，具有較好的適應(yīng)能力。

該算法的缺點(diǎn)是在動(dòng)態(tài)過(guò)程中每個(gè)節(jié)點(diǎn)獲得的時(shí)隙資源是波動(dòng)的，不同的復(fù)用時(shí)機(jī)與次序會(huì)影響復(fù)用效果，先復(fù)用節(jié)點(diǎn)選擇的時(shí)隙位置也會(huì)影響其他節(jié)點(diǎn)的復(fù)用效率，這也是本算法下一步要解決的問(wèn)題。算法沒(méi)有對(duì)隱藏接收終端與暴露發(fā)送終端所引起的資源浪費(fèi)進(jìn)行利用，因此復(fù)用效率是次優(yōu)的，但算法簡(jiǎn)單，便于實(shí)現(xiàn)。

[1]鄭相全，等.無(wú)線自組網(wǎng)技術(shù)[M].北京:清華大學(xué)出版社，2004.

[2]劉強(qiáng)，吳煒霞，蘇旸.波束成形技術(shù)在超短波電臺(tái)中的應(yīng)用研究[J].中國(guó)電子科學(xué)研究院學(xué)報(bào)，2010，5(4):30-33.

[3]YOUNG C D.USAP Multiple Access:Dynamic Resource Allocation for Mobile Multihop Multichannel Wireless Networking[C]//Proceedings of the IEEE MILCOM 1999 Conference，Atlantic City，New Jersey，1999:271-275.

[4]GARCES R，GARCIA-LUNA-ACEVES J J Collision Avoidance and Resolution Multiple Access for Multichannel Wireless Networks[C]//Proc IEEE INFOCOM 2000，Tel-Aviv，Israel，2000.