FANET中時延感知的跨層優化方法

文少杰，黃傳河

（武漢大學計算機學院，湖北 武漢430072）

和傳統的路由方法一樣，源節點預先為每一個數據分組建立一條端到端路徑，而這條路徑的生命周期不是確定的而是與路徑上鏈路的最小連通時間有關[9]。網絡中每一個節點廣播路由請求消息將會消耗大量不必要的資源，因為在FANET中每個GB的位置一般是固定的，每個節點都存儲有GB的相關信息，所以需要采用一些方法減少廣播帶來的資源消耗。定義一個變量SPP（single-hop packet progress）[27]表示中繼節點j相對于它的父節點i對數據產生的距離增益。

1 引言

無人機（UAV,unmanned aerial vehicle）可以作為傳感器收集環境中的數據，并把這些收集的數據傳遞到地面基站（GB）[1]。單架UAV系統由于其靈活性、易安裝和可擴展性等特點已經被廣泛地應用于不同的場景中[2]，但是單架UAV系統由于受到功能簡單、覆蓋范圍有限的限制，因此不能擴展到更多的應用中。為了克服單架 UAV系統的不足，可以通過不同UAV之間的協作建立multi-UAV系統[3]擴展應用范圍。在multi-UAV系統中，由于受到通信半徑的限制單架UAV與GB之間的鏈路可能會出現不連通的情況，這種局限性縮小了multi-UAV系統的應用范圍。一種可選的解決方案是在不同的UAV之間建立ad hoc模式的網絡，稱為飛行自組網絡（FANET,flying ad hoc network）。在FANET中，每架UAV可以通過單跳或多跳方式與GB進行通信，同時每架UAV既可以作為源節點也可以作為中繼節點幫助其他UAV傳遞數據分組。與單架UAV系統相比，FANET具有更好的靈活性和可擴展性，它允許 UAV可以根據實際需求選擇不同的通信模式，同時也允許 UAV可以在一定范圍內自由地飛行從而擴大監測的范圍。盡管FANET能夠彌補單UAV系統的不足，但是FANET也面臨一些挑戰，其中，實時路由、速率分配和功率控制是3個主要的問題。

FANET具有更高的移動性和空間維度[4]，這導致源節點和目的節點之間預先建立的路徑可能會很快失效，因此，FANET中的路由問題需要考慮節點之間的連通時間。實時路由要求每一種數據分組在時延約束內到達目的節點，如何設計一種算法同時滿足FANET的特征和時延約束的要求是主要研究的內容之一。UAV處于三維空間中，它們之間建立的鏈路更易受到其他無線信號的干擾，如何選擇發射功率既能減少信號之間的干擾又能保證傳輸的可靠性是另一個研究的主要內容。一個精確的干擾模型不僅能夠使傳輸者選擇更合適的中繼節點而且也能夠保證每個數據分組以較高的概率傳遞到目的節點。在FANET中，UAV之間的鏈路容量受到物理信道的約束，每個 UAV的傳輸速率被限制在一定的范圍內，如果超出了這個范圍數據分組將不能被正確地接收到。傳輸速率的上界是由發射功率和干擾信號決定的，因此，需要選擇合適的發射功率和傳輸速率，既保證端到端傳輸的可靠性又滿足實時路由的要求。根據FANET的特征可知，鏈路狀態的快速變化使集中式優化方法不能很好地工作，而分布式的方法可以很好地解決這個問題，因為它允許每個 UAV僅與鄰居交換信息來更新所對應的網絡參數而不需要全局拓撲知識。為了實施分布式方法，首先利用拉格朗日松弛方法把集中式問題轉化為分布式問題，然后使用原始—對偶分解方法[5]把全局問題分解為若干個規模較小的子問題。由于無線鏈路的不可靠性，數據分組在傳輸過程中的丟失容易導致部分中繼節點不能根據當前的信息更新網絡參數。傳統的同步優化方法[6]需要所有節點在同一時刻根據最新接收到的數據分組更新參數，這在不可靠的通信環境中很難實現。異步優化方法[7]允許節點在沒有接收到最新數據分組時使用最近保存的信息更新參數，所以利用異步優化方法能夠很好地解決因數據分組丟失導致部分節點不能正常更新參數的問題。本文的主要貢獻包括以下2點。1) 提出時延約束的跨層優化框架，利用拉格朗日松弛和原始—對偶分解技術把問題劃分為若干個多項式時間可解的子問題。2) 提出基于異步更新的時延感知分布式優化算法，每一個中繼節點僅使用局部信息更新原始和對偶變量以達到最優解。

2 相關工作

對于FANET中的路由問題，目前，已經存在很多的研究工作[8,9]，它們通過構建不同的網絡模型和考慮不同的網絡參數設計路由算法以滿足FANET的需要。這種僅考慮路由優化的算法局限性比較大，在考慮實時性和信號干擾的情況中不能很好地工作。跨層優化問題在其他網絡中提出了很多解決方案，文獻[10]針對智能電網絡通信的服務質量問題，提出了一種滿足端到端時延約束的跨層優化算法以保證物理層、MAC層和網絡層能夠很好地進行交互。在實時的無線網絡中，為了聯合優化速率控制和調度問題，文獻[11]提出了2種簡單的分布式策略，其中，優化操作在每個節點處完成而不要求節點間的協同；文獻[12]提出了一種基于干擾管理的高容量跨層優化策略，在多跳多基站場景中考慮干擾消除和區域劃分方法，并基于最小跳數建立的路由或多時間片分配設計吞吐量更大的優化策略。上面介紹的優化方法雖然能夠很好地解決所提出的問題，但是不能直接應用于鏈路狀態快速變化的FANET中。

UAV的高速移動性導致FANET的網絡拓撲快速變化和鏈路不可靠，這些特征使源節點和目的節點之間預先建立的路徑很快失效。同步優化方法[13,14]需要所有節點在同一時刻更新自身的網絡參數，而在多跳不可靠傳輸中這些方法不能正常工作。雖然文獻[15]考慮端到端時延要求下的動態速率分配方案，但是它要求網絡中所有節點同步地更新原始和對偶參數，這種操作將會帶來大量的通信開銷，在資源有限的FANET中是不合適的。然而異步優化方法不需要節點間的協作，每個節點可以使用舊的信息更新當前的參數，這些方法在時延較大和通信質量較差的場景中能夠保證算法的收斂性和優化性能。異步方法的優勢使它在不同的場景中得到廣泛的應用，包括智能電網[16]、通信網絡[17]等。近些年，出現了很多異步優化方法[18,19]，這些方法從不同的角度出發，例如，目標函數的性質、算法收斂速率和解的優劣等，設計不同的參數更新方法以滿足應用的需要。文獻[18]針對可分的非平滑成本函數分布式優化問題提出了一種基于隨機對偶近似梯度的異步優化算法。文獻[19]研究了非凸和非平滑優化問題中ADMM的異步實施問題，該文提出的算法在每次迭代過程中只需要部分節點更新自身的參數。在這些文獻中，文獻[18,19]提出的異步優化方法假設通信的時延是有界的，而文獻[17]討論了在通信時延不受限制的情況下如何保證異步對偶子梯度方法的性能，并在可分的凸規劃中給出了一種解決方案。文獻[7]針對編碼無線網絡多播場景中的資源分配問題，結合異步優化的思想提出了一種聯合優化端到端傳輸層速率、鏈路容量和平均功率消耗等的跨層設計方案。文獻[20]研究了如何以在線的方式設計一個平均最優的資源分配策略問題，并提出一種異步遞增對偶下降的資源分配算法，其中每個節點使用時延的隨機梯度更新參數。文獻[7,20]解決了不同網絡模型中的跨層優化問題，但是它們都沒有考慮實時性和動態拓撲問題。FANET是自組織的網絡，網絡中的所有節點都是同構和快速移動的，而這些移動節點構成隨機變化的網絡拓撲，文獻[20]中的多跳模式建立在環形網絡拓撲基礎上，不能滿足 FANET的要求。

針對以上方法的局限性，結合異步更新的思想并同時考慮端到端時延和每個中繼節點處的干擾，本文提出一種分布式的跨層優化方法解決所提出的問題。

3 網絡模型和問題描述

3.1 網絡模型

假設UAV基本均勻地分布在一定的區域內，每個UAV同時可以作為源節點和中繼節點，而地面基站（GB）只作為目的節點。所有的UAV可以自由地在區域內飛行，而GB的坐標在任意時間固定不變，UAV可以通過一跳或多跳的傳輸模式把數據傳遞到GB，如圖1所示。使用無向圖G=(V,E)表示FANET的網絡拓撲結構，其中，V表示所有UAV的集合，E表示網絡中所有鏈路的集合（圖1中UAV之間的虛線）。為了簡化符號，節點i表示第i個UAV。如果節點i發射的信號能夠被節點j正確的接收到，那么節點，其中是節點i在t時間的鄰居集合。二元組(i,j)表示一條連接節點i和節點j的鏈路，也可以用符號l代替。第k個數據流在鏈路l上消耗的時延表示為，端到端時延不能超過預設的時延閾值。假設每一個數據流具有相同的時延閾值，網絡中所有節點都存儲關于GB的位置信息，并且每個節點具有相同的通信半徑R。每一個中繼節點可以根據問題的最優解在[pmin,pmax]中選擇發射功率p和確定傳輸速率r。

圖1 FANET模型

3.1.1 干擾中斷概率

為了提高傳輸效率，減少網絡資源和時延的消耗，每一個中繼節點需要評估與鄰居節點之間的鏈路質量。由于網絡中每一個節點的位置隨著時間變化，所以任意2個節點之間的距離也是動態變化的。為了評估動態性對傳輸的影響，利用干擾預測方法[21]得到Δt時間內每個中繼節點處的平均干擾值。表示在t0時刻消息可用的情況下t時刻的干擾值，當t0=t時稱為t時刻的瞬時干擾值。在移動場景中，由得到的瞬時SINR不能很好地反映一段時間內鏈路的質量，而平均SINR可以很好地滿足這個要求。假設f(x)和g(x)分別表示與時間t相關的鏈路增益函數和衰減函數，在節點j處的預測干擾可以表示為

根據式(1)可以得到鏈路(i,j)上的平均SINR，其中，傳輸者為節點i，接收者為節點j，則有

其中，W表示網絡帶寬，其值為常數。參考文獻[22]中速率中斷概率的定義，鏈路質量表示為節點i的傳輸速率不超過鏈路容量 cl的概率。假設路徑增益服從方差為σ2=1的指數分布，速率中斷概率可以表示為

3.1.2 排隊時延

在每一個中繼節點處只考慮排隊時延，假設數據分組服從均值為Kbit的指數分布，每一個節點維持單一的隊列。根據文獻[23]計算的結果，當到達過程服從獨立的指數分布時，在t時刻鏈路l的期望排隊時延可以近似表示為

其中，rl和cl分別表示t時刻的傳輸速率和鏈路最大容量。

3.1.3 鏈路連通時間

為了延長路徑的使用時間，減少重建消耗的網絡資源，每一個源節點盡量選擇生命周期較長的路徑傳輸數據流。在t0時刻，節點i和j的坐標分別為移動速率向量分別表示為和根據t0時刻節點i和j的坐標可以得到它們之間的距離為，如果在一定時間間隔內所有節點勻速地沿著各自的方向移動，那么經過Δt時間后節點i的坐標為

3.2 問題描述

式(11)為聯合成本函數，主要目標是最小化以有效傳輸速率和功率為參數的成本函數。式(12)保證每一個發送者所使用的傳輸速率不能超過當前鏈路的最大容量，根據式(4)可知，鏈路的質量和期望排隊時延與中繼節點的傳輸速率相關，選擇合適的速率不僅能夠保證鏈路可靠性也能減少單跳時延。實時路由問題是需要考慮的一個主要問題，式(13)表示每一個數據流所消耗的端到端時延不能超過給定閾值，否則數據分組將會被中繼或GB丟棄。由于硬件的限制每一個節點不能用無限大的功率傳輸數據分組，式(14)把中繼節點發射功率限制在一定的范圍內，既要保證傳輸的可靠性又要減少對其他數據流的干擾。

4 分布式解決方案

集中式的優化方法需要網絡中的每一個節點頻繁地與控制中心通信來更新網絡參數以得到最優解，這種優化方法在節點快速移動的FANET中是不可取的。一方面，節點頻繁地與控制中心交換信息將會消耗大量的帶寬和功率資源，同時并發的傳輸將會對其他鏈路產生干擾，降低鏈路質量。另一方面，集中式優化需要控制中心接收到所有節點發送的更新信息才能進行下一步優化，在鏈路質量較差的情況中，控制中心可能會花費大量的時間等待最后一個節點的更新信息。以上2個方面決定了集中式優化方法不能用于高速移動的實時傳輸場景，而分布式的方法[25]可以很好地解決集中式方法存在的問題，它僅需要節點與其鄰居節點交換更新信息來執行優化操作。由于提出的跨層優化問題是一個非凸問題，利用對偶分解[5]方法可以把非凸約束消除使問題轉化為凸優化問題。

為式(12)引入拉格朗日對偶向量λ，向量中的每一元素λij對應一條鏈路的約束，問題可以轉化為

重新組合式(15)可以得到另外一種形式

根據式(16)可知，提出的跨層優化問題被分解為2個子問題，分別為

從式(17)和式(18)的結構和函數定義可知，2個子問題都為凸優化問題。式(17)聯合優化實時路由和速率分配問題，而式(18)主要優化功率控制問題，2個問題都可以利用分布式的方法在每個節點處獨立地執行。對于式(17)還需要解決另外一個問題，由于路徑的時延約束條件是全局耦合的，所有包含在路徑上的節點必須要協同的工作才能使端到端時延滿足式(13)。為了消除全局耦合約束式(13)，利用原始分解方法[5]進一步對式(17)進行劃分。引入一個輔助向量y把全局約束式(13)轉化為局部約束，y中的每一項與單條鏈路上的時延約束相關。通過考慮向量y，可將式(17)轉化為

如果把 yij看作t時刻鏈路l上的單跳時延閾值，優化式(19)可以劃分為2個子問題，對于每一個發送節點i，其優化目標為

假設F?(y)表示問題式(20)在時延約束向量y時的最優成本函數，通過解決下面的優化形式更新耦合的時延約束集合y

為問題式(20)中的時延約束引入對偶向量μ，問題轉化為

推論1 如果式(21)和式(22)存在最優解，那么對偶向量μ滿足條件

證明 為式(21)引入對偶向量β，可以得到

因為βij和yij是正數，可以得到用不等式右邊的項代替左邊的項，式(23)可以改為

其中，βij?可以看作分配給鏈路l的最大可用時延時間。如果向量y?是式(23)的最優解，那么它一定也是式(24)的最優解，所以和成立。因為?是一個常數，所以可以得到式(22)得到最優解或可行解的前提是式(22)中所使用的向量y必須是式(21)的最優解或至少是可行解。根據這個思路可以得到2個問題中對偶向量μ和β的關系，即與是等價的。如果式(21)得到的解y?能夠滿足(22)的約束條件，那么必須滿足結合之前的結論，可得

假設式(21)存在一個最優解y?，那么跨層優化問題的對偶形式可以表示為

利用傳統的基于對偶的優化方法，可以得到向量λ和μ在每一次迭代的更新操作為

其中，ε和ξ分別表示2個更新操作的步長，[x]+表示參數x在非負象限內的投影即由于FANET中節點的高速移動性導致鏈路的連通性快速變化，所以選擇常數步長可以保證優化問題的收斂性和加快收斂速率[26]。根據對偶參數值可以計算在t+1時刻原參數rij和pi的值，即

式(26)～式(29)提出的解決方案只適合于同步優化的場景，因為優化過程中的每一次迭代都需要最新的參數信息。在FANET中，由于節點的移動性和信號的干擾導致鏈路質量較差，數據分組將會因為消耗的總時延大于給定的閾值而被丟棄，因此，部分中繼節點可能在有些時候接收不到當前的參數信息。在以上提到的場景中同步優化不能很好地進行工作，所以為了解決這個問題使用異步更新的方式優化不同的網絡參數。異步更新方法允許數據分組在傳輸過程中丟失，沒有接收到數據分組的節點可以使用它們存儲的舊信息來更新網絡參數。定義變量τij(t)和?ij(t)為在迭代序列t上的投影，即離t最近一次迭代的序號。因為每個數據分組有一個時延閾值，當傳輸在一些中繼節點消耗的時延大于閾值時，中繼節點認為當前數據分組失效并丟棄它，而之后的節點可以根據存儲的舊參數信息進行更新。這樣利用τij(t)和?ij(t)代替當前迭代序列t，如果中繼節點接收到了數據分組，則有τij(t)=t和?ij(t)=t，更新操作式(26)和式(27)可以修改為

原問題中的參數更新操作式(28)和式(29)保持不變。為了使優化問題快速地收斂到最優解，實際操作中利用到目前迭代t的平均值代替式(28)和式(29)參數rij和pi，其中，

和傳統的路由方法一樣，源節點預先為每一個數據分組建立一條端到端路徑，而這條路徑的生命周期不是確定的而是與路徑上鏈路的最小連通時間有關[9]。網絡中每一個節點廣播路由請求消息將會消耗大量不必要的資源，因為在FANET中每個GB的位置一般是固定的，每個節點都存儲有GB的相關信息，所以需要采用一些方法減少廣播帶來的資源消耗。定義一個變量SPP（single-hop packet progress）[27]表示中繼節點j相對于它的父節點i對數據產生的距離增益。

其中，Hi為從源節點s到當前節點i經過的跳數。時延感知的跨層優化分2個步驟實施，包括滿足時延約束的路徑選擇算法和聯合優化速率分配及功率控制的算法。路徑選擇算法描述如算法1所示。

算法1 路徑選擇算法

1) //初始化

2) 在中繼節點i處：

3) if 節點i第一次接收到請求分組

5) ifs pij＞0

6) 把節點 j加入Ai中;

7) end if

8) end for

9) end if

10) 基于式(8)和式(33)計算CTsi和Ui；

11) ifUi>then

13) else

14) 丟棄數據分組；

15) end if

16) ifC Tsi< C Tthen

17) C T←CTsi,ch++;

18) end if

19) 節點i把數據分組廣播給Ai中的每一個節點

20) end if

21) 目的節點GB處:

22) GB選擇具有最大UGB的路徑轉發數據分組并向源節點返回一個回復數據分組

算法1的具體執行過程和參數描述如下。

網絡初始化階段，每個節點i向鄰居廣播一個HELLO分組。當鄰居節點j接收到來自節點i的HELLO分組時返回一個包含自身的識別符和坐標等信息的應答分組，然后節點i從收到的應答分組中提取出j的信息保存到中。如果節點i接收到了來自節點s的路徑請求分組，它根據式(8)和式(33)分別計算CTsi和 Ui，如果 Ui大于i當前保存的值，那么用 Ui替換這個值并把傳輸節點記錄到路由表中，否則丟棄這個數據分組。如果CTsi小于分組頭部中已存在的CT，那么用當前的 CTsi替換這個值，同時分組頭部的傳輸跳數ch值加1。然后i把路徑請求分組廣播給Ai中的每一個節點直到請求分組到達GB。當GB收到一個路徑請求信息后，從請求分組中提取出 C Tmin和 HGB，利用式(33)計算總的路徑效用UGB，如果UGB大于當前保存的值，那么用它替換這個值并把傳輸節點記錄到路由表中，否則，GB丟棄這個請求分組。

到達路徑請求的終止時間后，GB發送一個回復消息給路由表記錄的節點，每個中繼節從回復包中提取并保存 CTmin，重復這個過程直到回復消息到達源節點。

通過以上的路徑建立過程，每個被選擇的節點都保存下一跳節點的信息和路徑的最小持續時間CTmin，基于這些信息可以進行下一步優化操作。利用分布式優化的思想，在每一個中繼節點i處執行算法2。

算法2 異步分布式跨層優化（ADCO）

1) 在中繼節點i和它的中繼節點j處：

2) 初始化參數λij(0)、μij(0)并從路由表中獲得中繼節點j;

3) 基于式(3)計算鏈路容量;

4) if當前總的時延t

7) 基于式(30)和式(31)更新對偶變量λij和μij;

8) else

10)然后利用當前的λij和μij更新對偶變量；

11) end if

12) end if

13)節點i基于式(4)、式(5)、式(28)和式(29)計算和；

14)節點i發送數據分組給算法1選擇出的中繼節點j

15) ift+1＞CTmin

16)調用算法1；

17) end if

算法 2不要求每一個節點擁有全局的優化信息，每個中繼節點僅利用接收到的鄰居信息來完成優化操作。為了更清楚地理解算法 2，其執行過程描述如下。

初始化對偶向量λ(0)和μ(0)，同時給定由算法1得到的中繼節點集合。中繼節點i在t≤CTmin時刻接收到數據分組，首先判斷在當前時刻數據分組是否超時。如果數據分組總的傳輸時延超過了給定閾值，節點i丟棄接收到的數據分組。否則節點i從數據分組頭部提取出其中，p為由算法1選擇的路徑，同時根據數據分組經過的跳數，計算剩余跳數Hr。如果（參考推論 1的結果），則表明前面的鏈路質量較好，節點i使用當前的μij更新對偶變量，否則，把保存的μij替換為并用此參數更新對偶變量。節點i根據自身存儲的局部對偶變量λij(t)和μij(t)，利用式(4)、式(5)、式(28)和式(29)得到當前的傳輸速率rij(t)和功率pi(t)，并分別計算它們的均值和。如果t+1＞CTmin，節點i從緩存表中清空路由表和對偶變量，返回到算法1。否則，節點i根據式(30)和式(31)更新2個對偶變量，并保存到緩存中。節點i使用和把數據分組傳遞給下一跳節點j，重復步驟2)直到數據分組到達GB。如果部分中繼節點在時延閾值?內沒有接收到數據分組，它們將使用之前存儲的相關參數更新對偶變量。直到GB接收到數據分組本次傳輸任務結束。

接下來，分析算法2的時間復雜度，由于算法2是分布式實施的，因此，可以先分析每個節點i處的時間復雜度。在步驟3)中為每個鄰居節點計算鏈路容量，可以在單位時間內完成，所以這個過程的時間復雜度最大為O(Nmax)。因為步驟3)、步驟5)、步驟8)為判斷條件，可以在單位時間內完成，時間復雜度為O(1)，而計算剩余時延與更新原始和對偶變量操作也可以在單位時間內完成，所以步驟 3)～步驟11)總的時間復雜度為O(1)。計算和判斷操作可以在單位時間內完成，同時單跳傳輸操作也可以在單位時間內完成，所以步驟 12)～步驟 16)的時間復雜度為O(1)。在節點i處總的時間復雜度為最壞情況下的時間復雜度為對于整個網絡來說，總的時間復雜度為。結合以上對2個算法時間復雜度的分析可知，整個運行過程的時間復雜度為

5 仿真實驗

下面，利用OMNeT++5.0仿真平臺對 ADCO的性能進行仿真評估。ADCO主要考慮排隊時延和傳輸時延，而由MAC層競爭產生的時延在實驗中被忽略，并利用slotted-ALOHA協議實現MAC層的功能。假設所有的UAV均勻分布在1 000 m×1 000 m的區域內，地面基站固定在（700 m,700 m）的位置。所有UAV有相同的傳輸半徑250 m，當有數據分組傳輸時，UAV根據優化得到的傳輸速率和功率層發送數據，而所要優化的功率值從區間[0.37 W,0.66 W]中選擇。網絡中數據流的產生服從參數為 25的泊松分布，每一個數據分組的最大時延為10跳，假設每個UAV上都安裝有GPS，同時，所有UAV都擁有基站的位置信息。對偶向量λ(0)初始化為每條鏈路的排隊時延，如果在路由發現階段建立的路徑跳數為H，那么在每一個中繼節點處另外，2個步長因子的值分別設置為ε=0.01和ξ=0.01，權重因子ω1=0.3和ω2=0.7。為了使實驗結果更加準確，針對每一個網絡參數，根據5次不同的運行結果求平均得到最后的值，同時假設每個中繼節點對同一個數據分組最多重傳2次。

ADCO與文獻[9]中的RARP（robust and reliable predictive）路由協議和文獻[15]中提出的平均端到端時延約束的動態速率分配方法（DA-DNUM）進行比較。RARP是為 FANET提出的三維路由協議，主要考慮連通時間和端到端跳數，而DA-DNUM不考慮路由的問題。在RARP中節點的傳輸速率為12 Mbit/s，傳輸功率為0.45 W，其他參數的設置和以上提到的一樣。實驗結果主要包含超時率、分組丟失率、吞吐量和能量消耗4個參數，同時根據不同的移動速率和節點數量把這些結果分為2部分。圖2～圖5主要表示在不同移動速率下4個網絡參數在3種方法中的對比結果，圖6～圖9是在不同節點數量下3種方法的對比結果。

圖 2表示隨著移動速率的增加，3種方法的數據分組超時率也隨著增加。ADCO考慮端到端時延約束，每一個中繼節點在傳輸數據分組之前都要根據式(5)評估與鄰居之間的時延。因為DA-DNUM允許數據分組的時延在一定范圍內大于閾值，而在本文中這些數據分組將會被中繼節點丟棄，所以在嚴格要求端到端時延條件下本文提出的方法比DA-DNUM的分組超時率小。為了得到優化問題的最優解，中繼節點選擇能夠滿足當前時延約束的鄰居作為下一跳節點，RARP不考慮端到端時延約束的問題，它所選擇的中繼節點有可能消耗更多的時間傳輸數據分組。由于在每一個中繼節點處考慮時延約束，所以ADCO、DA-DNUM與RARP相比具有更小的超時率，如圖2所示。移動速率的增加使鏈路具有更短的連通時間，2個節點之間的傳輸可能會因為它們移出彼此的通信范圍而失敗，從而消耗更多的時延，所以在3種方法中超時率隨著移動速率的增加而逐漸增加。

圖2 不同移動速率下3種路由方法的分組超時率

總的分組丟失率包含超時率和在中繼節點處超過重傳次數導致的分組丟失率，在ADCO中每一個中繼節點根據式(4)評估與鄰居之間的鏈路質量，同時鏈路質量作為一個參數在目標函數中被優化。式(28)得到的最優傳輸速率也暗示著當前最好的鏈路質量，而RARP使用固定傳輸速率可能會導致較差的鏈路質量。因此，DA-DNUM和RARP比ADCO在中繼節點處會花費更多的傳輸次數，而更多的傳輸次數可能會帶來更大的分組丟失率。DA-DNUM沒有考慮鏈路質量問題，單純的優化傳輸速率并不能保證傳輸的可靠性，所以 DA-DNUM的總分組丟失率比 ADCO中的大。如圖3所示，ADCO比DA-DNUM和RARP具有更低的總丟失率。一般來說，總的丟失率越小表示被目的節點接收到的數據分組越多，也代表網絡的吞吐量越大，所以圖 4說明 ADCO比DA-DNUM和RARP具有更高的吞吐量。

圖3 不同移動速率下3種路由方法的總分組丟失率

為了減少信號之間的干擾，提高端到端傳輸的可靠性，ADCO要求每個中繼節點根據式(29)計算當前的最優功率層，得到的當前最優功率不僅可以減少信號之間的干擾，同時也提高了鏈路質量，使中繼節點可以用較少的重傳次數完成端到端傳輸。而DA-DNUM和RARP使用固定的功率層，在數據流較多的情況中將會導致較差的鏈路質量。在每一個中繼節點處更多的重傳表示更多的能量消耗，所以 ADCO傳輸單個數據分組所消耗的能量比DA-DNUM和RARP少，如圖5所示。

圖4 不同移動速率下3種路由方法的平均吞吐量

圖5 不同移動速率下3種路由方法中的能量消耗

當節點的移動速率設置為15 m/s時，運行3種不同的方法可以得到圖6～圖9的結果。從圖6可以看出，當網絡中節點的數量增加時，3種方法的超時率呈下降趨勢。因為考慮端到端時延約束，總節點數量越少中繼節點所能選擇的下一跳節點也越少。在鏈路質量較差的情況下，中繼節點可能要花費更多的時延完成一跳傳輸，這增加了數據分組超時的概率。當網絡中的節點數量較多時，每一個中繼節點可以選擇更好鏈路質量的鄰居傳輸數據分組。另一方面，較大的節點密度意味著更長的連通時間，因過多重傳次數導致數據分組丟失的概率較小，所以隨著節點數量增加，3種方法中的總丟失率減少。由于ADCO考慮端到端時延和鏈路質量，因此，它與 RARP和僅考慮端到端時延的DA-DNUM相比具有較低的總分組丟失率，如圖7所示。和前面的分析相同，越低的總分組丟失率表示越高的吞吐量，從圖8中可知，ADCO在不同節點數量下比DA-DNUM和RARP有更高的吞吐量。聯合考慮速率和功率優化不僅提高了網絡吞吐量，同時也減少了信號間的干擾和單跳重傳次數，從圖 9中可以看到，當節點數量不同時，ADCO比DA-DNUM和RARP消耗更少的能量完成端到端傳輸。

圖6 不同節點數量下3種路由方法的分組超時率

圖7 不同節點數量下3種路由方法的總分組丟失率

圖8 不同節點數量下3種路由方法的平均吞吐量

圖9 不同節點數量下3種路由方法的能量消耗

6 結束語

本文提出了一種時延感知的分布式跨層優化方法ADCO，該方法通過把優化過程分為2個步驟

分別解決了實時路由、速率分配和功率控制問題。為了實現分布式的方案，首先把跨層優化問題形式化為一個非凸優化問題，并使用拉格朗日松弛技術把非凸約束消除。然后利用對偶分解方法把一個全局問題分解為2個子問題，通過原始分解方法消除全局耦合的時延約束。考慮到無線鏈路的不可靠性，利用異步更新的思想更新原始和對偶參數，直到算法達到最優解或給定的更新間隔時間。實驗結果表明，ADCO在吞吐量、能量消耗和超時率等方面都有很好的性能。所提方法要求所有節點的可用鄰居集合不能為空，但當 UAV的移動速率很快導致網絡中某些中繼節點不滿足這個條件時，會產生空節點問題[28]，如何在FANET中解決這個問題將會是下一步工作的重點。

參考文獻：

[1]LAV G,RAJ J,GABOR V. Survey of important issues in UAV communication networks[J]. IEEE Communications Surveys & Tutorials,2016,18(2): 1123-1152.

[2]ANIKET D. MANETs as propellant in the growth of the Internet of things [J]. Journal of Computer Engineering,2016,18(5): 1-7.

[3] ?LKER B,OK S,?AMIL T. Flying ad hoc networks (FANET): a survey [J]. Ad Hoc Networks,2013,11(3):1254-1270.

[4]VISHAL S,RAJESH K. Cooperative frameworks and network models for flying ad hoc networks: a survey[J]. Concurrency and Computation:Practice and Experience,2017,DOI: 10.1002/cpe.3931.

[5]ALEJANDRO R,GEORGIOS B. G. Separation principles in wireless networking [J]. IEEE Transactions on Information Theory,2010,56(9):4488-4505.

[6]PENG L,WEI R,JAY A F. Distributed continuous-time optimization:non-uniform gradient gains,finite-time convergence,and convex constraint set [J]. IEEE Transactions on Automatic Control,2017,62(5):2239-2253.

[7]KETAN R,NIKOLAOS G,GEORGIOS B G. Cross-layer designs in coded wireless fading networks with multicast [J]. IEEE/ACM Transactions on Networking,2011,19(5):1276-1289.

[8]STEFANO R,KAROL K,GRéGOIRE H,et al. Dynamic routing for flying ad hoc networks[J]. IEEE Transactions on Vehicular Technology,2016,65(3): 1690-1700.

[9]GANBAYARG,ANISH P S,SANG J Y. Robust and reliable predictive routing strategy for flying ad hoc networks [J]. IEEE Access,2017,5(2017): 643-654.

[10]INES H,NOUREDDINE H. Cross layer optimization of end to end delay in WSN for smart grid communications [C]//International Symposium on Signal,Image,Video and Communications (ISIVC). 2016:217-223.

[11]SHUAI Z,I-HONG H,TIE L ,et al. Joint rate control and scheduling for real-time wireless networks [J]. IEEE Transactions on Wireless Communications,2017,DOI: 10.1109/TWC.2017.2700302.

[12]石雷,韓江洪,石怡,等. 無線多跳網絡下基于干擾管理的高容量跨層優化策略[J]. 通信學報,2014,35(12): 89-97.SHI L,HAN J H,SHI Y,et al. High capacity cross layer optimization strategy for multi-hop wireless network with interference management[J]. Journal on Communications,2014,35(12): 89-97.

[13]JUE Y L,GUO C,ZHI Y W,et al. Distributed subgradient method for multi-agent optimization with quantized communication [J]. Mathematical Methods in the Applied Sciences,2017,40(2017): 1201-1213.

[14]GUO Q Z,RICHARD H. Distributed optimization using the primal-dual method of multipliers [J]. IEEE Transactions on Signal and Information Processing over Networks,2017,DOI: 10.1109/TSIPN.2017.2672403.

[15]HAJIESMAILI M H,TALEBI M S,KHONSARI A. Utility-optimal dynamic rate allocation under average end-to-end delay requirements[C]//54th Annual Conference on Decision and Control (CDC).2015:4842-4847.

[16]NIKOLAOS G,GEORGIOS B G. Residential load control: distributed scheduling and convergence with lost AMI messages [J]. IEEE Transactions on Smart Grid,2012,3(2): 770-786.

[17]NIKOLAOS G,GEORGIOS B G. Asynchronous sub-gradient methods with unbounded delays for communication networks [C]//51st IEEE Conference on Decision and Control,2012: 5870-5875.

[18]IVANO N,GIUSEPPE N. Asynchronous distributed optimization via randomized dual proximal gradient [J]. IEEE Transactions on Automatic Control,2017,62(5): 2095-5875.

[19]MING Y H. A distributed,asynchronous and incremental algorithm for nonconvex optimization: an ADMM approach [J]. Transactions on Control of Network Systems,2017,DOI: 10.1109/TCNS.2017.2657460.

[20]AMRIT S B,KETAN R. Asynchronous incremental stochastic dual descent algorithm for network resource allocation[J]. arXiv preprint,arXiv: 1702.08290,2017.

[21]YI R C,XIANG Y Z,RODNEY A K,et al. Interference prediction in mobile ad hoc networks with a general mobility model [J]. IEEE Transactions on Wireless Communications,2015,14(8): 4277-4290.

[22]TAO L,PING Y F,KHALED B L. Outage probability of energy harvesting relay-aided cooperative networks over rayleigh fading channel[J]. IEEE Transactions on Vehichlar Technology,2016,65(2):972-978.

[23]GAGAN R G,NESS B S. Delay analysis for wireless networks with single hop traffic and general interference constraints [J]. IEEE/ACM Transactions on Networking,2010,18(2): 393-405.

[24]TONG M,FAN W,ZHENG Y,et al. Vasilakos spatial reusability-aware routing in multi-hop wireless networks[J]. IEEE Transactions on Computers,2016,65(1): 244-255.

[25]TYCHOGIORGOS G,LEUNG K K. Optimization-based resource allocation in communication networks[J]. Computer Networks,2014,66(2014): 32-45.

[26]ANDREA S,HADI J R. Primal recovery from consensus-based dual decomposition for distributed convex optimization[J]. Journal of Optimization Theory and Applications,2016,168(1): 172-197.

[27]LONG C,JIAN W N,JIAN N C,et al. QoS aware geographic opportunistic routing in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems,2014,25(7): 1864-1875.

[28]SARAB F A R,MEHMMOOD A A,BRAJENDRA K S,et al. 3D real-time routing protocol with tunable parameters for wireless sensor networks[J]. IEEE Sensors Journal,2016,16(3): 843-853.