一種基于鄰域信息的多信道自適應(yīng)建網(wǎng)算法

劉 琰 趙海濤 李 衛(wèi) 張 姣 劉松旺 魏急波

（1.國防科技大學(xué)電子科學(xué)學(xué)院，湖南長沙 410073；2.中國人民解放軍31401部隊，黑龍江哈爾濱 150090；3.中國人民解放軍75835部隊，廣東廣州 510000）

1 引言

無線自組網(wǎng)（Wireless Ad Hoc Networks）憑借無中心節(jié)點、自組織且不需要任何基礎(chǔ)通信設(shè)備支持的特點，使其具有較強的靈活性、抗毀性以及可擴展的能力，可以運用于緊急救援、環(huán)境監(jiān)測、戰(zhàn)場通信等領(lǐng)域［1-3］。在許多無線自組網(wǎng)的應(yīng)用場景，比如無線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)等系統(tǒng)中，為提高網(wǎng)絡(luò)構(gòu)建的魯棒性和帶寬利用率，網(wǎng)絡(luò)中的頻譜資源通常是多信道的。但是在頻譜競爭激烈或者存在惡意干擾的情況下，各節(jié)點的實際可用信道并不相同，具有非均勻的信道可用性。這種非均勻的信道可用性嚴(yán)重影響了自組網(wǎng)的建網(wǎng)過程。對于無線自組網(wǎng)來說，依靠可用網(wǎng)絡(luò)資源構(gòu)建穩(wěn)健、連通的網(wǎng)絡(luò)是一個非常重要的過程，是拓?fù)涔芾?、路由尋址、性能?yōu)化等一切后續(xù)行為的基礎(chǔ)。

無線自組網(wǎng)的建網(wǎng)過程通?？梢苑譃閮蓚€階段：鄰居發(fā)現(xiàn)階段和網(wǎng)絡(luò)形成階段。節(jié)點在鄰居發(fā)現(xiàn)前不知道其他節(jié)點是否存在以及可接入哪些信道。傳統(tǒng)的鄰居發(fā)現(xiàn)機制依靠一個網(wǎng)絡(luò)中所有用戶都可以使用的公共控制信道［4］，它便于協(xié)調(diào)相鄰節(jié)點之間交換感知信息（如信道和路由信息），以建立相鄰節(jié)點間的通信鏈路。許多研究假設(shè)網(wǎng)絡(luò)中始終存在預(yù)先分配的公共控制信道［5-6］，但是在實際的復(fù)雜頻譜環(huán)境中，找到對全網(wǎng)節(jié)點都可用的公共控制信道頻段是非常困難的。文獻［7］提出利用多跳聚類的方法進行公共控制信道的最優(yōu)分配，文獻［8］提出使用全雙工設(shè)備建立公共控制信道，但是這兩種算法只能建立部分節(jié)點共用的公共控制信道，需要多條公共控制信道才能控制整個網(wǎng)絡(luò)。值得注意的是，公共控制信道很容易成為被干擾和攻擊的對象，公共控制信道一旦被干擾將造成網(wǎng)絡(luò)的癱瘓。針對沒有公共控制信道的鄰居發(fā)現(xiàn)問題，目前主要利用基于信道跳變的盲交匯算法解決［9-11］，節(jié)點根據(jù)自己的信道跳變序列在不同的時隙切換到不同的信道，一旦兩個節(jié)點在同一時隙切換到同一可用信道，它們就可以交換信息。文獻［12］通過分析時隙重疊和信道確定性，提出一種多素數(shù)擴展的盲交匯算法，用于提高節(jié)點之間交匯的速度和穩(wěn)定性。文獻［13］提出了一種多無線電的盲交匯算法，給節(jié)點統(tǒng)一分配不同的跳變序列，有效減少了節(jié)點的交匯時間。文獻［14］的盲交匯算法能夠應(yīng)用兩種信道跳變序列，成功縮小了信道跳變序列的漸近逼近比。現(xiàn)有的盲交匯算法雖然在兩個或多個節(jié)點的交匯問題上取得了不錯的效果，但是不考慮整個網(wǎng)絡(luò)的形成，如果單純使用信道跳變算法進行建網(wǎng)，所有節(jié)點在多個信道之間頻繁地進行信道感知、接入與建鏈，尤其是網(wǎng)絡(luò)規(guī)模較大時，將造成嚴(yán)重的競爭沖突，大大延長建網(wǎng)時間。

網(wǎng)絡(luò)的形成階段主要關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)的選擇。無線自組網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)可以分為平面結(jié)構(gòu)和分簇結(jié)構(gòu)，在分簇結(jié)構(gòu)中，網(wǎng)絡(luò)節(jié)點組織成若干個稱為簇的邏輯集群，每個簇群中的節(jié)點具有不同的身份，如簇首、網(wǎng)關(guān)節(jié)點或普通簇成員。與平面結(jié)構(gòu)相比，分簇結(jié)構(gòu)能夠減輕網(wǎng)絡(luò)局部的拓?fù)浣Y(jié)構(gòu)變化對整個網(wǎng)絡(luò)的影響，比較適用于需要動態(tài)變化的無線自組網(wǎng)［15］。近年來，國內(nèi)外學(xué)者從不同的應(yīng)用需求出發(fā)對分簇算法進行設(shè)計［16-18］。文獻［19］提出了基于距離能量評估的分簇算法，該算法能夠有效提高無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命，但是沒有考慮節(jié)點的最大通信距離的限制，無法應(yīng)用在部署范圍較大的實際通信場景中。文獻［20］利用灰狼優(yōu)化算法進行網(wǎng)絡(luò)的分簇，考慮吞吐量、延遲和通信開銷等因素，以保證網(wǎng)絡(luò)的服務(wù)質(zhì)量，但是算法需要掌握網(wǎng)絡(luò)的全局信息，在沒有中心控制器的自組網(wǎng)中無法保證全局信息的有效獲取。文獻［21］通過對無人機的軌跡和分簇進行研究，提高了網(wǎng)絡(luò)的抗干擾能力，然而算法針對的是單信道網(wǎng)絡(luò)，不適用于存在非均勻信道可用性的多信道網(wǎng)絡(luò)。綜上所述，在每個節(jié)點無法感知全網(wǎng)拓?fù)洹⑵渌泄?jié)點的可用頻譜，以及無法獲得同步信息的實際場景中，無線自組網(wǎng)的建網(wǎng)問題沒有很好的解決辦法。

本文主要針對實際場景中多信道自組網(wǎng)的建網(wǎng)問題進行研究，既不是節(jié)能部署問題［22-23］，也不是拓?fù)渚S護問題［24-25］。本文研究的重點是在實際應(yīng)用場景的限定條件下，節(jié)點以較小的通信開銷建立完整的多信道網(wǎng)絡(luò)，提出了一種多信道自適應(yīng)建網(wǎng)算法（Multi-channel Adaptive Network Establishment，MANE）。設(shè)計了一個基于鄰域信息的建網(wǎng)策略，并且針對建網(wǎng)過程中節(jié)點對信道和簇首選擇問題，分別提出了信道質(zhì)量評價算法和鄰居簇首評價算法。仿真結(jié)果表明，所提算法能夠利用有限的鄰域信息建立分簇結(jié)構(gòu)的網(wǎng)絡(luò)。

2 系統(tǒng)模型

假設(shè)在一個部署范圍內(nèi)，存在N(N≥3)個節(jié)點，且節(jié)點被編號為1，2，…，N，用U={U1，U2，…，UN}表示。將網(wǎng)絡(luò)中的頻譜劃分為M(M≥2)個非重疊的信道，總信道用C={C1，C2，…，CM}表示?？紤]到非均勻的信道可用性，定義節(jié)點Ui∈U感知到的可用信道集合為CUi∈C。關(guān)于節(jié)點通信功能的假設(shè)是：

（1）每個節(jié)點都具備一個半雙工的收發(fā)器，可以實現(xiàn)頻譜感知，發(fā)現(xiàn)其可用信道并自由切換到任意一個信道進行數(shù)據(jù)通信；

（2）如果一個節(jié)點位于另一個節(jié)點的通信范圍內(nèi)，則兩個節(jié)點可以在相同的可用信道上通信；

（3）所有節(jié)點可以獲取自身的地理位置信息（利用北斗衛(wèi)星導(dǎo)航系統(tǒng)或者全球定位系統(tǒng)獲?。?/p>

考慮在節(jié)點啟動或網(wǎng)絡(luò)遭受攻擊等實際應(yīng)用場景中，網(wǎng)絡(luò)中沒有中心控制器的協(xié)調(diào)和可用的公共控制信道，所有節(jié)點無法感知全局信息，且無法與其他節(jié)點保持精確的時間同步，無線自組網(wǎng)構(gòu)建困難。針對以上問題，本文設(shè)計了多信道自適應(yīng)建網(wǎng)方法，網(wǎng)絡(luò)中的每個節(jié)點可以在任何時隙激活，然后開始進行自適應(yīng)建網(wǎng)，最終建立一個分簇結(jié)構(gòu)的網(wǎng)絡(luò)。典型的分簇結(jié)構(gòu)網(wǎng)絡(luò)如圖1 所示，其中簇首負(fù)責(zé)維持簇群，網(wǎng)關(guān)節(jié)點負(fù)責(zé)連接兩個相鄰的簇群，同一簇群內(nèi)的節(jié)點使用一條主用信道進行通信。

圖1 典型的分簇結(jié)構(gòu)網(wǎng)絡(luò)Fig.1 A typical clustered network

3 多信道自適應(yīng)建網(wǎng)算法

3.1 基本思路

本文所提多信道自適應(yīng)建網(wǎng)算法（MANE）的建網(wǎng)策略將鄰居發(fā)現(xiàn)階段和網(wǎng)絡(luò)形成階段融合在一起，使節(jié)點能夠以自身信息為基礎(chǔ)，通過可用信道情況、鄰居簇首情況等有限的鄰域信息確定自身身份（簇首、網(wǎng)關(guān)節(jié)點或普通簇成員），從而完成自適應(yīng)建網(wǎng)，具體的建網(wǎng)策略如圖2 所示。當(dāng)一個節(jié)點上電激活后將進行以下步驟：

圖2 建網(wǎng)策略流程圖Fig.2 Flow chart of network establishment strategy

步驟1節(jié)點對其可用信道情況和鄰居簇首情況進行感知。節(jié)點依次在其可用信道上進行切換，在每個可用信道上停留一段時間，檢測信道參數(shù)并接收鄰居簇首發(fā)出的HELLO數(shù)據(jù)包，完成一次所有信道切換的時間為一個搜索周期。信道參數(shù)是指帶寬、信干噪比、相干帶寬、相干時間等。HELLO 數(shù)據(jù)包中含有節(jié)點ID、可用信道、簇規(guī)模、地理位置等信息。

步驟2建立可用信道排序列表和鄰居簇首排序列表。節(jié)點使用信道質(zhì)量評價算法得到可用信道排序列表（設(shè)為列表A），使用鄰居簇首評價算法得到鄰居簇首排序列表（設(shè)為列表B）。兩種評價算法將分別在第3.2節(jié)、第3.3節(jié)進行討論。

步驟3確定節(jié)點身份。情況1：如果節(jié)點的鄰居簇首排序列表為空，則節(jié)點確定其身份為簇首，選擇節(jié)點的可用信道排序列表中第一個可用信道作為簇內(nèi)主用信道，并在該信道上發(fā)送HELLO數(shù)據(jù)包。情況2：如果鄰居簇首排序列表不為空，則節(jié)點確定身份為普通簇成員，選擇鄰居簇首排序列表中第一個鄰居簇首作為其簇首，然后以RTS/CTS 握手的方式與簇首建立連接。

步驟4如果節(jié)點身份為普通簇成員，并且能夠與另一個簇的任何節(jié)點建立連接，則節(jié)點修改其身份為網(wǎng)關(guān)節(jié)點。

步驟5如果節(jié)點身份為簇首，但是長時間沒有任何普通簇成員，則放棄其簇首身份，返回步驟1。

節(jié)點根據(jù)感知到的HELLO 數(shù)據(jù)包判斷周圍是否存在鄰居簇首，從而確定其身份。這種方式不依靠鄰居節(jié)點之間頻繁的信息交互，能夠減少建網(wǎng)開銷和建網(wǎng)時間，但具有一定的隨機性。為了保證構(gòu)成網(wǎng)絡(luò)的性能，需要重視兩個關(guān)鍵問題。一是簇首需要選擇一個最合適的可用信道作為主用信道。同一簇內(nèi)的節(jié)點依靠主用信道進行通信，因此需要對節(jié)點可用信道的信道質(zhì)量進行評價，將評價結(jié)果作為簇首選擇主用信道的依據(jù)；二是普通簇成員需要選擇一個最合適的鄰居簇首作為其簇首。鄰居簇首在各自的主用信道上發(fā)送HELLO 數(shù)據(jù)包來等待普通簇成員的加入，導(dǎo)致普通簇成員周圍可能存在多個鄰居簇首，因此需要一個能夠綜合評價鄰居簇首的算法，指導(dǎo)普通簇成員對于簇首的選擇。目前已有的一些關(guān)于信道質(zhì)量評價［26］和簇首質(zhì)量評價［27］的研究，都只是單獨考慮信道質(zhì)量或者簇首質(zhì)量，并沒有自組網(wǎng)節(jié)點快速建網(wǎng)的需求。因此本文結(jié)合建網(wǎng)過程，根據(jù)感知到的鄰域信息，提出了信道質(zhì)量評價算法和鄰居簇首評價算法。

3.2 信道質(zhì)量評價算法

首先利用節(jié)點可用信道的信道參數(shù)構(gòu)成線性加權(quán)的信道質(zhì)量評價函數(shù)，其中各信道參數(shù)的權(quán)重值還未確定。然后根據(jù)最大熵原理［28］建立多目標(biāo)規(guī)劃模型，解出權(quán)重的表達式。最后根據(jù)實際網(wǎng)絡(luò)需求設(shè)定主觀約束條件，得到滿足主觀約束條件的權(quán)重值，進而求出節(jié)點可用信道的信道質(zhì)量評價函數(shù)值。

設(shè)節(jié)點Up感知到其可用信道總數(shù)為n個，記為CUp={CUp(1)，CUp(2)，…，CUp(n)}，CUp(i) 表示節(jié)點Up的第i個可用信道?？捎眯诺赖男诺绤?shù)有m個，記為G={G1，G2，…，Gm}。CUp(i)的第j個信道參數(shù)Gj的值記為eij(i=1，2，…，n；j=1，2，…，m)。

節(jié)點Up感知到的n個可用信道共有n×m個信道參數(shù)值，構(gòu)成評價矩陣E，即

為通過公式（2）對信道參數(shù)進行歸一化處理，得到歸一化評價矩陣F，即

設(shè)m個信道參數(shù)的權(quán)重值為wj，節(jié)點Up對其可用信道CUp(i)的線性加權(quán)的信道質(zhì)量評價函數(shù)為：

由于各指標(biāo)的權(quán)重是具有不確定性的隨機變量，可以利用最大熵原理保證各信道參數(shù)權(quán)重的公平性。同時，當(dāng)滿足各信道參數(shù)值與信道參數(shù)平均值的加權(quán)方差最小時，所求的權(quán)重才最合理。建立目標(biāo)規(guī)劃函數(shù)為：

其中參數(shù)δ∈[0，1]，求解目標(biāo)規(guī)劃函數(shù)得到權(quán)重wj：

需要說明的是，公式（8）在求解權(quán)重wj時，需要根據(jù)實際情況確定參數(shù)δ。例如：在實際應(yīng)用中將帶寬、信干噪比作為最重要的指標(biāo)，相干帶寬、相干時間作為次要指標(biāo)，則可以增加主觀約束條件為w1≈w2>w3≈w4。通過改變參數(shù)δ的值，獲取滿足主觀約束條件的權(quán)值解w1、w2、w3、w4。將權(quán)重解代入公式（6）即可求出節(jié)點Up可用信道的質(zhì)量評價函數(shù)值JE(Up，CUp(i))。根據(jù)JE(Up，CUp(i))的大小即可實現(xiàn)對可用信道的信道質(zhì)量從高至低排序，得到節(jié)點Up的可用信道排序列表。

3.3 鄰居簇首評價算法

生物實驗展示多頭絨泡菌在覓食過程中能夠自主尋找到迷宮的最短路徑，形成的覓食網(wǎng)絡(luò)可以和人工設(shè)計的鐵道網(wǎng)絡(luò)相媲美，說明多頭絨泡菌具有良好的自組織、自優(yōu)化等智能行為［29］。多頭絨泡菌的菌絲可以抽象為有液體流動的導(dǎo)管，利用導(dǎo)管的半徑和導(dǎo)管內(nèi)部流體之間的反饋模擬多頭絨泡菌的覓食行為，即流體通量高時導(dǎo)管半徑增加，流體通量低時導(dǎo)管半徑減小［30］。流體通量表示為：

其中，Qij是通過i、j兩點之間導(dǎo)管的流體通量，Dij=是導(dǎo)管傳輸率，r是導(dǎo)管的半徑；η是導(dǎo)管內(nèi)流體的黏度。ΔPij=Pi-Pj是導(dǎo)管兩端點的壓力差，Lij是導(dǎo)管的長度。

由于多頭絨泡菌通過擴張和收縮導(dǎo)管來尋找食物，其調(diào)節(jié)函數(shù)表示為為導(dǎo)管的衰減率。f(Q)=Qu(u>0)為常用函數(shù)形式，可以得到調(diào)節(jié)函數(shù)：

本文將多頭絨泡菌模型引入到節(jié)點對于鄰居簇首評價中，建立了鄰居簇首評價映射模型，如圖3所示。將多頭絨泡菌的菌群映射為節(jié)點，食物映射為鄰居簇首，菌群覓食過程中發(fā)散的導(dǎo)管映射為節(jié)點與多個鄰居簇首之間的虛擬連接。

圖3 鄰居簇首評價映射模型Fig.3 Neighbor cluster head evaluation mapping model

導(dǎo)管的兩個端點i、j映射為節(jié)點Ui和一個鄰居簇首Uj。采用無量綱分析法進行變量的替換，首先，Dij是導(dǎo)管傳輸率，是由導(dǎo)管半徑和流體黏度決定的固有屬性，因此用公式（6）中的信道質(zhì)量評價函數(shù)值代替Dij，其中為鄰居簇首Uj的主用信道；其次，Lij表示管狀體的長度，其數(shù)值越大越不利，在無線自組網(wǎng)中，兩個節(jié)點的距離越大越不利，因此用兩個節(jié)點間的距離代替導(dǎo)管長度Lij；ΔPij表示導(dǎo)管兩端流體的壓力，是判斷連接兩點的導(dǎo)管是否存在的關(guān)鍵，其數(shù)值越大越有利。在分簇結(jié)構(gòu)的網(wǎng)絡(luò)中，節(jié)點連接簇規(guī)模大的簇首，有利于減少簇間信道協(xié)商的信令開銷，同時節(jié)點連接與其相同可用信道數(shù)量多的簇首，有利于連接穩(wěn)定。公式（10）可以轉(zhuǎn)化為公式（11）：

其中，EFij是節(jié)點Ui對于鄰居簇首Uj的評價函數(shù)值。是節(jié)點Ui對于鄰居簇首Uj的主用信道的信道質(zhì)量評價函數(shù)值，由可用信道排序列表給出。Sij表示鄰居簇首Uj的簇規(guī)模的歸一化值。Nij是節(jié)點Ui與鄰居簇首Uj的相同可用信道數(shù)量的歸一化值。k1、k2為權(quán)重系數(shù)，滿足k1+k2=1。將節(jié)點Ui的鄰居簇首按照評價函數(shù)值EFij的大小進行排序，得到節(jié)點Ui的鄰居簇首排序列表。

4 仿真分析

4.1 仿真參數(shù)設(shè)置

利用MATLAB仿真軟件對所提MANE算法的性能進行實驗評估。網(wǎng)絡(luò)部署范圍是1000 m×1000 m的矩形區(qū)域，將網(wǎng)絡(luò)的初始狀態(tài)設(shè)置為節(jié)點相互之間完全失聯(lián)。各節(jié)點的最大通信距離均為300 m，其可用信道是從總信道中隨機選取的部分信道。RTS/CTS握手機制和信道情況的參數(shù)設(shè)置如表1所示，其中退避時隙時長、短幀間隔和分布式幀間隔按照802.11 協(xié)議的標(biāo)準(zhǔn)進行設(shè)置［31］，信噪比、帶寬、相干帶寬、相干時間的范圍依據(jù)相關(guān)文獻設(shè)計［32-33］。

表1 主要的仿真參數(shù)和數(shù)值Tab.1 Main simulation parameters and values

4.2 仿真場景示例

為便于直觀展示仿真結(jié)果，示例中設(shè)置20個節(jié)點與6 個總信道，圖4 給出了在節(jié)點隨機部署情況下MANE 的建網(wǎng)過程，圖中節(jié)點編號用數(shù)字1 至20表示，節(jié)點下方的括號內(nèi)標(biāo)有其可用信道的編號，簇內(nèi)連接和簇間連接分別用實線和虛線表示，連線的權(quán)值表示節(jié)點之間連接所使用的信道編號。圖4（a）是節(jié)點完全失聯(lián)的初始狀態(tài)，各節(jié)點的可用信道隨機。圖4（b）至圖4（e）是節(jié)點正在建網(wǎng)的中間狀態(tài)，圖4（f）是節(jié)點完成建網(wǎng)的最終狀態(tài)。由圖4 可以看出，節(jié)點利用感知到的鄰域信息，自適應(yīng)判斷自身角色，選擇可用信道和鄰居簇首，逐步建成了圖4（f）所示的6個簇群（如節(jié)點13為簇首，節(jié)點9為普通簇成員，節(jié)點4、節(jié)點8 和節(jié)點11 為網(wǎng)關(guān)節(jié)點）。為顯示MANE 算法的適用性，圖5 給出了算法在“均勻部署”、“帶狀部署”和“隨機部署”三種典型部署情況下的最終建網(wǎng)結(jié)果，可以看到MANE 都能完成快速建網(wǎng)任務(wù)。

圖4 MANE的建網(wǎng)過程Fig.4 Network establishment process of MANE

圖5 不同情況下的建網(wǎng)結(jié)果Fig.5 Network construction results in different situations

4.3 系統(tǒng)性能分析

為了有效評價本文所構(gòu)建的無線自組網(wǎng)的系統(tǒng)性能，分別采用平均信息交互次數(shù)、平均簇內(nèi)公共信道數(shù)量以及平均簇規(guī)模作為主要評估指標(biāo)。

（1）平均信息交互次數(shù)是在建網(wǎng)過程中節(jié)點之間信息交互的平均次數(shù)，平均信息交互次數(shù)越小，代表建網(wǎng)開銷越小、建網(wǎng)時間越短。

（2）平均簇內(nèi)公共信道數(shù)量是各簇群中所有節(jié)點的相同可用信道數(shù)量的均值，平均簇內(nèi)公共信道數(shù)量越大，代表網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越穩(wěn)定。

（3）簇規(guī)模指的是一個簇群所包含的節(jié)點數(shù)量，平均簇規(guī)模是整個部署范圍內(nèi)各簇群規(guī)模的均值［34-35］。需要注意的是，本文研究的場景中每個簇群都是由簇首及其一跳范圍內(nèi)的節(jié)點構(gòu)成的，只有在簇首最大通信距離內(nèi)的節(jié)點才有可能入簇，不考慮利用網(wǎng)關(guān)節(jié)點和普通簇成員不斷擴大簇規(guī)模，并且各節(jié)點的實際可用信道并不相同，因此簇規(guī)模一般是比較有限的。雖然網(wǎng)絡(luò)的部署范圍和節(jié)點的通信距離不可避免地會對平均簇規(guī)模造成影響，部署范圍越大、通信距離越小，平均簇規(guī)模就越小，但是在部署范圍和通信距離確定的情況下，總是希望平均簇規(guī)模盡量大。平均簇規(guī)模能夠一定程度上代表網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的高效性，因為平均簇規(guī)模過小，將導(dǎo)致大量開銷用于簇間通信，嚴(yán)重影響網(wǎng)絡(luò)傳輸性能。

4.3.1 評價算法對MANE性能的影響

MANE利用信道質(zhì)量評價算法和鄰居簇首評價算法指導(dǎo)節(jié)點進行信道和簇首的選擇。為方便研究兩種評價算法對MANE 性能的影響，將使用建網(wǎng)策略但不使用兩種評價算法的MANE 命名為LMANE。具體來說，L-MANE 不使用評價算法，其可用信道排序列表和鄰居簇首排序列表是不依據(jù)評價函數(shù)值的隨機排序。由于使用評價算法不增加建網(wǎng)開銷，所以重點研究評價算法在平均簇內(nèi)公共信道數(shù)量和平均簇規(guī)模方面對MANE性能的影響。

（1）評價算法對平均簇內(nèi)公共信道數(shù)量的影響。

圖6（a）顯示，對于MANE 和L-MANE，當(dāng)總信道數(shù)量M一定時，平均簇內(nèi)公共信道數(shù)量隨著節(jié)點數(shù)量的增加而減少。當(dāng)節(jié)點數(shù)量一定時，平均簇內(nèi)公共信道數(shù)量隨著總信道數(shù)量的增加而增加。在相同的條件下，MANE 的平均簇內(nèi)公共信道數(shù)量高于L-MANE。圖6（b）顯示，相較于L-MANE，使用了評價算法的MANE 在平均簇內(nèi)公共信道數(shù)量上增加了18.20 %。由此可見，評價算法能夠明顯增加平均簇內(nèi)公共信道數(shù)量，提高網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性。

圖6 評價算法對平均簇內(nèi)公共信道數(shù)量的影響Fig.6 The effect of evaluation algorithms on the average number of common channels within the cluster

（2）評價算法對平均簇規(guī)模的影響。

圖7（a）顯示，隨著節(jié)點數(shù)量的增加，MANE 和L-MANE 的平均簇規(guī)模會隨之增加，但是MANE 的平均簇規(guī)模明顯高于L-MANE。圖7（b）顯示，使用了評價算法的MANE在相對于L-MANE的平均簇規(guī)模增加了77.28 %。由此可見，評價算法能夠明顯增加平均簇規(guī)模，使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更加高效。

圖7 評價算法對平均簇規(guī)模的影響Fig.7 The effect of evaluation algorithms on the average cluster size

4.3.2 搜索周期對整體網(wǎng)絡(luò)性能的影響

為驗證搜索周期對整體網(wǎng)絡(luò)性能的影響，本文在不同信道停留時間下進行建網(wǎng)實驗，并且采用多獨立樣本Kruskal-Wallis 秩和檢驗分析網(wǎng)絡(luò)性能之間是否存在顯著性差異［36］。首先隨機生成100種初始部署，分別設(shè)置信道停留時間為1 s、2 s、3 s、4 s，通過MANE 進行建網(wǎng)，得到A、B、C、D 共4 組建網(wǎng)結(jié)果。然后，針對每組的100個建網(wǎng)結(jié)果，分別計算平均簇內(nèi)公共信道數(shù)量和平均簇規(guī)模的指標(biāo)值。最后，對各組的指標(biāo)值進行秩和檢驗，得到漸進顯著性p值。秩和檢驗的原假設(shè)H0是建網(wǎng)結(jié)果的指標(biāo)值不存在顯著性差異，在顯著性水平為0.05 情況下，當(dāng)p<0.05 時拒絕H0，說明建網(wǎng)結(jié)果的指標(biāo)值存在顯著性差異，當(dāng)p>0.05 時接受H0，說明建網(wǎng)結(jié)果的指標(biāo)值不存在顯著性差異。實驗過程的示意圖如圖8所示，通過改變節(jié)點數(shù)量和總信道數(shù)量，能夠進行不同初始部署條件下的實驗。

圖8 實驗過程示意圖Fig.8 Schematic diagram of the experimental process

表2 給出了秩和檢驗的具體結(jié)果，在相同的初始部署下，不同信道停留時間的建網(wǎng)結(jié)果在兩個評估指標(biāo)上的p值均大于0.05，說明各建網(wǎng)結(jié)果的性能指標(biāo)值不存在顯著性差異。從統(tǒng)計的角度分析，搜索周期對整體網(wǎng)絡(luò)性能的影響是可控的。

表2 秩和檢驗結(jié)果Tab.2 The result of the rank sum test

4.3.3 MANE與其他算法的性能比較

本文考慮的是每個節(jié)點無法感知全網(wǎng)拓?fù)?、其他所有?jié)點的頻譜，以及無法獲得同步信息的實際場景，但是集中控制算法、信道跳變算法和分簇算法等現(xiàn)有的研究，不能完全滿足上述條件的限制。為了衡量本文所提MANE 算法的性能，對兩種現(xiàn)有算法進行了改進。第一種是最小ID 算法（Lowest ID），在該算法中ID 最低的節(jié)點優(yōu)先成為簇首。第二種是最大節(jié)點度算法（Max Degree），在該算法中節(jié)點度（鄰居節(jié)點數(shù)量）最大的節(jié)點優(yōu)先成為簇首?？紤]實際場景的限制，設(shè)置兩種算法的鄰居節(jié)點通過收發(fā)數(shù)據(jù)包交互信息。

圖9給出了平均信息交互次數(shù)對比情況。盡管三種算法在節(jié)點數(shù)量較少時的平均信息交互次數(shù)差距并不明顯，但隨著節(jié)點數(shù)量的增加，MANE的平均信息交互次數(shù)增加的速度比較緩慢，但其他兩種算法的平均信息交互次數(shù)有明顯的增加。在總信道數(shù)量M相同的情況下，不論節(jié)點數(shù)量如何變化，MANE一直保持著最低的平均信息交互次數(shù)。這主要是因為Lowest ID 和Max Degree 為了掌握全網(wǎng)信息需要節(jié)點之間進行全面的信息交互，節(jié)點數(shù)量增加，需要信息交互的次數(shù)相應(yīng)越多，導(dǎo)致通信沖突越嚴(yán)重，信息重傳次數(shù)越多。MANE 的建網(wǎng)策略中節(jié)點通過判斷是否存在鄰居簇首來確定身份，不需要掌握全網(wǎng)信息，所以信息交互次數(shù)少，受節(jié)點數(shù)量的影響更小。

圖9 平均信息交互次數(shù)對比Fig.9 Average number of information interactions

圖10給出了平均簇內(nèi)公共信道數(shù)量對比情況。Max Degree在建網(wǎng)過程中沒有考慮公共信道這個因素，Lowest ID的性能完全取決于具有最小ID的節(jié)點所在位置，兩種算法的平均簇內(nèi)公共信道數(shù)量并不具備優(yōu)越性。MANE 的平均簇內(nèi)公共信道數(shù)量最多，因為鄰居簇首排序時考慮了節(jié)點與鄰居簇首之間的相同可用信道數(shù)量。

圖10 平均簇內(nèi)公共信道數(shù)量對比Fig.10 Average number of common channels within the cluster

圖11給出了平均簇規(guī)模對比情況。圖11（a）顯示，當(dāng)部署范圍的邊長固定設(shè)置為1000 m 時，各算法平均簇規(guī)模隨著節(jié)點數(shù)量的增加而增加，這是由于節(jié)點數(shù)量增加會導(dǎo)致節(jié)點分布的密度增大。同時，總信道數(shù)量越多，平均簇規(guī)模越大，原因是總信道數(shù)量增多提高了節(jié)點之間存在相同可用信道的概率。圖11（b）顯示，當(dāng)節(jié)點數(shù)量固定設(shè)置為300個時，隨著部署范圍增大，各算法的平均簇規(guī)模都有所減小，這是因為部署范圍增大會使節(jié)點分布更加稀疏，進而導(dǎo)致簇首一跳范圍內(nèi)的節(jié)點數(shù)量減少。從整體來看，Lowest ID 不考慮拓?fù)浣Y(jié)構(gòu)和節(jié)點重要性，其獲得的平均簇規(guī)模最小。Max Degree 在全面掌握全網(wǎng)信息的基礎(chǔ)上選擇鄰居數(shù)量最多的節(jié)點作為簇首，所以平均簇規(guī)模最大。MANE 能夠利用有限的鄰域信息選擇簇規(guī)模大的簇首，無論節(jié)點數(shù)量和部署范圍如何變化，MANE 始終保持了較高的平均簇規(guī)模，性能優(yōu)于Lowest ID，且接近于Max Degree。

圖11 平均簇規(guī)模對比Fig.11 Average cluster size

5 結(jié)論

本文針對無線自組網(wǎng)節(jié)點在實際場景中建網(wǎng)困難的問題，提出了一種基于鄰域信息的多信道自適應(yīng)建網(wǎng)算法（MANE）。仿真結(jié)果表明，MANE 能夠以較少的建網(wǎng)開銷，構(gòu)建高效、穩(wěn)定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，適用于頻譜復(fù)雜變化的多信道無線自組網(wǎng)。下一步，將在此建網(wǎng)算法的基礎(chǔ)上研究資源分配問題，即如何在建網(wǎng)的同時進行有效的信道分配和功率分配，提高網(wǎng)絡(luò)的能效。