移動Ad-hoc網(wǎng)絡(luò)中無線跳頻頻率資源分配機制研究*

古稀林，王 超，馮志先，姜永廣

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

移動Ad-hoc環(huán)境中大量使用無線傳輸設(shè)備，例如SRD（Soldier Radio Device），SRD通過無線電波相互通聯(lián)，組成了靈活、龐大、復(fù)雜的用頻網(wǎng)系[1］。典型移動Ad-hoc網(wǎng)絡(luò)（Mobile Ad-hoc network，MANET）拓撲如圖1所示，多個節(jié)點（NODE）通過SRW（Soldier Radio Waveform）實現(xiàn)分層組網(wǎng)，以滿足節(jié)點間的互聯(lián)互通需求。

圖1 典型移動Ad-hoc網(wǎng)絡(luò)拓撲示意圖

跳頻頻率規(guī)劃需要為各個子網(wǎng)分配跳頻表號和網(wǎng)號，不同的子網(wǎng)可以采用不同頻表，也可以采用相同頻表，但需使用不同的網(wǎng)號來區(qū)分[2］，每個頻表中存在若干個頻率值（頻點），與網(wǎng)號一一對應(yīng)。針對采用同一頻表的多個子網(wǎng)而言，可以將網(wǎng)號對應(yīng)的頻點視為起跳頻點，不同的網(wǎng)號決定了子網(wǎng)擁有不同的起跳頻點。子網(wǎng)之間通過組建同步正交網(wǎng)絡(luò)[3-4］，使子網(wǎng)間的頻率間隔始終保持一致，因此，在一定條件下，子網(wǎng)之間的頻率間隔就等于起跳頻點之間的間隔。

移動Ad-hoc網(wǎng)絡(luò)中跳頻頻率資源規(guī)劃存在以下幾個方面的困難：

（1）通信需求多樣，導(dǎo)致網(wǎng)絡(luò)拓撲中組網(wǎng)關(guān)系十分復(fù)雜且多變，從而對頻率規(guī)劃求解模型的適應(yīng)性提出較高要求。

（2）SRD工作頻段窄，且SRD數(shù)量及子網(wǎng)數(shù)量往往較大，導(dǎo)致頻率資源十分緊缺[5］，這也是多個子網(wǎng)采用同一個頻表，并采用不同網(wǎng)號的主要原因。另外，某些子網(wǎng)也存在特殊需求，導(dǎo)致這些子網(wǎng)必須采用不同頻表，因此，頻率規(guī)劃求解模型應(yīng)具備多頻表協(xié)同規(guī)劃的能力。

（3）不同的頻表可能具有不同的頻點數(shù)量，從而對頻率規(guī)劃求解模型的擴展性提出要求。

（4）為了防止頻率碰撞或干擾，要求子網(wǎng)間存在一定的頻率間隔，特別是同節(jié)點內(nèi)的多個SRD，相互之間影響較大。頻率規(guī)劃需要兼顧網(wǎng)絡(luò)拓撲中所有節(jié)點內(nèi)SRD的頻率間隔，導(dǎo)致頻率資源統(tǒng)籌規(guī)劃難度大。

針對上述問題，本文以移動Ad-hoc網(wǎng)絡(luò)中無線跳頻頻率規(guī)劃為研究背景，將復(fù)雜網(wǎng)絡(luò)的拓撲抽象出三種組網(wǎng)場景，并通過定義節(jié)點集、子網(wǎng)集、組網(wǎng)集，實現(xiàn)對復(fù)雜組網(wǎng)場景統(tǒng)一描述，以此為基礎(chǔ)，提出一種無線跳頻頻率規(guī)劃求解模型，實現(xiàn)多節(jié)點、多子網(wǎng)、多頻表協(xié)同規(guī)劃，一方面減少網(wǎng)間頻率干擾，提高網(wǎng)絡(luò)運行穩(wěn)定性，另一方面降低頻率統(tǒng)籌規(guī)劃難度，實現(xiàn)頻率規(guī)劃過程自動化，提高頻率規(guī)劃效率。

1 SRD組網(wǎng)場景

實際應(yīng)用中的網(wǎng)絡(luò)拓撲較為復(fù)雜，一個節(jié)點（NODE）可能加入多個子網(wǎng)（MANET），這與節(jié)點內(nèi)部的SRD數(shù)量及組網(wǎng)方式相關(guān)。如圖2所示節(jié)點內(nèi)部包含了3個SRD，說明該節(jié)點在某時刻最多能加入到三個不同的子網(wǎng)中。根據(jù)實際使用需求，節(jié)點內(nèi)部可能存在以下三種組網(wǎng)場景。

圖2 節(jié)點內(nèi)部一臺一網(wǎng)組成示意圖

（1）一臺一網(wǎng)場景（One SRD One MANET，OSOM）

OSOM場景是指節(jié)點內(nèi)一個SRD最多加入一個子網(wǎng)。如圖2所示的SRD1、SRD3分別加入了一個子網(wǎng)，SRD2沒有加入子網(wǎng)。

（2）一臺多網(wǎng)場景（One SRD Many MANET，OSMM）

OSMM場景是指一個SRD具備加入不止一個子網(wǎng)的能力。如圖3所示，SRD1具備加入三個子網(wǎng)的能力，但某時刻SRD1只能加入到MANET1/MANET2/MANET3中的其中之一。此場景主要是為了滿足一臺多用的使用需求，SRD1可以按需切換通信信道以實現(xiàn)不同的通信需求。此場景提高了SRD的使用率，但無疑增大了頻率規(guī)劃的難度，因為需要根據(jù)入網(wǎng)情況可能會給一個SRD規(guī)劃出多個頻率值。

圖3 節(jié)點內(nèi)部一臺多網(wǎng)組成示意圖

（3）多臺一網(wǎng)場景（Many SRD One MANET，MSOM）

MSOM場景是指節(jié)點內(nèi)部存在多個SRD加入到同一個子網(wǎng)，如圖4所示的SRD1和SRD2均加入MANET1。此場景主要是為了達到通信信道備份的目的，但在某時刻SRD1與SRD2不能同時工作，否則會導(dǎo)致頻率干擾及通信環(huán)路問題。

圖4 NODE內(nèi)部多臺一網(wǎng)組成示意圖

上述三種場景互為補充，實際應(yīng)用由三種基本場景組合而成。本文通過定義節(jié)點集、子網(wǎng)集、組網(wǎng)集，以對各種組網(wǎng)場景實現(xiàn)統(tǒng)一描述。

節(jié)點集：GNODE={NODE1,NODE2,NODE3,…}表示網(wǎng)絡(luò)拓撲中的節(jié)點信息。

子網(wǎng)集：GMANET={MANET1,MANET2,MANET3,…}，表示網(wǎng)絡(luò)拓撲中的子網(wǎng)信息。

組網(wǎng)集：GCONNECT={CONNECTMANET|MANET∈GMANET,…}表示網(wǎng)絡(luò)拓撲中的組網(wǎng)信息。針對?CONNECTMANET∈GCONNECT，CONNECTMANET={(NODE,SRD)|NODE∈GNODE,SRD∈NODE}

表示一個子網(wǎng)的入網(wǎng)信息，入網(wǎng)信息又由多個二元組(NODE,SRD)組成。例如：CONNECTMANET1={(NODE1,SRD1),(NODE2,SRD1),(NODE3,SRD2)}，表明節(jié)點NODE1的SRD1，NODE2的SRD1，NODE3的SRD2加入到子網(wǎng)MANET1。

2 頻率規(guī)劃算法

基于節(jié)點集、子網(wǎng)集、組網(wǎng)集，建立頻率規(guī)劃求解模型，并將實際應(yīng)用對頻率的相關(guān)要求轉(zhuǎn)化為算法的約束條件，通過遍歷所有的頻率資源，不斷嘗試為所有子網(wǎng)分配頻率，直至滿足約束條件為止。

2.1 算法描述

頻率資源用頻率集來表示，頻率規(guī)劃算法的輸入描述如下。

（1）組網(wǎng)集：GCONNECT

（2）頻表集：GFTBL={FTBL1,FTBL2,…}

（3）子網(wǎng)與頻表映射：MAP:MANET?FTBL

頻表集包含了若干個頻表，根據(jù)實際應(yīng)用需求維護子網(wǎng)與頻表的映射關(guān)系，支持不同的子網(wǎng)選擇使用不同的頻表，達到多頻表協(xié)同規(guī)劃的目的。不同頻表可能存在不同數(shù)量的頻點，因此在理論上算法不限制頻表中頻點的數(shù)量，以使算法能適應(yīng)多種規(guī)格的頻表應(yīng)用。

為防止頻率干擾，子網(wǎng)之間存在頻率間隔要求，主要包括兩個方面：一是不同子網(wǎng)應(yīng)具有不同的頻率；二是每個節(jié)點加入的子網(wǎng)兩兩之間的頻率間隔應(yīng)大于一個固定值。形成的算法約束條件如下。

約束條件一：?MANETu∈GMANET，?MANETv∈GMANET，u!=v，要求FreqMANETu!=FreqMANETv，其中，F(xiàn)reqMANETu表 示MANETu的 頻 率，F(xiàn)reqMANETv表 示MANETv的頻率。

約束條件二：?NODE∈GNODE，令節(jié)點內(nèi)所有SRD加入的子網(wǎng)集合為GMANET-OF-NODE，顯然存在GMANET-OF-NODE?GMANET。針對?MANETu∈GMANET-OF-NODE，?MANETv∈GMANET-OF-NODE，且u!=v，要求|FreqMANETu-FreqMANETv|＞K，K為一個固定值。

若算法獲得一個解，表示在給定頻率資源和約束條件下能為每個子網(wǎng)分配出頻率資源，得到集合{FreqMANET|MANET∈GMANET}，其中，F(xiàn)reqMANET為一個子網(wǎng)的頻率；否則，算法無解。

2.2 頻率規(guī)劃求解模型

求解模型如圖5所示，以圖論中的樹作為算法求解的基礎(chǔ)，求解過程采用回溯法，為了減少計算時間，通過深度優(yōu)先策略在構(gòu)建樹的同時實現(xiàn)求解。

圖5 頻率規(guī)劃求解模型

當(dāng)構(gòu)建一個樹節(jié)點時，需要先判斷當(dāng)前約束條件是否成立，若約束條件成立，則構(gòu)建此樹節(jié)點，并繼續(xù)縱深至下一層；若約束條件不成立，則無法創(chuàng)建該樹節(jié)點，此時就回溯至上一層節(jié)點。

樹的節(jié)點（TNode）用一個三元組表示：TNode={MANET，F(xiàn)TBL，F(xiàn)Point}，表示子網(wǎng)MANET采用了頻表FTBL中的頻點FPoint為頻率值。樹的根節(jié)點（Root Tree Node，RTNode）是個空節(jié)點，RTNode={NULL，NULL，NULL}，它僅用于模型建立與算法計算。

樹的深度取決于子網(wǎng)集GMANET中元素的數(shù)量，GMANET中每個元素與樹的一個層級相對應(yīng)，即同一深度的樹節(jié)點表示一個子網(wǎng)的不同頻率取值，如圖5中所示，樹深度為2的節(jié)點均表示MANET1的不同頻率取值，樹深度為3的節(jié)點均表示MANET2的不同頻率取值，依次類推。

通過子網(wǎng)與頻表的映射關(guān)系MAP，可映射出每個子網(wǎng)應(yīng)采用的頻表，頻表中的所有頻點（FPoint）就是該子網(wǎng)可能的頻率取值，因此，某深度的樹節(jié)點最大個數(shù)取決于該子網(wǎng)對應(yīng)頻表的容量。

由于資源總量有限，而子網(wǎng)數(shù)量較大，往往多個子網(wǎng)共用頻表，根據(jù)約束條件，子網(wǎng)的頻率取值不能相同，因此，為一個子網(wǎng)分配頻率時，需要判斷該頻點是否已經(jīng)被使用。

算法執(zhí)行結(jié)束時，存在兩種情況，一是算法獲得滿足約束條件的一個解后立即退出，此時GMANET中所有子網(wǎng)均分得頻率，且樹的一個分支到達葉子節(jié)點，樹的深度為GMANET中子網(wǎng)的數(shù)量加1；二是遍歷完成所有可能情況后算法終止，此種情況表明算法無解，進而表明在給定約束條件下，當(dāng)前的頻率資源無法滿足網(wǎng)絡(luò)拓撲需求，因此，此時需要對頻率資源進行調(diào)整或適當(dāng)放寬約束條件。

算法執(zhí)行流程如圖6所示，基本步驟描述如下：

第①步：創(chuàng)建樹的根節(jié)點RTNode，令算法的當(dāng)前處理節(jié)點為Current，初始情況下Current=RTNode；

第②步：嘗試為Current創(chuàng)建子節(jié)點X，根據(jù)X={MANET，F(xiàn)TBL，F(xiàn)Value}，需先確定出X對應(yīng)子網(wǎng)，通過遍歷子網(wǎng)集GMANET，獲取出一個子網(wǎng)作為節(jié)點X對應(yīng)的子網(wǎng)，進入下一步；若子網(wǎng)集GMANET遍歷結(jié)束，進入第⑧步；

第③步：根據(jù)上一步獲取的子網(wǎng)，通過MAP映射出該子網(wǎng)采用的頻表索引，基于頻表索引在頻表集GFTBL中獲取該頻表的所有頻點；

第④步：通過遍歷依次獲取出上一步所得頻表中的每個頻點，遍歷過程需要跳過已經(jīng)被其它子網(wǎng)占用的頻點。若該頻表遍歷結(jié)束，表明無法給該子網(wǎng)尋找到一個合適的頻點，進入下一步；否則，獲取到該頻表的一個頻點，進入第⑥步；

圖6 頻率規(guī)劃算法流程

第⑤步：判斷當(dāng)前節(jié)點Current的父節(jié)點（設(shè)為F）是否為NULL，若F為NULL，表明此時Current=RTNode，即算法無法為RTNode創(chuàng)建出子節(jié)點，進入第⑧步；若F不為NULL，回溯至樹的上一層，即令Current=F，進入第②步，繼續(xù)嘗試為Current創(chuàng)建子節(jié)點；

第⑥步：針對遍歷所得的一個頻點，判斷若將此頻點分配給當(dāng)前MANET，是否滿足算法約束條件，若不滿足，進入第④步嘗試下一個頻點；若滿足則進入下一步；

第⑦步：創(chuàng)建樹節(jié)點X，使X為Current的子節(jié)點，并更新Current為X，繼續(xù)為Current嘗試創(chuàng)建子節(jié)點，進入第②步。

第⑧步：算法結(jié)束。分為兩種情況，一是若子網(wǎng)集中的所有子網(wǎng)均分配得到一個頻率值或樹的深度等于子網(wǎng)集中元素數(shù)量加1，則表明算法獲得了一個解；二是表明頻率資源不足，無法獲取一個滿足約束條件的解。

3 算法時間復(fù)雜度分析及優(yōu)化建議

3.1 算法時間復(fù)雜度分析

考慮算法最壞的情況是：

（1）假定子網(wǎng)集中的子網(wǎng)個數(shù)為N，每個子網(wǎng)采用不同的頻表，每個頻表中頻點個數(shù)最大為M；

（2）算法無解且窮盡了所有可能的情況，每個樹節(jié)點均有M個子節(jié)點，整棵樹是個完整M叉樹，如圖7所示。

圖7 算法復(fù)雜度分析

遍歷完整棵樹，算法的時間復(fù)雜度為O(M+M2+M3+…+MN)=O(MN)，當(dāng)頻點個數(shù)M及子網(wǎng)個數(shù)N較大，且在給定條件下算法無解導(dǎo)致算法完整遍歷整棵樹時，將需要大量的計算時間。

3.2 算法流程優(yōu)化

可以從兩個方面入手對算法進行優(yōu)化，一是優(yōu)化節(jié)點入網(wǎng)集GMANET-OF-NODE以降低頻率資源開銷，有利于為更多的子網(wǎng)規(guī)劃出頻率資源；二是通過優(yōu)化子網(wǎng)集GMANET中的元素順序，在算法存在解的情況下，有利于較早獲得算法的解，縮短算法執(zhí)行時間。

（1）優(yōu)化節(jié)點入網(wǎng)集

以圖3為例，SRD1加入了MANET1、MANET2、MANET3，SRD2加入了MANET4，SRD3加入了MANET5。當(dāng)為上述子網(wǎng)分配頻率資源并進行約束條件判斷時，存在兩種情形。

情形一：

該節(jié)點的入網(wǎng)集為：

GMANET-OF-NODE={MANET1,MANET2,MANET3,MANET4,MANET5}，假設(shè)GMANET-OF-NODE中每個子網(wǎng)對應(yīng)的頻率為：G1={FreqMANET1,FreqMANET2,FreqMANET3,FreqMANET4,FreqMANET5}。

情形二：

上文已經(jīng)提及，某時刻SRD1只能加入三者MANET1、MANET2、MANET3之一，因此該節(jié)點的入網(wǎng)集GMANET-OF-NODE只能是下面三種可能之一：

可能一：

GMANET-OF-NODE={MANET1,MANET4,MANET5}

可能二：

GMANET-OF-NODE={MANET2,MANET4,MANET5}

可能三：

GMANET-OF-NODE={MANET3,MANET4,MANET5}

上述三種可能對應(yīng)的頻率分別為G2、G3、G4：

G2={FreqMANET1,FreqMANET4,FreqMANET5}

G3={FreqMANET2,FreqMANET4,FreqMANET5}

G4={FreqMANET3,FreqMANET4,FreqMANET5}

令：

J1=G1中兩兩之間頻率間隔大于固定值K；

J2=G2中兩兩之間頻率間隔大于固定值K；

J3=G3中兩兩之間頻率間隔大于固定值K；

J4=G4中兩兩之間頻率間隔大于固定值K。

比較上述兩種情形，J1與（J2&J3&J4）均能滿足算法的約束條件。從算法實現(xiàn)的難易角度而言，J1較（J2&J3&J4）容易；但從對頻率資源要求角度而言，J1比（J2&J3&J4）苛刻一些，因為（J2&J3&J4）并不要求FreqMANET1、FreqMANET2、FreqMANET3兩兩之間的頻率間隔。因此，算法實現(xiàn)建議采用（J2&J3&J4）來判斷約束條件滿足情況。

（2）優(yōu)化子網(wǎng)集中元素順序

算法的求解過程是根據(jù)約束條件的滿足情況進行回溯，減少回溯次數(shù)，有利于減少算法執(zhí)行時間。導(dǎo)致回溯的原因是約束條件無法滿足，無法創(chuàng)建樹的節(jié)點，需要回溯至父節(jié)點重新利用頻表中的其它頻點進行嘗試。

通過約束條件可知，發(fā)現(xiàn)節(jié)點入網(wǎng)集GMANET-OF-NODE中元素數(shù)量越大，該節(jié)點對頻率資源的要求就越苛刻，因此，根據(jù)節(jié)點入網(wǎng)集的元素數(shù)量進行排序，使算法先處理數(shù)量較大的節(jié)點入網(wǎng)集中的子網(wǎng)。例如，節(jié)點NODE1、NODE2、NODE3的節(jié)點入網(wǎng)集如下：

NODE1：GMANET-OF-NODE1={MANET1,MANET4}

NODE2：GMANET-OF-NODE2={MANET1,MANET2,MANET3}

GMANET-OF-NODE3={MANET2}

按照節(jié)點入網(wǎng)集元素數(shù)量多少的排序結(jié)果為：NODE2、NODE1、NODE3，其中，NODE2對頻率資源要求最高，因為需要滿足三個子網(wǎng)之間的頻率間隔。

根據(jù)排序結(jié)果，依次將各節(jié)點入網(wǎng)集中的子網(wǎng)加入到子網(wǎng)集，得到GMANET={MANET1,MANET2,MANET3,MANET4}。根據(jù)子網(wǎng)集中元素順序可以看出，NODE2的節(jié)點入網(wǎng)集中的子網(wǎng)會優(yōu)先得到處理（位置靠前），此舉可以在構(gòu)建求解樹過程中讓回溯操作大概率地發(fā)生在深度較小的樹節(jié)點，從而減少在深度較大的樹節(jié)點發(fā)生回溯操作的幾率，即讓需要發(fā)生回溯的操作盡可能地提前，使算法減少執(zhí)行時間。

4 結(jié) 語

本文以移動Ad-hoc網(wǎng)絡(luò)的無線跳頻頻率規(guī)劃為研究背景，針對組網(wǎng)場景復(fù)雜多變、多頻表混合使用、頻表中頻點數(shù)量不統(tǒng)一、子網(wǎng)間存在頻率間隔要求等問題，本文完成工作如下：

（1）將網(wǎng)絡(luò)拓撲中復(fù)雜多變的組網(wǎng)關(guān)系，抽象出三種基本的組網(wǎng)場景，并通過定義節(jié)點集、子網(wǎng)集、組網(wǎng)集，實現(xiàn)對各種復(fù)雜組網(wǎng)場景統(tǒng)一描述。

（2）構(gòu)建頻率規(guī)劃求解模型，先后闡述了算法輸入、約束條件、求解過程、算法輸出，實現(xiàn)了多節(jié)點、多子網(wǎng)、多頻表資源協(xié)同規(guī)劃，降低了頻率資源統(tǒng)籌規(guī)劃難度，提升了頻率規(guī)劃效率。

（3）基于算法流程，通過優(yōu)化節(jié)點入網(wǎng)集以節(jié)省頻率資源開銷；通過優(yōu)化子網(wǎng)集中元素順序，有利于減少算法執(zhí)行時間。

本文算法從理論上回答了在給定頻率資源和約束條件下，能否為網(wǎng)絡(luò)拓撲中所有子網(wǎng)分配出頻率資源的問題。并分析了算法的時間復(fù)雜度，指出當(dāng)算法無解時可能會耗費大量的計算時間，因此，如何結(jié)合實際具體應(yīng)用，優(yōu)化算法求解過程，減少算法求解時間是下一步研究的主要工作。