基于鄰居監測的時隙動態復用算法

田永春

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

0 引言

在以無線通信為主的高動態戰術通信環境中，一般采用多跳的Ad hoc網絡結構，沒有一個可靠的中心控制點，節點間分布式協調困難，存在隱藏終端和暴露終端等問題，導致進行全局資源優化的難度較大。較低的通信帶寬和低下的信道利用率一直是戰術通信發展的主要瓶頸，因此動態信道分配與復用技術一直是戰役/戰術通信系統的主要研究難點。

戰術業務類型通?？煞譃橹芷谛院屯话l性業務，為了保證周期性業務的及時、可靠傳輸，要求節點必須具有無沖突的周期性信道資源;而為了滿足突發性業務及大報文業務的及時傳輸，要求節點具有可動態使用的額外信道資源。這給信道分配帶來了新的困難。

為了滿足戰術業務的傳輸需要，提高信道資源利用率，有兩個基本解決途徑:一是增加單個節點可用信道資源，在戰術環境下，該途徑會帶來較大的代價;二是提高信道的利用率，結合多種信道分配方式，在保證節點一定固定信道資源的同時，進行資源的動態復用，充分利用戰術通信網的多跳特性，進行空間復用。

信道分配方式主要可以分為競爭協議和預留協議[1]。由于戰術環境對信息傳輸的及時性和可靠性要求較高，因此競爭協議不能作為主要的信道接入手段;FDMA、CDMA均無法有效避免隱藏終端和暴露終端等問題，采用固定分配TDMA方式時，又存在效率較低等問題;而基于波形成形技術的信道空間復用技術還在研究階段[2]。

將單信道固定分配TDMA方式與動態時隙競爭協議結合起來，通過信道監測與節點的鄰居關系，實現信道的空間復用，試圖以較小的代價與算法復雜度，獲得較高的信道利用率。第1節將對算法模型進行描述，并在第2節對算法進行仿真分析，最后對算法進行總結。

1 算法描述

1.1 算法前提

本文的算法以單信道固定分配TDMA協議為基礎，假設信道具有較高的通信速率，能進行較精確的時間和跳頻同步，支持TDMA和CSMA方式，支持動態信道占用。

為了滿足周期性和突發性業務的傳輸需要，采用TDMA+CSMA組合的信道訪問方式，將信道劃分為時幀T，每個時幀包括固定分配時隙FS和競爭時隙CS，則T={FS CS}。幀結構如圖1所示。

圖1 信道幀結構示意圖

其中FS的時隙數量與網內節點數n一致，每個節點固定占用一個時隙，用于節點初始組網和周期性信息的傳遞;CS的時隙數量c主要作為緊急突發業務的傳輸及臨時入網用戶的隨機接入信道。為了提高突發業務傳輸速度，CS可與FS進行交錯排列。復用算法針對整個時幀T進行。

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

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

1.2 復用算法

在網絡初始化時，為每個節點Ni指定一個時隙FSi作為固定的時隙，如果在復用后發生沖突時，其余節點應進行退避。節點在該時隙上進行初始化，建立鄰居關系表和路由表。在網絡初始化完成后，根據監測到的信道狀況生成 CULi，并進行CULi的維護與更新。當節點檢測到某個時隙被使用后，將對應的位狀態置1;如果檢測到某個使用的時隙在某個時間內一直處于空閑狀態，則將對應的位狀態置0。生成 CULi后，節點即可進行信道復用。

復用算法拓撲示意圖，如圖2所示。進行分析可以發現，節點1與節點11～14無論是發送還是接收，都不會互相影響，同樣，節點2與節點9、10、11、14等都不會互相影響。因此節點1可以復用節點11～14的時隙，達到類似空分復用的效果。

圖2 復用算法拓撲示意圖

根據上面的分析，可推得如下結論。

設節點Ni與Nj之間的跳數為h，則節點Ni可以復用的時隙集合RSi為

式中，FSj是節點Nj的固有時隙。

由于競爭時隙CS也可以與FS一樣進行信道復用，一般地，設節點Ni的鄰居節點集合為Nbi，則可推得RSi為

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

采用該算法后，在初始化過程中，在一個時幀內每個節點只有一個固有時隙(與固定分配TDMA一樣)，在完成復用后，每個節點在一個時幀內將獲得多個動態復用時隙。

1.3 算法實現

從上述算法可設計出算法的實現。為了實現對空閑時隙的復用，每個節點或新加入的節點在通信過程中持續監視信道。假如節點需要增加時隙以滿足業務傳輸的需要，它首先發送復用請求(Req_resume)，鄰居節點將傳輸它當前的信道監測矢量CULi給請求的節點，進行“位或”運算后，選擇Tr個空閑時隙進行占用，并向鄰居發送占用消息(Slot_Occup_NUM)，指定占用的時隙位。假如在移動過程中，有節點發現了沖突，則發送否認消息(NAK_NUM)，所有占用了否認消息內指示時隙的節點將釋放這些時隙，并重新進行復用。如果沖突時隙是自己的固有時隙，則拒絕釋放。節點在占用了除固有時隙以外的時隙時，如果節點業務量較小，應釋放不用的時隙資源，發送釋放消息(Slot_Rel_NUM)，鄰居節點更新自己的CULi。

算法實現流程如圖3所示。

圖3 動態時隙占用

2 仿真結果

為了對算法的復用效果進行分析，建立仿真場景進行分析。場景設置如下:節點個數100個，均勻隨機分布在覆蓋范圍內，信道設為UHF信道，通信距離設置為10 km，每個時隙長度設為16 ms，競爭時隙CS個數設為0，每次最大復用時隙個數Tr=10，可重復復用。因此一時幀長度就為1.6 s，FS個數為100。針對靜止時信道復用情況、信道接入時延以及運動時時隙復用的變化情況進行仿真，仿真結果如圖4所示。

圖4 靜止時動態時隙占用情況

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

信道平均接入時延的變化情況，如圖5所示。在不復用時，節點的平均信道接入時延在0.69 s左右，復用后減少到0.44 s左右?？梢姀陀靡部山档托诺澜尤霑r延。

圖5 靜止時信道平均接入時延

為了分析運動過程中信道復用情況，設置100個節點分布在60 km×60 km，運動速度設為5～50 km/h，平均30 km/h，不同方向運動速度有較大差異，用于模擬戰術使用場景。節點在運動過程中會經歷稀疏到稠密然后再稀疏的過程。仿真結果表明，在節點運動過程中，網絡平均時隙復用個數隨著節點的分布密度而變化。當節點較密時，平均復用個數下降，但當節點較稀疏時，平均復用個數將增加。由于篇幅限制，這里不詳細列出。因此，本文的算法在網絡分布較稀疏時，空間復用效果更加明顯，在動態過程中，算法也有較好的效果。

3 結語

本算法適應于以時隙為基本傳輸單元的戰術電臺，結合了固定分配TDMA與動態時隙分配的優勢，在保證每個節點都獲得周期性時隙資源的同時，盡可能進行信道復用，保證每個節點在固定時隙之外，獲得額外的時隙資源。仿真表明，復用對節點可用資源的提高效果是明顯的。算法對戰術通信的特點也能很好的適應，通過分配時隙數量、優先級、復用次序及單次最大復用時隙數等，可以保證重要的或大業務量的節點獲得更多的時隙，具有較好的適應能力。

該算法的缺點是在動態過程中每個節點獲得的時隙資源是波動的，不同的復用時機與次序會影響復用效果，先復用節點選擇的時隙位置也會影響其他節點的復用效率，這也是本算法下一步要解決的問題。算法沒有對隱藏接收終端與暴露發送終端所引起的資源浪費進行利用，因此復用效率是次優的，但算法簡單，便于實現。

[1]鄭相全，等.無線自組網技術[M].北京:清華大學出版社，2004.

[2]劉強，吳煒霞，蘇旸.波束成形技術在超短波電臺中的應用研究[J].中國電子科學研究院學報，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.