2013年--外文翻譯--無線傳感器網(wǎng)絡(luò)中基于集群通信拓撲結(jié)構(gòu)選擇和無人機路徑規(guī)劃（譯文）

1、<p>　　中文6460字，5300單詞，23700英文字符</p><p>　　出處：Ho D T, Grøtli E, Sujit P B, et al. Cluster-based communication topology selection and UAV path planning in wireless sensor networks[C]//Unmanned Aircraft

2、 Systems (ICUAS), 2013 International Conference on. IEEE, 2013: 59-68.</p><p>　　無線傳感器網(wǎng)絡(luò)中基于集群通信拓撲結(jié)構(gòu)選擇和無人機路徑規(guī)劃</p><p>　　摘要：在傳統(tǒng)的無線傳感器網(wǎng)絡(luò)中，低功耗自適應(yīng)集群分層型協(xié)議（LEACH）被普遍應(yīng)用以節(jié)省能量。在大規(guī)模部署中，節(jié)約能源非常困難。本文主要介紹了傳感器網(wǎng)絡(luò)

3、通信拓撲結(jié)構(gòu)的選擇和應(yīng)用無人機進行數(shù)據(jù)采集。為降低能源消耗和誤碼率，減少無人機飛行時間，本文采用粒子群優(yōu)化算法（PSO）尋找最佳集群。根據(jù)實驗結(jié)果表明，PSO在能耗和誤碼率方面更優(yōu)于LEACH協(xié)議，而無人機飛行時間一樣。實驗結(jié)果進一步表明兩者之間的性能差距隨著簇頭節(jié)點數(shù)量的增加而增大。降低能源消耗意味著網(wǎng)絡(luò)運行時間可顯著延長，而低誤碼率則可以大大增加網(wǎng)絡(luò)接收的數(shù)據(jù)量。</p><p><b>　　1 引

4、言</b></p><p>　　無人機系統(tǒng)技術(shù)（UAS）在各種軍用領(lǐng)域和民用領(lǐng)域已得到廣泛應(yīng)用。該技術(shù)主要應(yīng)用在雷達定位、野火管理、觀察支撐、農(nóng)業(yè)監(jiān)測、邊境監(jiān)視、環(huán)境監(jiān)測、氣象監(jiān)測和航拍，以及搜索救援任務(wù)。與傳統(tǒng)載人機相比，無人機系統(tǒng)技術(shù)最明顯的好處就是成本低，提高了人員的安全性，并且易于部署。無線傳感器網(wǎng)絡(luò)中的許多應(yīng)用采用了無人機系統(tǒng)技術(shù)來擴大通信范圍，通過使用運載工具作為中繼節(jié)點最大化網(wǎng)絡(luò)的數(shù)據(jù)通

5、信能力，從遠程或惡劣環(huán)境中收集數(shù)據(jù)，或協(xié)助節(jié)點在移動網(wǎng)絡(luò)中的定位。本文作者主要對這些方面進行研究，溢油應(yīng)急響應(yīng)、海冰監(jiān)測、船舶交通監(jiān)控和海水水質(zhì)監(jiān)測。然而，許多待探索的地區(qū)條件非常苛刻，并且很偏遠，由于缺乏通信基礎(chǔ)設(shè)施相對孤立。而建立永久性的通信基礎(chǔ)設(shè)施又非常昂貴，且難以保養(yǎng)。在這些區(qū)域中的地面上或海面上建立網(wǎng)絡(luò)節(jié)點，并應(yīng)用無人機收集這些網(wǎng)絡(luò)節(jié)點的數(shù)據(jù)是更容易和更便宜。根據(jù)調(diào)查，關(guān)于如何從無線傳感器網(wǎng)絡(luò)節(jié)點中收集數(shù)據(jù)已有廣泛研究。在這些

6、網(wǎng)絡(luò)中，簇中的傳感器節(jié)點通常被凝結(jié)和相互連接。因此，這些節(jié)點都是通過它們的簇頭（CH）節(jié)點與基站進行通信。因此，這些節(jié)點之間需要多跳數(shù)據(jù)通信。這可能會消耗大量的能量，由于集群中大量的通信和</p><p><b>　　2 相關(guān)工作</b></p><p>　　無人機在不同限制條件下的路徑優(yōu)化問題已經(jīng)有了幾十年的研究。根據(jù)不同的應(yīng)用環(huán)境，所采用的目標函數(shù)和優(yōu)化方法也不一

7、樣。本文的目標是為了使通過節(jié)點的最能耗最低；任何節(jié)點和它的簇頭節(jié)點之間，簇頭節(jié)點和無人機之間通過無線通道的數(shù)據(jù)通信質(zhì)量最好；無人機飛行時間最短。目標是提供一個無人機能訪問到的節(jié)點列表。優(yōu)化在每一個無人機飛行任務(wù)之前運行，其解決方安案為無人機完成一次數(shù)據(jù)采集提供了一條路徑。參考無線傳感器網(wǎng)絡(luò)與無人機之間的通信質(zhì)量表明，如果無人機一次與較少的傳感器節(jié)點通信，那么誤碼率就較低。然而，無人機需要飛過網(wǎng)絡(luò)中的所有節(jié)點，飛行時間會顯著增長。這個問題

8、在集群中分組的節(jié)點和只有簇頭節(jié)點被無人機訪問的地方較好。集群技術(shù)只取決于通信能力或距離，這導(dǎo)致通信質(zhì)量差或低能源利用率是低效的。這里最小化訪問所有節(jié)點時間的簇頭節(jié)點的優(yōu)化與推銷員覆蓋問題（CSP）的研究相似。在CSP中，目標是最小化總行駛時間或銷售員至少訪問沒有交集集合中的一個無素的距離。研究表明，通信質(zhì)量（BER）和網(wǎng)絡(luò)模型中的行駛距離或時間是相關(guān)聯(lián)的。這可以在本文第五節(jié)中看見。</p><p>　　能耗問題在

9、傳統(tǒng)的傳感器網(wǎng)絡(luò)中是個具有挑戰(zhàn)性的問題，它涉及到如網(wǎng)絡(luò)拓撲結(jié)構(gòu)的跨層設(shè)計、集群算法、傳輸方法和MAC協(xié)議。在之前的論文中，已經(jīng)提出了針對廣域傳感器網(wǎng)絡(luò)的節(jié)能MAC協(xié)議和網(wǎng)絡(luò)編碼方法。在本文中我們專注于集群算法，這一般取決于網(wǎng)絡(luò)是集中式或分散式。因為我們假設(shè)無人機有網(wǎng)絡(luò)的全部信息，所以集中式集群解決方案會被使用。在傳統(tǒng)的無線傳感器網(wǎng)絡(luò)中，集中式低功耗自適應(yīng)集群分層協(xié)議（LEACH-C）被普遍使用在各種應(yīng)用環(huán)境下，因為它的效率和節(jié)點上的低運

10、算負重。然而，大面積的傳感器網(wǎng)絡(luò)中的節(jié)能比正常的無線傳感器網(wǎng)絡(luò)中的更具有挑戰(zhàn)性，一個更好的優(yōu)化方法是很有必要的。相比于普通的傳感器節(jié)點，應(yīng)用基于迭代技術(shù)的粒子群優(yōu)化（PSO）算法，無人節(jié)的能耗和計算能力很有優(yōu)勢。其結(jié)果是在同等條件下與LEACH-C比較的結(jié)果。在第三節(jié)和第四節(jié)我們將說細解釋LEACH-C和PSO是如何被修改并應(yīng)用于我們的網(wǎng)絡(luò)優(yōu)化問題。</p><p>　　3低功耗自適應(yīng)集群分層協(xié)議（LEACH）&

11、lt;/p><p>　　LEACH是一個旨在降低無線傳感器網(wǎng)絡(luò)能耗的集群算法。它是一個沒有任何中心節(jié)點的分布式方案。在LEACH中，每個節(jié)點能依賴一些概率函數(shù)自主決定是否會成為一個簇頭節(jié)點。簇頭的數(shù)量可以變化，集群主要是基于節(jié)點到簇頭節(jié)點的最短歐式距離。是否為成為一個簇頭節(jié)點的獨立決策可能會導(dǎo)致網(wǎng)絡(luò)中一些節(jié)點的能量引流加速。LEACH-C是一個集中式方案，它可以改善一些與LEACH相關(guān)的問題。在LEACH-C中，關(guān)于

12、位置和所有節(jié)點剩余能量的信息會被發(fā)送至每個無人機起始處的基站。然后，基站將計算網(wǎng)絡(luò)中的平均能耗水平，將高于平均水平的節(jié)點看作是簇頭節(jié)點?；緦⒃谶@些節(jié)點中隨機選擇一些候選節(jié)點，并計算它們各自的目標函數(shù)。此過程重復(fù)多次迭代，比較目標函數(shù)值以找到最適合的簇頭節(jié)點。在無線傳感器參考文獻中，普遍使用的目標函數(shù)是基于簇頭節(jié)點和它們成員節(jié)點間的平均距離。所選的簇頭節(jié)點然后會通過無人機傳播到網(wǎng)絡(luò)中所有的節(jié)點。為了啟動它的數(shù)據(jù)傳輸，網(wǎng)絡(luò)中的每個節(jié)點然后

13、將需要找到最近的簇頭節(jié)點。在我們的網(wǎng)絡(luò)系統(tǒng)中，目標函數(shù)更復(fù)雜，將在第4節(jié)進行說明。</p><p>　　4粒子群優(yōu)化算法（PSO）</p><p>　　無線傳感器網(wǎng)絡(luò)中的許多應(yīng)用是采用PSO作為一個有效的集群算法。PSO背后的是想法是模擬鳥群和魚群的社會行為。PSO算法是一種計算方法，基于一些基本規(guī)剛反復(fù)嘗試來改進種群或粒子的候選方案的方法。對于每個粒子，S是粒子的數(shù)量，粒子的位置（）根據(jù)

14、公式（1）來更新，粒子的速度（）根據(jù)公式（2）來更新。</p><p>　　這里，是粒子i最好的位置，g是種群最好的位置，參數(shù)ω是慣性權(quán)重，CP和Cg（加速度常數(shù)）是調(diào)整參數(shù)。一個方案的適合度是基于函數(shù)的值，它能被最小化。，粒子的最好位置被更新。，種群的最好位置被更新。</p><p>　　粒子的初始位置在搜索空間中均勻分布，即，其中和分別是搜索空間的最小邊界和最大邊界。粒子初始速度是。算

15、法會在用戶指定迭代次數(shù)或一些依賴適應(yīng)度函數(shù)的其它標準后結(jié)束。</p><p>　　PSO能被用于集群以及查找集群的質(zhì)心向量。每個粒子Xi為含有質(zhì)心的位置向量的候選解決方案。本文PSO算法用于集群和簇頭選擇。因為我們要求它們的位置從傳感器位置中選擇。記作簇頭節(jié)點的數(shù)量，N記作傳感器網(wǎng)絡(luò)中的傳感器數(shù)量。我們還涉及成一種二維問題，并且假定每個傳感器的位置是已知的。由于Xi包含所有簇頭節(jié)點的的候選解決方案。Xi向量的長度

16、是。為強制簇頭節(jié)點位置從傳感器位置中選擇，我們引入了函數(shù)，它接收一個搜索空間中的位置向量，例如：粒子位置向量Xi，返回Xi最近的傳感器的位置向量。例如：如果，，其中是公式（3）的解決方案。</p><p>　　，，是傳感器網(wǎng)絡(luò)中的一組坐標集。</p><p>　　這些簇頭是根據(jù)適應(yīng)度函數(shù)（公式4）選擇的。</p><p>　　其中是加權(quán)常量，f1是網(wǎng)絡(luò)能耗，f2是傳

17、輸誤碼率，f3是無人機總行駛時間。每一項將在以下章節(jié)里解釋。</p><p><b>　　A．網(wǎng)絡(luò)能耗</b></p><p>　　非簇頭節(jié)點j的總能耗由下式給出：</p><p>　　其中l(wèi)是數(shù)據(jù)包的比特長度，是控制包的比特數(shù)目，是從節(jié)點j到第i個集群簇頭節(jié)點傳輸一個比特位的能耗。是標位發(fā)射功率，是接收一個比特位的能耗，R0是廣播消息中使用的

18、比特率。由下式得到：</p><p>　　其中，發(fā)射功率是根據(jù)節(jié)點j和它的簇頭節(jié)點i之間的鏈路預(yù)算調(diào)整的。在第一種情況下，，其中，是節(jié)點j與簇頭節(jié)點i之間的路徑損耗，i能從節(jié)點j用標準發(fā)射功率接收數(shù)據(jù)。在第二種情況下，，發(fā)射功率被控制來增加節(jié)點j的發(fā)射功率到，這樣簇頭節(jié)點i能在基本頻率上接收數(shù)據(jù)，根據(jù)和的接收長度是節(jié)點j和簇頭節(jié)點i上的總增益。是用帶寬B和最小比特率從香農(nóng)定理計算出來的值。在這種假設(shè)情況下，節(jié)點間

19、的距離相比于它們天線之間的高度是大的。j與簇頭節(jié)點i之間的路徑損耗能通過這個模型被計算出來。</p><p>　　其中，Gj和Gi是發(fā)送（節(jié)點j）和接收天線（簇頭節(jié)點i）之間的增益，hj和hi是地面或節(jié)點天線表明上的高度，dji是它們之間的距離。在廣域無線傳感器網(wǎng)絡(luò)中，節(jié)點之間不是相互靠近，因此假定簇頭節(jié)點i將接收和轉(zhuǎn)發(fā)它成員節(jié)點的數(shù)據(jù)給無人機是適合的。因此，在第i個集群中，簇頭節(jié)點與它成員節(jié)點之間的總能耗是：&

20、lt;/p><p>　　其中，是傳輸一個位的能耗。一般正常情況下和是一樣的，因此可寫成：</p><p>　　其中，Ni是包含簇頭節(jié)點i的第i個集群中的傳感器節(jié)點的數(shù)量，Eiu是從簇頭節(jié)點i傳輸?shù)綗o人機每個位的能耗，EDA是數(shù)據(jù)匯合后每位的能耗。Eiu的表達式被類似于公式（6）進行計算。</p><p>　　其中，是當和無人機通信時節(jié)點i必須的發(fā)射功率，在第一種情況下的

21、標準值PT0是大到足以維持無電源控制通信，也就是說，，其中，是簇頭節(jié)點與無人機之間的自由空間路徑消耗。對所涉及的通信鏈路的路徑消耗是：</p><p>　　其中，f是射頻，單位HZ，diu是簇頭節(jié)點i與無人機之間的距離，單位米。在第二種情況下，，能量控制是這樣被應(yīng)用，，其中Giu是簇頭節(jié)點i與無人機天線之間的增益。</p><p>　　公式（4）中引入的f1為：</p>&l

22、t;p><b>　　A．誤碼率</b></p><p>　　誤碼率通常取決于數(shù)據(jù)的調(diào)制方式和發(fā)射機與接收機之間的通信信道。在傳感器網(wǎng)絡(luò)中我們通常最關(guān)注的是數(shù)據(jù)通信的節(jié)點能耗。因此，M-QAM調(diào)制被建議用于所有的節(jié)點。該方案的平均誤碼率估計：</p><p>　　其中，M是調(diào)制率，g = 1.5/(M ? 1)。是一個MGF，它用于性能分析；是積分的角度變化。&l

23、t;/p><p>　　如果無線信道是地面上的任意兩個節(jié)點之間，那么無線電波傳播路徑上的地面反射是顯著。例如：一個節(jié)點j與它的簇頭節(jié)點i之間的符號錯誤率能用公式（13）計算出來。</p><p>　　這里，是指通過該信道的固定路徑損耗的干擾加噪聲比（SINR）的平均信號?；旧希琒INR等于，其中I是位于周圍接收節(jié)點所有源的干擾，N0是該信道的噪聲。針對簇頭節(jié)點i與飛過它的無人機u之間的通信，這

24、個視距通常是顯著的，所以可以用萊斯多徑衰落分布來計算：</p><p>　　這里，K是水稻因子和表示LOS路徑的在反射路徑部分中的主導(dǎo)地位。從之前空對地通信系統(tǒng)的研究中，K的值可以根據(jù)上面節(jié)點入射角而變化。然面，該模型中，所有無人節(jié)和節(jié)點都配備了一個數(shù)組天線，因此這不會影響到K的值。在這種情況下，天線陣列只適用于無人機，這種影響必須要考慮到。為了評估節(jié)點與節(jié)點之間、節(jié)點與無人機之間通信的誤碼率，Ps按下式轉(zhuǎn)換成P

25、b：</p><p>　　公式（4）中引進的f2為：</p><p>　　其中分別是節(jié)點j與簇頭節(jié)點i，簇頭節(jié)點i與無人機之間通信的誤碼率。</p><p>　　C．無人機路徑與行駛時間</p><p>　　在第四節(jié)介紹的適應(yīng)度函數(shù)f3是無人機訪問所有簇頭節(jié)點的總行駛時間，然后返回到基站。假定無人機的速度是個常量，那么花費的時間就與總距離成正

26、比。由于我們專注于利于固定翼無人機收集數(shù)據(jù)，因此，歐幾里德旅行商問題（TSP）不能為無人機提供一個可行的軌跡。相反，我們基于Dubins TSP的解決方法計算f3，它提供了一個可行的路徑。一個Dubins（最短）路徑是連續(xù)可微，幾乎無處不在，包括直線和有界曲率圓弧。在本文中我們計算f3作為交替TSP算法的解決方案。這是建設(shè)性的、保守的總長度能夠從解決方案中提供給Euclidean TSP的。這個適應(yīng)度函數(shù)f3是：</p>

27、<p>　　其中，ρ>0是最小的轉(zhuǎn)彎半徑，v為UAV速度，P是個簇頭節(jié)點集，是Euclidean TSP解決方案的長度。</p><p>　　請注意，對于在運輸中的無人機，假設(shè)燃料消耗與拖動成正比是合理的，而這又可以假設(shè)為正比于速度的平方。如果無人機在運輸過程中的大多數(shù)時間是以恒定或幾乎恒定的速度運行，那么消耗的能量正比于行駛距離和行駛時間。</p><p><b&g

28、t;　　5 仿真</b></p><p>　　對兩個方案LEACH-C和PSO用不同集群簇頭節(jié)點的數(shù)量做了大量的模擬實驗。對于所有的模擬實驗中，網(wǎng)絡(luò)中的傳感器數(shù)目保持恒定，在5平方公里的區(qū)域中隨機生成位置。在每種模擬情況的開始時，它們都擁有一樣的初始能量E0。每輪數(shù)據(jù)收集，優(yōu)化算法運行次迭代。模擬的總數(shù)是2000次，每次當網(wǎng)絡(luò)中的所有節(jié)點的能量排出時停止。在每一輪開始，優(yōu)化算法的結(jié)果將提供給無人機一個

29、應(yīng)當飛過和從中收集數(shù)據(jù)的簇頭節(jié)點集合。這個簇頭節(jié)點集也通過廣播被傳送至網(wǎng)絡(luò)的所有節(jié)點中。每個節(jié)點需要找到它的最好的簇頭節(jié)點，準備與這個簇頭節(jié)點進行數(shù)據(jù)通信。</p><p>　　在這些模擬中，簇頭數(shù)目從網(wǎng)絡(luò)中節(jié)點總數(shù)的5%變化到15%。為了讓兩種算法的模擬結(jié)果具有可比性，LEACH-H和PSO兩種算法選擇簇頭節(jié)點的迭代次數(shù)是一樣的。此外，所有和無人機飛行相關(guān)的其它參數(shù)，數(shù)據(jù)通信和仿真條件是相同的，在表1中顯示。假

30、定這兩個傳感器節(jié)點與無人機都配有陣列天線，并且在通信過程中，發(fā)射機和接收機都指向彼此。如果Tx和Rx的位置信息是已知的，那么這種假設(shè)是可行的。無人機假定在200米的恒定高度和地面速度40m/s，120米的最小轉(zhuǎn)彎半徑下飛行。仿真結(jié)果表明，適應(yīng)度函數(shù)所有項的性能，其中包括網(wǎng)絡(luò)中的平均能耗、平均誤碼率和無人機行駛時間。其他結(jié)果，如活/死節(jié)點、節(jié)點分布，以及LEACH-C和PSO的適應(yīng)度函數(shù)值進行了分析。</p><p&g

31、t;　　根據(jù)圖1、圖2和圖3的結(jié)果表明，在一樣的仿真條件和網(wǎng)絡(luò)拓撲下，PSO相較于LEACH-C性能更好。例如：在一樣的簇節(jié)點數(shù)目下，通過PSO提供的飛行路徑里的網(wǎng)絡(luò)節(jié)點的總能耗比LEACH-C提供的路徑更低。從圖2中可以看出，使用粒子群優(yōu)化方案剩余網(wǎng)絡(luò)中的活節(jié)點的數(shù)量始終比為LEACH-C方案更多。此外，這3個圖表明，網(wǎng)絡(luò)中簇頭節(jié)點的數(shù)目越高，能耗和誤碼率就越低，這也解釋了更高的存活節(jié)點數(shù)。圖2也表明，使用PSO方案時20個簇頭節(jié)點比

32、使用LEACH-C方案時30個簇頭節(jié)點的效果還好。這一趨勢與圖4中的結(jié)果相匹配，表示適應(yīng)度函數(shù)的最佳值來自這兩種算法。圖4顯示出PSO相較于LEACH-C的主要改進之處。在這兩種情況下，使用LEACH-C和PSO兩種方案的自適應(yīng)度值開始時略微升高，然后在數(shù)輪數(shù)據(jù)收集后開始降低。似乎合理的理由是，此刻幾乎所有節(jié)點已經(jīng)死了，但簇頭節(jié)點的數(shù)量仍然不變。因此，與無人機直接通信節(jié)點的比率增加了。這導(dǎo)致一個事實，誤碼率和無人機的行駛時間變低。由于P

33、SO方案在節(jié)點節(jié)約能源中性能更好，所以在網(wǎng)絡(luò)中仍然有許多存活著的節(jié)點。圖5和圖6顯示了其進一步分析，描繪了死節(jié)點和活節(jié)點的位置。</p><p><b>　　6 結(jié)論</b></p><p>　　在本文中，我們已經(jīng)評估了兩種算法在無人機訪問節(jié)點的優(yōu)化選擇上的性能。在我們的目標函數(shù)中，網(wǎng)絡(luò)的能源消耗、通信質(zhì)量和無人機的行駛時間都是通過PSO算法進行優(yōu)化的。在仿真中，我們