文少杰，黃傳河

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

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

1 引言

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

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

2 相關工作

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

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

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

3 網(wǎng)絡模型和問題描述

3.1 網(wǎng)絡模型

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

圖1 FANET模型

3.1.1 干擾中斷概率

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

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

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

3.1.2 排隊時延

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

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

3.1.3 鏈路連通時間

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

3.2 問題描述

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

4 分布式解決方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 路徑選擇算法

1) //初始化

2) 在中繼節(jié)點i處：

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

5) ifs pij＞0

6) 把節(jié)點 j加入Ai中;

7) end if

8) end for

9) end if

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

11) ifUi>then

13) else

14) 丟棄數(shù)據(jù)分組；

15) end if

16) ifC Tsi< C Tthen

17) C T←CTsi,ch++;

18) end if

19) 節(jié)點i把數(shù)據(jù)分組廣播給Ai中的每一個節(jié)點

20) end if

21) 目的節(jié)點GB處:

22) GB選擇具有最大UGB的路徑轉(zhuǎn)發(fā)數(shù)據(jù)分組并向源節(jié)點返回一個回復數(shù)據(jù)分組

算法1的具體執(zhí)行過程和參數(shù)描述如下。

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

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

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

算法2 異步分布式跨層優(yōu)化（ADCO）

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

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

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

4) if當前總的時延t

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

8) else

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

11) end if

12) end if

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

14)節(jié)點i發(fā)送數(shù)據(jù)分組給算法1選擇出的中繼節(jié)點j

15) ift+1＞CTmin

16)調(diào)用算法1；

17) end if

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

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

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

5 仿真實驗

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

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

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

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

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

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

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

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

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

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

圖6 不同節(jié)點數(shù)量下3種路由方法的分組超時率

圖7 不同節(jié)點數(shù)量下3種路由方法的總分組丟失率

圖8 不同節(jié)點數(shù)量下3種路由方法的平均吞吐量

圖9 不同節(jié)點數(shù)量下3種路由方法的能量消耗

6 結(jié)束語

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

分別解決了實時路由、速率分配和功率控制問題。為了實現(xiàn)分布式的方案，首先把跨層優(yōu)化問題形式化為一個非凸優(yōu)化問題，并使用拉格朗日松弛技術(shù)把非凸約束消除。然后利用對偶分解方法把一個全局問題分解為2個子問題，通過原始分解方法消除全局耦合的時延約束?？紤]到無線鏈路的不可靠性，利用異步更新的思想更新原始和對偶參數(shù)，直到算法達到最優(yōu)解或給定的更新間隔時間。實驗結(jié)果表明，ADCO在吞吐量、能量消耗和超時率等方面都有很好的性能。所提方法要求所有節(jié)點的可用鄰居集合不能為空，但當 UAV的移動速率很快導致網(wǎng)絡中某些中繼節(jié)點不滿足這個條件時，會產(chǎn)生空節(jié)點問題[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]石雷,韓江洪,石怡,等. 無線多跳網(wǎng)絡下基于干擾管理的高容量跨層優(yōu)化策略[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.