基于能耗均衡的無(wú)人機(jī)集群組網(wǎng)算法*

陳秉試

（廈門海洋職業(yè)技術(shù)學(xué)院，福建 廈門 361012）

0 引言

近年來(lái)，面向消費(fèi)級(jí)和工業(yè)級(jí)的無(wú)人機(jī)(Unmanned Aerial Vehicle,UAV)的應(yīng)用發(fā)展迅速，在地圖重建、監(jiān)控巡查、電力巡檢、災(zāi)后救援以及物流運(yùn)輸?shù)阮I(lǐng)域都取得了顯著的成效。無(wú)人機(jī)集群可以通過(guò)感知交互、信息傳遞和協(xié)同工作應(yīng)付更加復(fù)雜的任務(wù)和環(huán)境，提高執(zhí)行效率以及任務(wù)完成度，從而受到廣泛關(guān)注[1-3]。大規(guī)模的無(wú)人機(jī)集群已成為趨勢(shì)，針對(duì)無(wú)人機(jī)網(wǎng)絡(luò)的高度動(dòng)態(tài)性和能耗約束性等特點(diǎn)，分層組網(wǎng)架構(gòu)具備更強(qiáng)的可擴(kuò)展性，更有利于無(wú)人機(jī)網(wǎng)絡(luò)資源分配[4]。

在進(jìn)行分層組網(wǎng)時(shí)，分簇算法起到重要作用，其中簇成員和簇頭時(shí)常分別隸屬于不同組網(wǎng)層面，通過(guò)簇內(nèi)和簇間通信實(shí)現(xiàn)層間數(shù)據(jù)傳輸。文獻(xiàn)[5]提出了基于路徑規(guī)劃的簇首加權(quán)選舉和簇成員加權(quán)調(diào)整算法，動(dòng)態(tài)調(diào)整分簇過(guò)程。文獻(xiàn)[6]采用魚(yú)群算法實(shí)現(xiàn)網(wǎng)絡(luò)自組重構(gòu)，并考慮節(jié)點(diǎn)剩余能量和簇間通信開(kāi)銷，以完成簇頭選舉。文獻(xiàn)[7]提出了針對(duì)速度相似度、鏈路保持率、節(jié)點(diǎn)度差和節(jié)點(diǎn)剩余能量的多參數(shù)加權(quán)分簇算法。文獻(xiàn)[8]綜合考慮節(jié)點(diǎn)能耗以及距離等因素進(jìn)行分簇以及簇頭選擇。本文則采用機(jī)器學(xué)習(xí)的思想，利用Kmeans++算法，更加強(qiáng)調(diào)聚類的相似性和智能性。

無(wú)人機(jī)集群拓?fù)鋭?dòng)態(tài)變化，因此集群控制技術(shù)至關(guān)重要。文獻(xiàn)[9]通過(guò)覆蓋分布地圖(CDM)描述任務(wù)環(huán)境，以預(yù)測(cè)周期內(nèi)最大覆蓋率增量設(shè)為獎(jiǎng)勵(lì)函數(shù)，采用差分進(jìn)化算法進(jìn)行求解。文獻(xiàn)[10]采用虛擬力的理念控制無(wú)人機(jī)飛行到合適的位置。文獻(xiàn)[11]提出了基于Agent 與元胞自動(dòng)機(jī)的集群混合式控制模型。文獻(xiàn)[12]介紹了無(wú)人機(jī)集群路徑規(guī)劃的模型并歸納梳理了采用智能優(yōu)化算法的集群路徑規(guī)劃的相關(guān)研究。其中，啟發(fā)式算法在恰當(dāng)?shù)膮?shù)設(shè)置下，對(duì)于復(fù)雜的模型特別是NP 問(wèn)題可高效地搜索最優(yōu)解。因此，本文首先構(gòu)建能耗模型，再通過(guò)分簇實(shí)現(xiàn)初始組網(wǎng)，再采用遺傳算法進(jìn)行無(wú)人機(jī)集群中能耗均衡和通信負(fù)載分配。

1 系統(tǒng)場(chǎng)景及架構(gòu)

本文所研究的無(wú)人機(jī)自組網(wǎng)拓?fù)浣Y(jié)構(gòu)如圖1 所示，無(wú)人機(jī)作為移動(dòng)通信的緩存節(jié)點(diǎn)，成為基站的補(bǔ)充，以適應(yīng)在動(dòng)態(tài)用戶流下完成邊緣緩存的數(shù)據(jù)分發(fā)和負(fù)載分流。無(wú)人機(jī)集群形成多個(gè)簇，每個(gè)簇包含若干簇成員和一個(gè)簇頭，簇頭和簇成員之間均可雙向簇內(nèi)通信。同時(shí)，簇頭之間可進(jìn)行簇間雙向通信，并且簇頭形成骨干網(wǎng)絡(luò)，通過(guò)多跳與控制中心連接。控制中心收集無(wú)人機(jī)運(yùn)動(dòng)信息和通信信息，對(duì)無(wú)人機(jī)集群簇頭完成集中式控制。簇內(nèi)管理則由簇頭負(fù)責(zé)，從而實(shí)現(xiàn)了集中—分布混合通信管理模式。

圖1 無(wú)人機(jī)集群組網(wǎng)場(chǎng)景及架構(gòu)

設(shè)簇頭無(wú)人機(jī)通信半徑為RCH，簇成員無(wú)人機(jī)通信半徑為RCM，所覆蓋的地面區(qū)域半徑為Rc，且RCH＞RCM＞Rc。每個(gè)無(wú)人機(jī)節(jié)點(diǎn)周期性發(fā)送HELLO 包，其中包含節(jié)點(diǎn)的狀態(tài)信息，即ID、三維位置坐標(biāo)、剩余電量、所在周期通信能耗。簇成員將狀態(tài)信息匯總到簇頭，簇頭將本簇的狀態(tài)信息匯總到控制中心，控制中心根據(jù)用戶需求分布以及無(wú)人機(jī)集群中各節(jié)點(diǎn)的能耗情況計(jì)算下一周期最優(yōu)的節(jié)點(diǎn)位置分布以及各節(jié)點(diǎn)的通信負(fù)載。

2 節(jié)點(diǎn)能耗模型

每架無(wú)人機(jī)的能耗由兩部分組成，即飛行能耗和通信能耗。系統(tǒng)時(shí)間維度切分為若干時(shí)間周期，每個(gè)周期持續(xù)時(shí)間為T。無(wú)人機(jī)運(yùn)動(dòng)模式主要是在駐留位置上空懸停或者駐留位置改變時(shí)的位移。設(shè)無(wú)人機(jī)懸停功率均為Po，位移時(shí)功率均為Pm。同時(shí)，假設(shè)無(wú)人機(jī)均以速度v進(jìn)行高速移動(dòng)，從懸停加速到該速率或者反向減速的時(shí)間極短，可忽略不計(jì)，并且在覆蓋區(qū)內(nèi)移動(dòng)所消耗的時(shí)間遠(yuǎn)小于周期持續(xù)時(shí)間。設(shè)第t個(gè)周期無(wú)人機(jī)u位移距離為sut，則其位移能耗為

無(wú)人機(jī)u移動(dòng)到目的位置后保持懸停，則該周期懸停能耗為：

無(wú)人機(jī)通信能耗與傳輸?shù)臄?shù)據(jù)量有關(guān)，設(shè)無(wú)人機(jī)傳輸單位數(shù)據(jù)量的功率為Pa，無(wú)人機(jī)u在第t個(gè)周期被分配的需要傳輸?shù)臄?shù)據(jù)量為則通信能耗為：

因此，無(wú)人機(jī)u在第t周期的總能耗為

設(shè)無(wú)人機(jī)集群中，無(wú)人機(jī)節(jié)點(diǎn)總數(shù)為U，周期t預(yù)計(jì)需要傳輸?shù)臄?shù)據(jù)總量為Bt，無(wú)人機(jī)最大通信負(fù)載為bmax，允許的無(wú)人機(jī)移動(dòng)時(shí)長(zhǎng)為τ，則優(yōu)化目標(biāo)可以歸結(jié)為通過(guò)合理移動(dòng)無(wú)人機(jī)集群中各節(jié)點(diǎn)的位置以及合理分配各節(jié)點(diǎn)通信負(fù)載，從而最小化節(jié)點(diǎn)的最大能耗，即：

3 算法原理及流程

3.1 總體思想及流程

整個(gè)服務(wù)區(qū)內(nèi)某個(gè)周期的通信流量已知，但是分布不均，因此需要實(shí)現(xiàn)在節(jié)點(diǎn)負(fù)載約束下，服務(wù)區(qū)域全覆蓋且分擔(dān)所有通信流量需求。首先完成初始化過(guò)程，即給定U個(gè)無(wú)人機(jī)節(jié)點(diǎn)的初始服務(wù)位置設(shè)定，既要完成服務(wù)區(qū)全覆蓋，也要保證一定規(guī)模的節(jié)點(diǎn)間的連通性。其次，每個(gè)周期內(nèi)完成無(wú)人機(jī)節(jié)點(diǎn)基于Kmeans++的分簇，確定簇成員所服務(wù)的覆蓋區(qū)以及簇頭節(jié)點(diǎn)管轄的簇成員，以構(gòu)建分層組網(wǎng)架構(gòu)。再次，當(dāng)前周期的節(jié)點(diǎn)狀態(tài)信息經(jīng)簇內(nèi)匯總以及簇間多跳傳輸發(fā)送至控制中心，采用遺傳算法，以節(jié)點(diǎn)最大能耗最小化為目標(biāo)，計(jì)算下一周期各節(jié)點(diǎn)的最優(yōu)位置及通信負(fù)載。

3.2 初始化過(guò)程

將服務(wù)區(qū)域劃分為zm*zn個(gè)服務(wù)網(wǎng)格，無(wú)人機(jī)節(jié)點(diǎn)的候選服務(wù)位置即為其中部分網(wǎng)格的中心點(diǎn)，且其地面服務(wù)半徑內(nèi)可覆蓋多個(gè)服務(wù)網(wǎng)格。設(shè)K為分簇的簇?cái)?shù)，則將整個(gè)服務(wù)區(qū)均勻分為U-K個(gè)覆蓋區(qū)，每個(gè)區(qū)域由一個(gè)無(wú)人機(jī)節(jié)點(diǎn)服務(wù)，這些節(jié)點(diǎn)即為簇成員。若覆蓋區(qū)可被無(wú)人機(jī)的地面服務(wù)半徑囊括，則無(wú)人機(jī)節(jié)點(diǎn)初始位置將位于該覆蓋區(qū)中心點(diǎn)位置，且保持懸停，如圖2（a）所示；反之，無(wú)人機(jī)節(jié)點(diǎn)將以可行的最小飛行半徑在覆蓋區(qū)上空盤旋，以服務(wù)該覆蓋區(qū)，如圖2（b）所示。

圖2 初始化過(guò)程中無(wú)人機(jī)初始位置分布

這些U-K個(gè)節(jié)點(diǎn)通過(guò)聚類得到K個(gè)簇，由剩余的K個(gè)節(jié)點(diǎn)作為簇頭分別管轄。同理，簇頭根據(jù)覆蓋能力與簇成員的分布，采用懸停或者盤旋的方式實(shí)現(xiàn)簇內(nèi)通信或者簇間通信。

3.3 基于K-means++的分簇算法

簇頭的個(gè)數(shù)K取決于簇頭節(jié)點(diǎn)的通信負(fù)載能力，因?yàn)榇仡^需要匯總簇成員的狀態(tài)信息并通過(guò)多跳傳給控制中心，而單位時(shí)間內(nèi)簇頭可通信的數(shù)據(jù)量和簇成員狀態(tài)信息量是確定的，由此可估計(jì)K的值。

將U-K個(gè)節(jié)點(diǎn)聚類成K個(gè)簇的過(guò)程中，主要根據(jù)節(jié)點(diǎn)的空間位置信息，采用K-means++進(jìn)行聚類。對(duì)于每個(gè)簇，簇頭節(jié)點(diǎn)則根據(jù)通信半徑以及簇成員分布，也采用懸停或者盤旋的方式，對(duì)簇成員進(jìn)行全覆蓋，并與其他簇頭構(gòu)成連通鏈路。由于周期T 的數(shù)量級(jí)在數(shù)分鐘到數(shù)小時(shí)不等，而控制中心根據(jù)當(dāng)前周期節(jié)點(diǎn)能耗情況預(yù)測(cè)并規(guī)劃下一周期的節(jié)點(diǎn)位置。因此，允許簇頭進(jìn)行節(jié)點(diǎn)狀態(tài)信息多跳傳輸?shù)臅r(shí)延較長(zhǎng)，則簇頭可采用盤旋覆蓋多簇成員，并且間歇地與其他簇頭連通，如圖3 所示。

圖3 簇頭盤旋覆蓋簇成員

3.4 基于遺傳算法的目標(biāo)函數(shù)優(yōu)化

為求解給定約束條件下的目標(biāo)函數(shù)，控制中心在獲取各個(gè)節(jié)點(diǎn)的狀態(tài)信息后，采用遺傳算法，預(yù)測(cè)下個(gè)周期各節(jié)點(diǎn)的最佳位置以及所分配的通信流量，流程圖如圖4 所示。

圖4 基于遺傳算法的組網(wǎng)機(jī)制

根據(jù)前述能耗公式以及目標(biāo)函數(shù)，第t個(gè)周期中，節(jié)點(diǎn)u的待優(yōu)化變量是移動(dòng)距離以及被分配的數(shù)據(jù)量為但其移動(dòng)距離是由優(yōu)化后節(jié)點(diǎn)的目標(biāo)位置決定，且設(shè)簇成員節(jié)點(diǎn)均在同一高度飛行，因此將對(duì)的優(yōu)化先轉(zhuǎn)化為對(duì)于節(jié)點(diǎn)平面位置坐標(biāo)的優(yōu)化。從而，將每個(gè)無(wú)人機(jī)節(jié)點(diǎn)的待優(yōu)化變量表示為三元組設(shè)種群個(gè)數(shù)為N，則第e代種群的第n個(gè)個(gè)體為U個(gè)無(wú)人機(jī)節(jié)點(diǎn)的三元組集合其中u=1,2,…,U；n=1,2,…,N。在公式（5）中的目標(biāo)函數(shù)作為每個(gè)個(gè)體的適應(yīng)度函數(shù)，在選擇、交叉、變異的計(jì)算后得到可以實(shí)現(xiàn)最佳適應(yīng)度值的三元組集合其中收斂條件是指達(dá)到最大代數(shù)或者最佳適應(yīng)度函數(shù)值變化小于給定誤差時(shí)停止迭代。

4 仿真及分析

4.1 仿真條件

仿真場(chǎng)景為1km*1km 的區(qū)域，劃分為100*100的服務(wù)網(wǎng)格，每個(gè)網(wǎng)格為10m*10m 的區(qū)域。簇頭無(wú)人機(jī)通信半徑RCH=300m，簇成員無(wú)人機(jī)通信半徑為RCM=200m，所覆蓋的地面區(qū)域半徑為Rc=125m，即每個(gè)無(wú)人機(jī)的地面覆蓋區(qū)包含25*25個(gè)服務(wù)網(wǎng)格。每個(gè)周期持續(xù)時(shí)間T設(shè)為10 分鐘。每個(gè)無(wú)人機(jī)初始能量為E0=100 個(gè)能量單位，懸停功率Po消耗每周期1 個(gè)能量單位，位移功率Pm消耗每周期2 個(gè)能量單位，飛行速度72km/h，傳輸單位容量數(shù)據(jù)量的功率Pa每周期消耗1 個(gè)能量單位。每周期整個(gè)區(qū)域的數(shù)據(jù)總量為Bt=100 個(gè)容量單位且呈二維高斯分布分布在各個(gè)服務(wù)網(wǎng)格，該分布如圖5 所示，均值和協(xié)方差如下：

圖5 通信數(shù)據(jù)量需求分布

每個(gè)無(wú)人機(jī)的通信負(fù)載上限bmax為10 個(gè)容量單位，允許的無(wú)人機(jī)移動(dòng)時(shí)長(zhǎng)τ設(shè)為3 秒。無(wú)人機(jī)總數(shù)U=10,15,20，每個(gè)簇頭無(wú)人機(jī)最多可服務(wù)4 個(gè)簇成員，即可能的簇個(gè)數(shù)為2,3,4。遺傳算法中種群個(gè)數(shù)設(shè)為15，交叉概率為0.45，變異概率為0.008，最大迭代代數(shù)為200，最大代間適應(yīng)度值誤差為0.001%。總仿真周期量為10 個(gè)周期，且為消除隨機(jī)性導(dǎo)致的性能偏差，重復(fù)仿真100 次后取平均。

本文在MATLAB 中將比較采用能耗均衡以及未采用能耗均衡的組網(wǎng)機(jī)制在數(shù)據(jù)傳輸完成率、節(jié)點(diǎn)最小剩余能量等方面的性能差異。

4.2 數(shù)據(jù)傳輸完成率比值

數(shù)據(jù)傳輸完成率可衡量負(fù)載分流的情況，其定義為所在周期中，所有無(wú)人機(jī)傳輸?shù)挠脩魯?shù)據(jù)量流量與總用戶數(shù)據(jù)流量之比。進(jìn)而，將未采用能耗均衡的組網(wǎng)機(jī)制的數(shù)據(jù)傳輸完成率與采用能耗均衡的組網(wǎng)機(jī)制的數(shù)據(jù)傳輸完成率的比值衡量提出機(jī)制的有效性，仿真結(jié)果如圖6 所示。

從圖中可以看出，隨著時(shí)間推移，所提出的機(jī)制逐漸體現(xiàn)優(yōu)勢(shì)。這是因?yàn)閰^(qū)域內(nèi)通信流量需求分布不均勻，因此覆蓋高通信流量區(qū)域的無(wú)人機(jī)可能超載，若不調(diào)整多個(gè)無(wú)人機(jī)位置完成負(fù)載分流，將導(dǎo)致無(wú)法完成需求通信量的傳輸。另外，隨著節(jié)點(diǎn)數(shù)減少，所提出機(jī)制的優(yōu)勢(shì)更加明顯，因?yàn)楦俚墓?jié)點(diǎn)將導(dǎo)致每個(gè)節(jié)點(diǎn)更接近滿載，只有合理的位置和負(fù)載的調(diào)度才能更好實(shí)現(xiàn)負(fù)載均衡。

圖6 數(shù)據(jù)傳輸完成率比值

4.3 節(jié)點(diǎn)最小剩余能量比值

節(jié)點(diǎn)最小剩余能量可衡量網(wǎng)絡(luò)中無(wú)人機(jī)能耗的最差情況，其定義為該周期結(jié)束后，該網(wǎng)絡(luò)所有無(wú)人機(jī)中剩余能量的最小值。當(dāng)無(wú)人機(jī)節(jié)點(diǎn)服務(wù)通信流量需求高的區(qū)域時(shí)，能耗較快，若干周期后很可能導(dǎo)致能量耗盡，并且對(duì)應(yīng)區(qū)域是熱點(diǎn)區(qū)域，因此對(duì)于整個(gè)網(wǎng)絡(luò)的吞吐量影響很大。圖7 呈現(xiàn)了未采用能耗均衡時(shí)節(jié)點(diǎn)最小剩余能量和所提出機(jī)制的比值。

圖7 節(jié)點(diǎn)最小剩余能量比值

由圖可見(jiàn)，節(jié)點(diǎn)最小剩余能量的比值隨著時(shí)間推移呈先上升后下降的趨勢(shì)。這意味著仿真周期的初期和末期，兩種機(jī)制在該指標(biāo)上的性能相當(dāng)，但所提出的機(jī)制在仿真周期中期展現(xiàn)出較大的優(yōu)勢(shì)。第一個(gè)周期時(shí)，兩種機(jī)制的無(wú)人機(jī)分布是相同的，因此能耗相同。后續(xù)周期中，所提出的機(jī)制不斷完成無(wú)人機(jī)位置和通信負(fù)載的調(diào)度，讓剩余較多能量的節(jié)點(diǎn)替換熱點(diǎn)區(qū)域能耗高的節(jié)點(diǎn)。同時(shí)，采用負(fù)載均衡使得熱點(diǎn)區(qū)域有更多的節(jié)點(diǎn)共同覆蓋，從而實(shí)現(xiàn)了在完成通信傳輸總需求量的情況下，無(wú)人機(jī)節(jié)點(diǎn)之間的能耗均衡。

5 結(jié)語(yǔ)

無(wú)人機(jī)集群所服務(wù)的區(qū)域的通信流量需求分布不均，且無(wú)人機(jī)能量有限。所提出的基于能耗均衡的無(wú)人機(jī)組網(wǎng)機(jī)制在分層分簇的網(wǎng)絡(luò)架構(gòu)下，通過(guò)控制中心集中管理，利用啟發(fā)式算法優(yōu)化無(wú)人機(jī)集群中節(jié)點(diǎn)位置和通信負(fù)載，可以實(shí)現(xiàn)更高的數(shù)據(jù)傳輸完成率，并有效降低無(wú)人機(jī)集群的整體能耗。在未來(lái)工作中，可引入人工智能算法，進(jìn)一步改進(jìn)組網(wǎng)機(jī)制的性能。