自組織網(wǎng)絡(luò)區(qū)域覆蓋協(xié)作控制算法

劉大鹍，陳桂芬，王義君

(1.長春理工大學(xué) 電子信息工程學(xué)院，吉林 長春 130022；2.中國北方車輛研究所 網(wǎng)絡(luò)與信息中心，北京 100072)

0 引言

自組織網(wǎng)絡(luò)的發(fā)展核心是在異構(gòu)協(xié)作基礎(chǔ)上為應(yīng)用提供最優(yōu)化服務(wù)，即面向不同應(yīng)用實現(xiàn)差異化的服務(wù)功能共享。功能需求個性化決定了應(yīng)用場景的多變性，應(yīng)用場景的多變性決定了網(wǎng)絡(luò)協(xié)議、硬件技術(shù)、軟件技術(shù)的不同，因此自組織網(wǎng)絡(luò)的研究內(nèi)容是面向應(yīng)用場景、面向功能需求的。從目前的研究情況可知，自組織網(wǎng)絡(luò)的關(guān)鍵技術(shù)包括射頻識別(RFID)技術(shù)、無線傳感器網(wǎng)絡(luò)(WSNs)技術(shù)、智能嵌入(EI)技術(shù)、納米技術(shù)、信息處理技術(shù)、自組織管理技術(shù)以及安全技術(shù)等[1-2]。但是對于絕大多數(shù)應(yīng)用場景，如果能夠通信的網(wǎng)絡(luò)節(jié)點不能有效覆蓋信息區(qū)域，則上述關(guān)鍵技術(shù)的相關(guān)研究內(nèi)容都將變得沒有意義。因此，自組織網(wǎng)絡(luò)區(qū)域覆蓋的有效性研究是未來軍事及民用領(lǐng)域能夠?qū)崿F(xiàn)廣泛應(yīng)用的基礎(chǔ)內(nèi)容，但是對于該方面內(nèi)容的具體研究并不多見。

對于區(qū)域覆蓋技術(shù)的研究，文獻(xiàn)[3]提出一種針對移動自組織網(wǎng)絡(luò)的能量有效區(qū)域覆蓋機制。通過一個網(wǎng)絡(luò)區(qū)域覆蓋的臨時備份節(jié)點，利用三角測量技術(shù)減少通信消耗來增強能源的使用效率。因此，能夠在均衡電池能源使用最小化的同時，實現(xiàn)最大程度地節(jié)點覆蓋連通，進(jìn)而保證網(wǎng)絡(luò)的魯棒性并延長網(wǎng)絡(luò)的生命周期。文獻(xiàn)[4]提出一種基于網(wǎng)格劃分的無線傳感器網(wǎng)絡(luò)多重覆蓋算法，包括冗余節(jié)點判斷和節(jié)點調(diào)度兩部分。該算法將節(jié)點覆蓋區(qū)域劃分為多個網(wǎng)格，通過判斷各個網(wǎng)格是否滿足覆蓋要求，進(jìn)而判斷節(jié)點是否冗余；在調(diào)度過程中能夠克服邊界效應(yīng)的影響，同時通過冗余節(jié)點能量比較，避免休眠沖突和覆蓋盲區(qū)的產(chǎn)生。文獻(xiàn)[5]依據(jù)區(qū)分與劃分相結(jié)合的可拒絕模式識別思路，提出高維空間海量訓(xùn)練樣本情況下基于結(jié)構(gòu)風(fēng)險最小化決策的自組織多區(qū)域覆蓋可拒絕近鄰分類算法。該算法利用數(shù)據(jù)分類實現(xiàn)覆蓋應(yīng)用，具有一定的實踐價值。文獻(xiàn)[6]面向物聯(lián)網(wǎng)應(yīng)用分析了覆蓋網(wǎng)絡(luò)節(jié)點布置問題，主要利用局部搜索算法解決時間復(fù)雜度，這種算法很難均衡地反映覆蓋控制的綜合指標(biāo)。文獻(xiàn)[7]提出了無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤應(yīng)用場景下的邊界節(jié)點選擇算法，該方法主要針對目標(biāo)跟蹤，具有一定的局限性。

本文在已有研究基礎(chǔ)上提出基于三角剖分的自組織網(wǎng)絡(luò)元胞遺傳區(qū)域覆蓋控制(CRCCTS)算法。該算法首先在三角剖分基礎(chǔ)上完成網(wǎng)絡(luò)節(jié)點的區(qū)域劃分；其次根據(jù)區(qū)域劃分后信號頻譜的不同確定集群范圍；最后基于元胞遺傳算法解決自組織網(wǎng)絡(luò)節(jié)點的功率控制。仿真結(jié)果表明，該算法在覆蓋效率、能量消耗以及平均端到端傳輸可靠性三方面取得了一定的改進(jìn)。

1 模型假設(shè)

對于自組織網(wǎng)絡(luò)而言，必須綜合考慮網(wǎng)絡(luò)環(huán)境的特點，按照某種原則合理部署網(wǎng)絡(luò)節(jié)點，保證網(wǎng)絡(luò)連通覆蓋前提下完成與終端用戶的通信，而通信傳輸?shù)木W(wǎng)絡(luò)節(jié)點應(yīng)盡可能少，從而保證網(wǎng)絡(luò)能耗盡可能低。自組織網(wǎng)絡(luò)特點如下：

1)覆蓋區(qū)域。自組織網(wǎng)絡(luò)的目的是協(xié)作通信，從網(wǎng)絡(luò)覆蓋范圍考慮，最終目標(biāo)是實現(xiàn)整個作戰(zhàn)區(qū)域的全方位覆蓋。具體到某個網(wǎng)絡(luò)，其覆蓋區(qū)域至少應(yīng)該是城域網(wǎng)或廣域網(wǎng)。

2)網(wǎng)絡(luò)帶寬。自組織網(wǎng)絡(luò)包含千變?nèi)f化的異構(gòu)網(wǎng)絡(luò)，異構(gòu)網(wǎng)絡(luò)帶寬存在較大差異，因此在不考慮信號頻譜情況下，對網(wǎng)絡(luò)進(jìn)行覆蓋算法研究將變得沒有意義。

3)功率控制。自組織網(wǎng)絡(luò)節(jié)點分屬于不同異構(gòu)網(wǎng)絡(luò)，對于發(fā)射功率的要求也不盡相同。節(jié)點選擇合適的發(fā)射功率可以影響其無線通信信號的覆蓋范圍，進(jìn)而可以選擇性地調(diào)整整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。相對于單一網(wǎng)絡(luò)節(jié)點，自組織網(wǎng)絡(luò)節(jié)點對于能量消耗的要求有所降低，因此自組織網(wǎng)絡(luò)功率控制的主要目的是保證網(wǎng)絡(luò)連通度和覆蓋度前提下增加網(wǎng)絡(luò)的容量，降低通信干擾[8]。

通過以上分析可知，自組織網(wǎng)絡(luò)覆蓋控制的特點主要體現(xiàn)在連通和通信兩方面。因此本文對自組織網(wǎng)絡(luò)區(qū)域覆蓋算法所應(yīng)用的數(shù)學(xué)模型作如下定義。

1.1 連通模型

由于覆蓋模型需要表現(xiàn)出節(jié)點發(fā)送信號在網(wǎng)絡(luò)中的傳播能力，需要用連通度來反映覆蓋能力。連通數(shù)學(xué)模型是基于某種特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及節(jié)點分布狀態(tài)，可以用(1)式表示覆蓋連通模型，

(1)

式中：S為網(wǎng)絡(luò)節(jié)點連通度；N為節(jié)點數(shù)；Si為第i個節(jié)點連通度。

1.2 通信模型

自組織網(wǎng)絡(luò)中異構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)不同，對于傳輸對象的信號帶寬也不盡相同，每個節(jié)點必須能夠感知信號的頻帶寬度，用以完成對網(wǎng)絡(luò)的選擇和信號的傳輸。在實際應(yīng)用中，當(dāng)被監(jiān)測區(qū)域中的監(jiān)測對象不在節(jié)點通信范圍內(nèi)時，節(jié)點不能感知到監(jiān)測對象。因此此時還需要考慮發(fā)射功率對于接收節(jié)點的影響。

根據(jù)電磁波傳播理論，當(dāng)其在自由空間中傳播時，如果發(fā)射端與接收端在視距范圍內(nèi)，則可用自由空間傳播模型預(yù)測接收信號的強度。設(shè)Ps為發(fā)射端的信源發(fā)射功率，r為收發(fā)端距離，則收發(fā)節(jié)點之間的信號功率關(guān)系為

(2)

式中：Pr為信宿接收功率；λ為載波波長；σ為信道衰落系數(shù)；As、Ar分別為信源天線和信宿天線的增益。

1.3 網(wǎng)絡(luò)模型

本網(wǎng)絡(luò)模型基于元胞思想[9]。

1.3.1 元胞空間及狀態(tài)集定義

定義1C={c1，c2，…，cN}為網(wǎng)絡(luò)節(jié)點集合，C中任意源節(jié)點與目的節(jié)點間的所有通信路徑構(gòu)成鏈路元胞空間L，L={Lk=(c1，…，cz，…，cj，…，cN)|cz，cj∈C，cz≠cj，z、j=1，2，…，N}。其中：Lk為兩節(jié)點第k條鏈路的元胞空間，k∈Z，Z表示整數(shù)集。

定義2S={So，Sw，Si}為元胞節(jié)點狀態(tài)集，So表示工作狀態(tài)，Sw表示等待狀態(tài)，Si表示空閑狀態(tài)。元胞節(jié)點共有中心元胞節(jié)點(CC)、鄰居元胞節(jié)點(NC)2種類型，反映3種元胞狀態(tài)。其中：CC為正在傳輸信息的工作節(jié)點，該節(jié)點始終處于工作狀態(tài)，此時CC需要決定下一跳節(jié)點的選擇；NC為CC在通信距離一跳范圍內(nèi)的鄰居節(jié)點，NC的狀態(tài)分為工作狀態(tài)和空閑狀態(tài)兩種，CC可以根據(jù)通信鏈路關(guān)系選擇鄰居節(jié)點，實現(xiàn)下一跳信息傳輸。設(shè)Sl為元胞空間Lk在t時刻的鏈路狀態(tài)集合，該集合由Lk、S和t決定，即集合U(Lk，S，t)∈Sl.

1.3.2 元胞節(jié)點間鄰居關(guān)系確定

采用Von Neumann鄰域確定元胞節(jié)點間的鄰居關(guān)系，該關(guān)系定義在二維方格上，由中央單元及其4個相鄰鄰居及擴(kuò)展鄰居組成，如圖1所示。圖1中，Z為處于中央單元的中心元胞，M為4個相鄰鄰居元胞，E為擴(kuò)展鄰居元胞，x、y表示元胞坐標(biāo)。該鄰域關(guān)系由無重復(fù)的U(Lk，S，t)集合決定。同時，在此鄰域關(guān)系基礎(chǔ)上，元胞空間Lk的通信鏈路判定由下面公式?jīng)Q定：

X={Lk|d(Lk1-Lk2)≤v，Lk1，Lk2∈Lk}，

式中：X為鏈路判定集合；d(Lk1-Lk2)為相鄰節(jié)點間不同通信路徑的差別，Lk1、Lk2表示兩節(jié)點間第k1和第k2條鏈路；v表示相差度，由鏈路能量、誤包率和時間延遲決定。

圖1 Von Neumann鄰域關(guān)系Fig.1 Von Neumann neighborhood

1.3.3 網(wǎng)絡(luò)模型進(jìn)化及更新準(zhǔn)則

步驟1網(wǎng)絡(luò)初始化：C={c1，c2，…，cN}，S={So，Sw，Si}。

步驟2元胞節(jié)點狀態(tài)S轉(zhuǎn)換。

狀態(tài)1：假設(shè)CC周圍存在處于空閑狀態(tài)的相鄰NC，則CC通過一個空閑狀態(tài)相鄰NC轉(zhuǎn)發(fā)數(shù)據(jù)分組到下一跳元胞；選擇依據(jù)為節(jié)點能量，即選擇鄰居節(jié)點中剩余能量最多的作為轉(zhuǎn)發(fā)節(jié)點；

狀態(tài)2：如果CC周圍沒有相鄰NC但存在擴(kuò)展NC，則CC通過一個擴(kuò)展NC轉(zhuǎn)發(fā)數(shù)據(jù)分組到下一跳節(jié)點，選擇依據(jù)為節(jié)點能量及鏈路狀態(tài)；

狀態(tài)3：如果CC有效范圍內(nèi)不存在有效元胞，此時該CC的所有鄰居元胞均處在工作狀態(tài)，則CC將數(shù)據(jù)分組存儲到緩存中；當(dāng)該CC接收到某一元胞發(fā)送的釋放消息后，選擇該元胞完成數(shù)據(jù)分組的下一跳節(jié)點。

步驟3鏈路元胞空間狀態(tài)S轉(zhuǎn)換。構(gòu)建網(wǎng)絡(luò)傳輸路徑，通過下式比較鏈路的節(jié)點通信路徑差別，選擇相對最優(yōu)的數(shù)據(jù)鏈路完成鏈路路徑選擇。

X={Lk|d(Lk1-Lk2)≤v，Lk1，Lk2∈Lk}.

步驟4更新鏈路，存儲多徑信息，完成U(Lk，S，t)∈Sl的鏈路更新。

2 覆蓋協(xié)作控制算法

2.1 基于三角剖分的區(qū)域劃分

為了提高網(wǎng)絡(luò)節(jié)點的覆蓋效率，必須對節(jié)點進(jìn)行合理部署，即對自組織網(wǎng)絡(luò)覆蓋范圍進(jìn)行科學(xué)的區(qū)域劃分，為基于信號頻譜的集群確定選擇出合適的掃頻節(jié)點。因此協(xié)作控制算法的第一步是將覆蓋區(qū)域進(jìn)行物理劃分，從而不僅可以降低拓?fù)淇刂频某杀?，還能通過最少的鏈路節(jié)點獲取最大的路由效率，是下一步算法實現(xiàn)的基礎(chǔ)。在確定覆蓋區(qū)域所需掃頻節(jié)點時，由于覆蓋區(qū)域可能較為復(fù)雜，可以將其分為若干子塊。每一塊由掃頻節(jié)點覆蓋。為了完成每一塊的分解，需要將區(qū)域內(nèi)若干頂點通過對角線連接起來，即一段開線段。這種開線段必須完全落在分塊區(qū)域內(nèi)。通過一組極大的互不相交的對角線，即可將覆蓋區(qū)域分解為多個三角形的集合，實現(xiàn)覆蓋區(qū)域的三角剖分。本文以節(jié)點覆蓋區(qū)域外部多邊形頂點結(jié)構(gòu)為基準(zhǔn)，通過三角剖分形式將網(wǎng)絡(luò)覆蓋區(qū)域劃分為若干子域。網(wǎng)絡(luò)覆蓋區(qū)域的外部多邊形結(jié)構(gòu)即區(qū)域W如圖2所示。

圖2 節(jié)點覆蓋區(qū)域外部多邊形結(jié)構(gòu)Fig.2 Outside polygon structure of nodes coverage

2.1.1 構(gòu)建單調(diào)多邊形

將區(qū)域W劃分為w個單調(diào)多邊形，通過引入對角線來消除多邊形不規(guī)則情況下引起的拐點，如圖3所示。圖3中，點p為1個拐點，與其連接的2條多邊形的邊分別位于點p的左右兩側(cè)，此時需構(gòu)造1條以p為起點、向上連接到點b的對角線，對角線pb將原多邊形分為兩部分，此時p不再屬于拐點，而屬于劃分后2個多邊形的1個公共頂點。基于此，即可完成區(qū)域C的單調(diào)劃分。由文獻(xiàn)[10]可知，在空間復(fù)雜度O(w)的存儲條件下，可在O(wlgw)的時間復(fù)雜度內(nèi)將包含多個頂點的任何簡單多邊形分解為多個單調(diào)的子塊多邊形。

圖3 通過引入對角線消除拐點Fig.3 Introducing diagonals to eliminate inflection point

2.1.2 單調(diào)多邊形的三角剖分

完成對自組織網(wǎng)絡(luò)外部多邊形結(jié)構(gòu)的單調(diào)劃分后，按隨機次序依次引入網(wǎng)絡(luò)中的各節(jié)點，程序的執(zhí)行需要維護(hù)并更新1個與當(dāng)前點集對應(yīng)的三角剖分。單調(diào)多邊形三角剖分構(gòu)造算法流程圖如圖4所示。

圖4 三角剖分流程圖Fig.4 Triangulation flow chart

綜上所述，通過對覆蓋區(qū)域的外部多邊形結(jié)構(gòu)進(jìn)行單調(diào)劃分和三角剖分，即可得到自組織網(wǎng)絡(luò)節(jié)點外部多邊形為10個頂點時在平面區(qū)域內(nèi)劃分的三角剖分拓?fù)浣Y(jié)構(gòu)圖(見圖5)。

圖5 經(jīng)過三角分解后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.5 Network topology after triangular decomposition

2.2 基于信號頻譜的集群確定

2.2.1 基于染色方案的掃頻節(jié)點確定

網(wǎng)絡(luò)拓?fù)湫纬珊?，需要為覆蓋協(xié)作控制奠定基礎(chǔ)。當(dāng)三角剖分后的拓?fù)浣Y(jié)構(gòu)形成后，將三角形頂點處的節(jié)點組成1個子集。為了最大限度地在該子集中找到盡可能少的節(jié)點、完成區(qū)域覆蓋任務(wù)，使用紅、黃、綠3種顏色給子集中的所有節(jié)點進(jìn)行染色。染色方案需要滿足由任何邊連接的2個節(jié)點所染的顏色不能相同。基于此，三角剖分后的多邊形經(jīng)過染色后，其中每個三角形都有且僅有1個紅色、黃色和藍(lán)色頂點。通過上述方法，當(dāng)網(wǎng)絡(luò)完成三角劃分后，如果覆蓋區(qū)域外部多邊形結(jié)構(gòu)存在h個頂點，則可以選擇h個網(wǎng)絡(luò)中三角形頂點處的節(jié)點完成整個網(wǎng)絡(luò)區(qū)域的監(jiān)測，如圖6中圓形頂點所示。在拓?fù)浣Y(jié)構(gòu)確定的基礎(chǔ)上，通過染色可以獲取協(xié)作控制的中心節(jié)點，保證集群確定的實現(xiàn)。

圖6 骨干傳輸節(jié)點選擇示意圖Fig.6 Schematic diagram of backbone node selection

2.2.2 基于信號頻譜的集群確定

首先定義興趣驅(qū)動的概念。所謂興趣驅(qū)動，是將網(wǎng)絡(luò)中同時具有如下特征的節(jié)點稱為同類興趣驅(qū)動節(jié)點：1)描述共同的需求網(wǎng)絡(luò)行為；2)具有共同的性能指標(biāo)參數(shù)；3)表達(dá)共同的附加功能請求。關(guān)于同類興趣驅(qū)動節(jié)點，就需求網(wǎng)絡(luò)行為而言，可以指能量消耗需求或時間同步精度需求；就性能指標(biāo)參數(shù)而言，廣義講可以指傳輸信號的類型，如視頻、圖像或語音等，或者是允許多種類型信號同時傳輸對指標(biāo)參數(shù)的要求；就附加功能請求而言，可以指是否需要與互聯(lián)網(wǎng)或移動通信網(wǎng)絡(luò)相連等。

當(dāng)確定掃頻節(jié)點后，掃頻節(jié)點通過發(fā)射某種頻率的信號發(fā)現(xiàn)具有共同興趣驅(qū)動的自組織網(wǎng)絡(luò)節(jié)點，將具有共同興趣驅(qū)動的節(jié)點劃分到統(tǒng)一的通信范圍中，本文將滿足該通信范圍所代表的區(qū)域稱為1個集群?；陬l譜的共同興趣驅(qū)動節(jié)點發(fā)現(xiàn)過程如圖7所示。當(dāng)掃頻節(jié)點確定后，所有節(jié)點仍處于獨立的分布狀態(tài)，并沒有形成以興趣驅(qū)動為目標(biāo)的集群，此時不同類型掃頻節(jié)點開始以不同頻率發(fā)射廣播信號，尋找共同興趣驅(qū)動的同類型節(jié)點，如圖7(a)所示，廣播信號的幀結(jié)構(gòu)包括集群ID、時間戳、安全認(rèn)證碼和興趣驅(qū)動優(yōu)先級，其中時間戳位于集群ID之后。當(dāng)掃頻節(jié)點周圍的普通節(jié)點接收到與其同頻段的廣播信號時確定興趣類型，并向該掃頻節(jié)點發(fā)送應(yīng)答信號，等待掃頻節(jié)點確認(rèn)后加入屬于該頻段且同興趣的集群中，如圖7(b)所示。當(dāng)共同興趣驅(qū)動節(jié)點完成集群組合后，如圖7(b)所示，在規(guī)定時間內(nèi)自組織網(wǎng)絡(luò)節(jié)點3并沒有發(fā)現(xiàn)合適的集群，此時該節(jié)點主動成為掃頻節(jié)點并開始以頻率f廣播信號，尋找共同興趣集群。當(dāng)有同類型節(jié)點收到此信號時，與節(jié)點3建立聯(lián)系并告知該集群中的掃頻節(jié)點，使節(jié)點3加入該集群中，如圖7(c)所示。如果節(jié)點3在有效時間閾值中不能找到共同興趣集群，則其以掃頻節(jié)點身份存在于網(wǎng)絡(luò)中。

圖7 基于頻譜的共同興趣驅(qū)動節(jié)點發(fā)現(xiàn)過程Fig.7 Discovery process of common interests drive nodes based on spectrum

2.3 基于元胞遺傳的功率控制

對于自組織網(wǎng)絡(luò)，覆蓋協(xié)作控制算法的關(guān)鍵一步是功率控制，以降低網(wǎng)絡(luò)節(jié)點的相互干擾、提高自組織網(wǎng)絡(luò)的覆蓋效率。功率控制的基礎(chǔ)是區(qū)域劃分和集群確定，這三方面相互協(xié)作，可以實現(xiàn)區(qū)域的完全覆蓋。覆蓋控制方法需要遵循功率控制與睡眠調(diào)度相統(tǒng)一原則[11]。節(jié)點在沒有事件驅(qū)動時設(shè)置通信模塊為睡眠狀態(tài)，在有事件驅(qū)動時結(jié)束睡眠并喚醒鄰居節(jié)點，進(jìn)而形成數(shù)據(jù)轉(zhuǎn)發(fā)的拓?fù)浣Y(jié)構(gòu)。該原則使無線通信模塊大部分時間處于休眠狀態(tài)，傳感器模塊則處于工作狀態(tài)。由于無線通信模塊的能耗遠(yuǎn)大于傳感器模塊，節(jié)省了能量開銷。該原則重點在于解決節(jié)點在睡眠狀態(tài)和激活狀態(tài)之間的切換，而且不能獨立成為一種拓?fù)浣Y(jié)構(gòu)控制機制，需要與其他拓?fù)淇刂扑惴ńY(jié)合使用才更有效。因此，要建立能量高效的覆蓋控制結(jié)構(gòu)，必須在考慮通信能耗和空閑能耗的基礎(chǔ)上建立功率控制機制。本文基于元胞遺傳思想解決功率控制問題，算法運行流程圖如圖8所示。圖8中，Ep為1條無線通信鏈路中端到端的總能量消耗，Eth為端到端通信所需要的最低能量消耗閾值，PERl為1條無線通信鏈路中端到端的總誤包率，PERth為端到端通信所要求的最低誤包率閾值，Tp為1條無線通信鏈路中端到端的傳輸總延時，Tth為端到端通信所要求的最短時間閾值，β為時間延遲的目標(biāo)概率，P表示概率。

圖8 功率控制算法流程圖Fig.8 Flow chart of power control algorithm

控制方法具體步驟如下：

步驟1進(jìn)行三角剖分，整個自組織網(wǎng)絡(luò)完成區(qū)域劃分及節(jié)點覆蓋布置，形成初始節(jié)點分布集群。

步驟2建立基于元胞的節(jié)點集群網(wǎng)絡(luò)模型。

步驟3節(jié)點集群網(wǎng)絡(luò)模型通過能量測試完成性能指標(biāo)適應(yīng)度評估。設(shè)Nb為節(jié)點傳輸數(shù)據(jù)包的比特數(shù)，

Nb=Nh+Nc+Nd，

(3)

式中：Nh為報頭的比特數(shù)；Nc為經(jīng)過編碼后的編碼比特數(shù)；Nd為數(shù)據(jù)比特數(shù)。設(shè)1條無線通信鏈路上第n個節(jié)點傳輸Nb信息的能量消耗為E(n)，則

(4)

(5)

如果Ep≤Eth，則表示無線通信鏈路穩(wěn)定，可以按照既定路由完成數(shù)據(jù)轉(zhuǎn)發(fā)；如果Ep≥Eth，則轉(zhuǎn)步驟4，開始集群的進(jìn)化。

步驟4節(jié)點集群進(jìn)化的一方面是誤包率判斷，(6)式給出了誤包率進(jìn)化的判斷方法，

PERl=1-(1-PERe)(1-PERi)≤PERth，

(6)

式中：PERe為物理層經(jīng)過編碼差錯控制的鏈路誤包率；PERi為網(wǎng)絡(luò)誤包率。如果(6)式成立，則滿足誤包率進(jìn)化要求。節(jié)點種群進(jìn)化的另一方面是時間延遲判斷，(7)式給出了時間延遲判斷方法，

(7)

式中：Tq為鏈路中某節(jié)點信息申請及等待發(fā)送時間；Tc為信息轉(zhuǎn)發(fā)執(zhí)行時間；Ti為網(wǎng)絡(luò)傳輸時間。如果Tp≤Tth的概率P(Tp≤Tth)≥β，則滿足時間延遲進(jìn)化要求；如果上述兩條原則均滿足，則替換節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)種群，否則轉(zhuǎn)步驟5.

步驟5設(shè)we、wp、wt分別為鏈路能量、誤包率和時間延遲的權(quán)重，則有

we+wp+wt=1.

(8)

當(dāng)步驟1～步驟3不能滿足時，功率控制采用(9)式完成。節(jié)點能量、誤包率和時延在與相應(yīng)閾值作歸一化比較后，與對應(yīng)的權(quán)值完成加權(quán)運算，將三類參數(shù)求加權(quán)和，通過均衡3組參數(shù)權(quán)值最小值，選擇相應(yīng)的節(jié)點增大功率，而其他節(jié)點則處于睡眠狀態(tài)，不加入拓?fù)浣Y(jié)構(gòu)中。

(9)

4 仿真實驗

仿真實驗中將自組織網(wǎng)絡(luò)節(jié)點按發(fā)送信號頻譜的不同分為3類，每類節(jié)點各取300個，通過在800 m×800 m區(qū)域內(nèi)布置900個自組織網(wǎng)絡(luò)節(jié)點來測試覆蓋控制算法，其中具體仿真設(shè)置參數(shù)如表1所示。為了驗證本文所提CRCCTS算法的有效性，將其與均衡速率區(qū)域覆蓋算法(BRACA)[12]、最小節(jié)點強屏障的分區(qū)構(gòu)造(PMNSB)算法[13]、覆蓋配置協(xié)議(CCP)算法[14]和多跳Ad Hoc無線網(wǎng)絡(luò)的節(jié)能技術(shù)(SPAN)算法[15]進(jìn)行比較。其中，BRACA主要以實現(xiàn)網(wǎng)絡(luò)生命周期的最大化為目的開展網(wǎng)絡(luò)能量均勻及均衡覆蓋方面的研究；PMNSB算法構(gòu)建了強柵欄覆蓋模型，提出分區(qū)強K-柵欄覆蓋構(gòu)建方法，旨在用最少的節(jié)點形成強柵欄；CCP算法將無關(guān)節(jié)點安排睡眠間隔，其余節(jié)點保持活動狀態(tài)以提供連續(xù)服務(wù)；SPAN算法則側(cè)重在保證網(wǎng)絡(luò)連通度情況下，最大限度地降低網(wǎng)絡(luò)節(jié)點的能量損耗。將5種算法同時在表1所示的仿真環(huán)境下進(jìn)行實驗，并從覆蓋效率、能量消耗和平均端到端可靠性3個方面進(jìn)行數(shù)據(jù)處理和分析。

4.1 覆蓋效率

覆蓋效率是綜合衡量網(wǎng)絡(luò)覆蓋控制算法的評價指標(biāo)，它既可以反映覆蓋程度，也可以反映節(jié)點的冗余程度，同時還可以體現(xiàn)網(wǎng)絡(luò)能量消耗狀況。覆蓋效率可定義為覆蓋區(qū)域中所有節(jié)點的覆蓋范圍并集與所有節(jié)點覆蓋范圍和集的比值，即

表1 仿真參數(shù)Tab.1 Simulation parameters

(10)

式中：Ci為第i個節(jié)點的覆蓋范圍。

圖9 覆蓋效率比較Fig.9 Comparison of coverage efficiencies

根據(jù)(10)式，得到CRCCTS算法、BRACA、PMNSB算法、SPAN算法和CCP算法在覆蓋效率方面的性能指標(biāo)如圖9所示。由于CRCCTS算法通過三角剖分劃分覆蓋區(qū)域并確定集群中心節(jié)點的位置，可實現(xiàn)最少節(jié)點覆蓋最大區(qū)域，同時采用信號頻譜確定集群集合，進(jìn)而調(diào)整集群節(jié)點的功率控制范圍。從圖9中可見，隨著節(jié)點數(shù)量的不斷增加，CRCCTS算法覆蓋效率比BRACA平均提高約3%，比PMNSB算法平均提高約5%，比SPAN算法平均提高約12%，比CCP算法平均提高約22%.

4.2 能量消耗

對于能量消耗，本文主要考慮自組織網(wǎng)絡(luò)底層異構(gòu)網(wǎng)絡(luò)中能量受限的無線網(wǎng)絡(luò)節(jié)點，如無線個域網(wǎng)中的傳感器節(jié)點或移動無線網(wǎng)絡(luò)終端等。因此，將(4)式進(jìn)一步細(xì)化，可得每個節(jié)點完成一次信息傳輸所消耗的能量，如(11)式所示：

E=q(Ei+Es+ξrψ)+E0，

(11)

式中：q為節(jié)點收發(fā)數(shù)據(jù)次數(shù)；Ei為1次收發(fā)過程節(jié)點電路本身能量消耗；Es為網(wǎng)絡(luò)協(xié)議能量消耗；ξ為電磁場擴(kuò)散能量損失系數(shù)；ψ為擴(kuò)散損失因子；E0為節(jié)點在空閑狀態(tài)下的能量消耗。因為CRCCTS算法一方面采用最少的節(jié)點數(shù)量保證網(wǎng)絡(luò)覆蓋效率，另一方面基于元胞遺傳完成節(jié)點功率控制，所以1次端到端信息傳輸參與通信節(jié)點數(shù)量較少，而且每個節(jié)點完成此次通信任務(wù)的平均信息交換次數(shù)較少，其能量消耗相對于其他4種算法具有一定的優(yōu)勢。5種算法的能量消耗性能指標(biāo)比較如圖10所示。從圖10中可見，網(wǎng)絡(luò)中節(jié)點數(shù)量較少時，CRCCTS算法能量消耗最低，CCP算法能量消耗最高，但5種算法相差不大；隨著節(jié)點數(shù)量增多，5種算法表現(xiàn)出來的能量消耗差距明顯，當(dāng)網(wǎng)絡(luò)中有900個節(jié)點時，CRCCTS算法約消耗能量18 J，BRACA約消耗能量20 J、PMNSB算法約消耗能量26 J，SPAN算法約消耗能量46 J，而CCP算法約消耗能量70 J.

圖10 能量消耗比較Fig.10 Comparison of energy consumptions

4.3 平均端到端可靠性

網(wǎng)絡(luò)可靠性與網(wǎng)絡(luò)質(zhì)量和性能具有密切關(guān)系，本文針對覆蓋控制算法，將平均可靠性指標(biāo)定義如下：假設(shè)網(wǎng)絡(luò)中有n個節(jié)點，平均端到端鏈路為La，則平均端到端可靠性指標(biāo)可定義為

(12)

式中：pi為2節(jié)點間第i條鏈路成功通信概率；δi為2節(jié)點間第i條鏈路容量權(quán)重系數(shù)，本文所采用的鏈路容量指標(biāo)為數(shù)據(jù)傳輸速率和信道數(shù)量。同時，將5種算法與文獻(xiàn)[16]中提出的路由算法相結(jié)合，對端到端可靠性進(jìn)行仿真，仿真結(jié)果如圖11所示。由于CRCCTS算法利用信號頻率建立集群，不同集群可作為信息傳輸?shù)妮d體，同時利用元胞遺傳控制集群節(jié)點功率，實現(xiàn)端到端可靠覆蓋傳輸。由圖11可知，網(wǎng)絡(luò)中節(jié)點數(shù)量不同的情況下，CRCCTS算法的平均端到端可靠度在87%～97%之間，BRACA和PMNSB算法的平均端到端可靠度約為70%～95%，SPAN算法和CCP算法的平均端到端可靠度約為60%～85%. 由此可見，CRCCTS算法能夠保證信息的端到端可靠傳輸。

圖11 平均端到端可靠性比較Fig.11 Comparison of average end-to-end reliabilities

5 結(jié)論

為了解決自組織網(wǎng)絡(luò)區(qū)域覆蓋有效性的問題，本文提出基于三角剖分的自組織網(wǎng)絡(luò)元胞遺傳區(qū)域覆蓋控制思想。通過區(qū)域劃分、集群確定以及功率控制實現(xiàn)自組織網(wǎng)絡(luò)應(yīng)用環(huán)境下的區(qū)域覆蓋控制。該算法可以較好地滿足自組織網(wǎng)絡(luò)的特點以及覆蓋效率、能量消耗和傳輸可靠性等方面的約束。仿真實驗結(jié)果證明了CRCCTS區(qū)域覆蓋控制算法的有效性。由于本文在超密集節(jié)點和節(jié)點具有移動特性的情況下，相關(guān)性能指標(biāo)優(yōu)勢并不明顯。后續(xù)研究將進(jìn)一步解決上述關(guān)鍵問題，同時將拓?fù)淇刂萍夹g(shù)和路由技術(shù)融入到本文提出的區(qū)域覆蓋控制算法中，綜合考慮提高自組織網(wǎng)絡(luò)異構(gòu)數(shù)據(jù)傳輸速率及可靠性等問題的有效方法。