無線多跳網絡中基于限期約束的報文轉發策略研究

劉猛

無線多跳網絡中基于限期約束的報文轉發策略研究

劉猛

針對有損及存在突發鏈路的無線多跳網絡中的實時報文轉發問題進行了研究，目標是盡量提高各報文在限期前到達目的地的概率。假設信道實時狀態無法獲得，但可以利用真實報文傳輸的成功率和失敗率做出估計，將報文轉發問題看成是一個部分可觀測馬爾科夫決策過程，并獲得了可以實現在線報文轉發概率最大化的最優轉發策略。另外，為了降低實現復雜度，文中還通過利用最大體積內切橢球獲得了近似解。仿真實驗也驗證了本文方案的有效性。

無線多跳網絡；報文轉發；限期；馬爾科夫鏈；最優轉發策略；最大體積內切橢球

0 引言

機器與機器通信是近幾年的研究熱點[1,2]。然而，很少有文獻對滿足實時監控等機器與機器應用的QoS要求所必需的基礎技術進行研究。其中一項關鍵要求就是如何在苛刻的報文期限前轉發報文[3]。例如，在智能電網中，只有及時接收到包含電壓、功率和頻率的測量數據（在限期前）才能對生產方和消費方進行協調、檢測異常及保證電網穩定性。已有文獻量化證明[4]，端到端數據流中報文滿足傳輸限期的概率，對閉環控制系統的性能具有重要影響。

部分文獻對非可靠性網絡中嚴格限期條件下的通信問題進行了研究。比如，文獻[5,6]中研究了“適時吞吐量”問題。文獻[7]構建了面向可重構路由器的報文轉發引擎構件重構模型，并基于Pass-Through模式設計實現了可重構FPGA器件與網絡處理器相結合的程序／電路構件運行環境。仿真結果表明，可重構路由器報文轉發引擎在保證高吞吐率、低延遲的報文轉發處理性能的同時，可有效支撐多樣化業務構件靈活重構與映射。文獻[8]采用狀態有限馬爾科夫鏈信道模型，研究了限期約束條件下的最大可靠性數據轉發問題。文獻[9]研究了限期約束條件下的最小能量數據轉發問題。然而它們均假設，系統運行時各個節點上的調度器可以充分訪問其出向鏈路上的信道狀態（比如通過運行專門的鏈路估計器獲得）。本文將文獻[8,9]的工作擴展到調度器無法訪問到出向鏈路的信道狀態這一情景下。此時，只能通過鏈路上的數據傳輸來觀察鏈路的信道狀態。通過觀察突發鏈路上的內存，可以預測信道的未來狀態。文中給出了在這些有限信道狀態信息下可以實現在線報文轉發概率最大化的最優數據轉發策略。同時，給出一種新的計算量較低的近似求解方法，最后通過仿真實驗驗證了本文方案的有效性。

1 模型和相關假設

本文主要研究非可靠性多跳無線網絡上的通信問題。報文通過有向圖(N,L)轉發，其中節點集合N={1,2,...,N}表示收發兩用機，鏈路(i,j)∈L表示節點i可向節點j發送報文。目的節點表示為N，且節點集合N中的節點均可到達。Ni定義為節點i可向其發送報文的節點集合，Ni表示節點i的出向鏈路數量。

通過對過程進行時隙處理，每個時隙允許傳輸一個報文及其相應的確認。通信鏈路的可靠性較低，鏈路上的報文丟失事件可模擬為狀態有限馬爾科夫鏈。不同鏈路的馬爾科夫鏈相互獨立，且節點無法直接訪問馬爾科夫鏈的狀態。然而，節點通過在其出向鏈路上傳輸數據報文并記錄相應結果，就可觀察到其任意一條出向鏈路的狀態。每個馬爾科夫鏈在離散時間內演化，且狀態變化與時隙邊界一致。設s∈S表示鏈路的馬爾科夫狀態，S表示所有可能狀態的集合。設表示節點i所所有出向鏈路(i,j)的狀態，且當信道狀態為s時wij=s。在狀態為wij的鏈路(i,j)上傳輸報文，則報文成功傳輸的概率為qwij，失敗概率為pwij=1-qwij。

假設在某一場景下，在時間t=0時只產生一個報文，需要在時間t=DD前傳輸到目的節點N。本文的目的是確定一種轉發策略，使得在限期N前成功轉發報文的概率最大。本文還研究了所有鏈路損失過程描述為雙態Gilbert-Elliott (GEE)模型時的最優轉發策略。這些模型包含“理想”(G)狀態和“非理想”(BB)狀態，如圖1所示：

圖1 鏈路報文損失的雙態Gilbert-Elliot (GEE)模型

如果鏈路的狀態較好，則設置wij=GG，否則設置wij=B 。理想狀態下的成功概率為1，非理想狀態下的成功概率為0。因此，如果已經觀察到前一時間的狀態為理想狀態，則當前時隙的成功傳輸概率為qG，如果觀察到的狀態為非理想狀態，則成功概率為qB。于是，平均成功概率為（理想狀態的靜態分布）：。此外，用TB表示非理想狀態的平均突發長度（時隙數量），即TB=1/qB。

2 問題定義及其最優解

2.1 限期約束條件下進行數據轉發的POMDP問題定義

文獻[9]將多跳網絡限期約束條件下的報文轉發問題看成是有窮界限馬爾科夫決策過程（MDP）。系統狀態包括報文位置和網絡中所有鏈路的信道狀態。通過為限期前成功傳輸到目的地的報文分配一定獎勵，平均獎勵則等于限期約束條件下的報文轉發可靠性。

因為，節點只能訪問網絡中鏈路的部分信道狀態（自己的出向鏈路狀態），所以這也是部分可觀察馬爾科夫決策過程（POMDP）。此外，本文假設通過在網絡中進行真實的數據傳輸即可獲得鏈路的信道狀態。數據傳輸之后，可以根據鏈路的馬爾科夫鏈模型估計將來信道狀態的概率分布。GEE模型處于理想狀態時的概率更新示例如圖2所示：

圖2 GE模型的理想狀態概率更新。平均理想狀態概率為0.5，時間為0時只能觀察到理想狀態(G)或非理想狀態(B)。

文獻[10]已經證明，置信狀態（即系統狀態的概率分布）是PPOMDP問題的充分統計量，且最優轉發策略是置信狀態到行為的一個映射。具體來說，節點需要維護其出向鏈路信道狀態的概率分布。其他鏈路的置信度是一致的，且等于平均信道狀態分布，因為，該節點無法訪問其他鏈路的信道狀態。這一結論可以將POMDP問題化簡為連續狀態空間條件下的等效MDP問題。因此，可以相應確定價值函數和Bellman等式。

假設價值函數（即限期約束條件下的最大轉發可靠性）為Ri(t,b)，其中t表示當前時間，表示節點i在先前時隙期間出向鏈路的所有可能信道狀態的置信度。本文隱含地假設節點i其他鏈路的置信度處于其平均狀態。向量b的長度為（因此，當用GE模型描述鏈路損失時，b的長度為于是對所有節點i有

其中wi表示先前時隙t-1的信道狀態；表示當前時隙t的信道狀態；Rj(tt+1)表示平均信道狀態分布條件下節點j在時間t+1時的最大可靠性；表示觀察到信道狀態時的新的置信度。使用平均信道狀態分布的可靠性RRj(t+1)，是因為節點i無法訪問節點j的出向鏈路狀態。可由鏈路的馬爾科夫鏈模型計算出來。最后，價值函數可計算為公式（2）：

本文的目標是計算報文由源節點在時間0生成時的價值函數RRsrc(0,b)。

2.2 最大可靠性和最優策略

因為，系統狀態是連續的，所以，無法使用標準的離散時間動態規劃求解公式（2）。然而，有窮界限POMMDP問題的價值函數是置信狀態上的分段線性凸函數(PWLLC)[10]，即Ri(t,b)可寫為公式（3）：

其中集合Γi,t在每次更新時計算。通過展開BBellman更新即可證明PWLC屬性。當初始條件為RN(t,b)=1,?t,b和Ri(D,b)=0,?b,i≠NN 時，對時間tt=D-1到t==0期間的每個節點運用更新。為了更詳細地確定更新和最優策略，考慮隨機節點i。對時間t=D,D-1,...,D-hi-1，可靠性均為0，其中hi表示與目的地之間的最小跳數距離。t=D-hi，則有公式（4）：

Rj(D-hi+1)在前一步驟t=D-hi+1中節點j計算得到，且Ri(D--hi+1,b)=0,?bb 。因此，對t=D-hi，價值函數具有如下PPWLC屬性：

下文通過歸納法來證明當PWLCC屬性在時間t+1成立時，在時間t也成立。設表示新的信道狀態置信度，使用貝葉斯規則來計算新的信道狀態的置信度。如公式（5）：

其中，如果新的信道狀態w?i與鏈路(i,j)的wwi'j相等，則1{wi'jw?i}=1，否則為0。因此，得公式（6）：

上式利用了如下歸納假設：Ri==(t+1,b')是置信狀態b'上的PPWLC函數。將這些表達式代入式（1），有：

將其進一步化簡為公式（7）：

因此，限期約束條件下的最大可靠性為公式（8）：

該式表示置信度為b時的PWLCC屬性。每個α向量關聯一個行為，通過確定最大化時的α向量即可求得最優行為。可以發現，當界限長度增加時，α向量數量呈指數增長。請注意，每個節點i的行為數量為，信道可能狀態數量為。因此，。對第2節描述的GE模型，向節點j傳輸數據時的最大轉發可靠性為公式（9）：

GE模型有兩個信道狀態，但是，理想狀態下的損耗概率為0。這表明，，遠小于通用馬爾科夫鏈路模型。在下文中，只研究雙態GE模型。然而，所得結果可直接擴展至通用型有限狀態馬爾科夫鏈模型如圖3所示：

圖3 LLP修剪示例。虛線被修剪，因為它在任何置信度下均沒有獲得最優值。

2.3 基于線性規劃的修剪處理

每次Belllman更新時，α向量數量均會上升，且定義最終價值函數的線性函數數量可能會很大。然而，在價值函數的PWLC表示中，可能存在部分向量α∈Γi,t對所有置信度均非最優。修剪這些冗余向量，以節約后續更新時的計算開銷。

基本的修剪方法就是通過線性規劃((LP)來確定α向量是否有用，如果冗余則將其刪除。對Γi,t中的所有α向量運行這一步驟。向量αm的線性規劃具體內容如公式（10）：

最大化：δ條件：αmm·b-α·b≥δ,?α∈Γi,t{αm}, （10）

該線性規劃可確定向量αm相比于其他所有向量，可為價值函數貢獻的最大額外價值。如果線性規劃返回δ≤0，則向量δ≤0受其他向量主導，應被修剪。例如，圖3中虛線的最大額外價值為負，證明它受其他線性函數主導，可以被修剪。

3 最大體積橢球修剪近似解

在運行期間，每個節點運行的數據轉發算法通過計算當前置信度和每個α向量間的內積來尋找該時隙期間的最優行為，如公式（3）所示。考慮到機器與機器應用場景中的硬件平臺往往為資源有限平臺，如果α向量數量較大，則難以在這些平臺上存儲并計算這些最優行為。本節提出一種近似求解方法，在降低部署復雜性的同時（降低了α向量的數量），又維持了優異性能如圖4所示：

圖4 向量為α1且體積較大時的MVE修剪示例。

粗垂直線表示α1和α2的額外價值（即線性規劃時的δ）。這些價值比較接近，但是本文更傾向于α1，因為它的置信度活躍區間更大。

2.3節的修剪策略保存了貢獻值為正δ的α向量。一種直觀的近似求解方法是根據其δ值對α向量排序，將貢獻較小的向量去除。然而，線性規劃方法沒有返回α向量居于主導地位的置信范圍。例如，在圖4中，向量α1和α2的δ貢獻值比較接近，但是α1的活躍范圍更大。本文提出根據向量居于主導地位的區域的最大體積內切橢球(MVE)尺寸來對向量排序。橢球的體積可高效計算出來，作為α向量居于主導地位的區域的真實體積（該體積難以計算）。在圖44中，必要情況下，α2的橢球較小因此可被首先修剪。

對向量αm∈Γi,t，其居于主導地位的區域是維線性空間的多面體Pm。設表示該空間中的一個點，且b表示信道狀態的置信度，r表示轉發可靠性。定義且ek作為第k個元素為1、其余元素均為0的向量。多面體Pm可描述為：

該式可寫為如下一組線性不等式：

根據文獻[11]]可知，尋找最大體積內切橢球是個凸優化問題：

最大化logdetB

其中B表示描述橢球的對稱矩陣，橢球的體積與數學行列式B成正比。為了求解該問題，下面給出了一種簡單的啟發式算法。該算法首先通過線性規劃修剪掉冗余向量，然后迭代修剪掉體積最小的α向量，直到所有α向量相對于最大體積的體積大于閾值為止如算法1：

算法1：閾值為ξ的MVE修剪

RRN(t)=1?t∈[0,D];Ri(D))=0?i≠N

FFor t=D-1到0 do

For 所有i∈NN及i≠N doo

利用式（8）計算α向量

使用式（10）及線性規劃修剪掉冗余的α向量

計算每個α向量的MVE體積det(B)

Whilemmin(det(B))/max(det(B)))≤ξ do

刪除體積最小的α向量

計算每個α向量的MMVE體積det(BB)

End whilee

計算平均置信度為Ri(t)的可靠性

End for

EEnd for

4 仿真實驗

我們通過MATLAAB仿真和簡單網絡證明本文方法的有效性，如圖5所示：

圖5 網絡拓撲示例

在本節中，統一用節點1表示源節點，節點16表示目的節點。鏈路上的報文消除服從GEE模型，所有鏈路的模型參數相同，平均成功概率為πG=0.5。

圖5首先比較了本文所研究的在信道狀態信息有限條件下，帶有限期約束時的最大可靠性，此時前一時隙所有出向鏈路的信道狀態已知。當報文注入網絡時，假設無先驗傳輸歷史信息，因此，使用平均信道狀態置信度進行報文轉發。只知道有限信道狀態信息時的限期約束可靠性始終低于知道完全的信道狀態信息時如圖6所示：

圖6 完全信道狀態信息和最小平均延時路徑兩種情況下的限期約束可靠性比較。

如果鏈路的突發性較弱且TB=22.5，則知道完全狀態信息的效果將會下降。原因是此時成功傳輸概率基本與前一時隙的鏈路狀態無關。

在圖6中比較了信道狀態信息有限時限期約束條件下的最大可靠性與平均最小延時條件下的可靠性。因為，鏈路為同質鏈路，所以，網絡中的任意三跳路徑均是最小平均延時路徑。圖6表明，除非限期時間為3，否則最小平均延時路徑的性能始終低于有限價信道狀態。此時，限期時間等于最小跳數，在當前報文的轉發決策中無法使用獲得的信道狀態。

限期約束條件下的最大可靠性取決于信道狀態知識。如果報文注入網絡的頻率加劇，則能獲得更多的信道狀態最新信息，進而提升端到端可靠性。3種不同注入率條件下的最大可靠性如圖7所示：

圖7 報文注入速率對限期約束最大可靠性的影響。注入率越高，可靠性越高。

當采用高速和中速注入率時，分別在每一個限期周期和兩個限期周期內注入報文。從圖7中可以看到，注入率越高，可靠性越高。然而，當限期變長時，3種情景下的差異消失。原因是此時鏈路的信道狀態置信度與下一報文注入前的均值比較接近。

最后，算法1中閾值ξ取不同值時，進行MVVE修剪的近似求解方法的限期約束最大可靠性如圖8所示：

圖8 平均信道狀態置信度條件下的限期約束可靠性：MVVE修剪策略近似解

最優轉發策略和MMVE修剪轉發策略每個節點的α向量平均數量，如表1所示：

表1 MMVE修剪取不同ξ閾值時，每個節點的α向量平均數量

此時限期時間為10。結果表明，ξ較大時，被修剪的α向量較多，可靠性較低。當ξ=1時，每個節點每個時間只有一個α向量，但是可靠性仍然遠高于最小平均延時路徑。此外，當ξ=1e-5時，MVE修剪策略雖然只使用一半的α向量，但性能只有輕微下降。

5 總結

本文研究了多跳無線有損網絡限期約束條件下的報文轉發可靠性最大化問題。將鏈路上的報文丟失模擬為狀態有限馬爾科夫鏈，只有通過在鏈路上傳輸報文才能獲得鏈路的狀態。將該問題闡述為部分可觀察的馬爾科夫決策過程，并獲得了最優策略。引入一種新的基于最小體積內切橢球的修剪方法，以便在性能和部署復雜度間進行折衷。討論了最大可靠性和最優策略的結構屬性。下一步研究包括如下幾個方面。首先，可以研究另一種模型，允許節點通過消耗一定能量明確地查詢信道來獲得鏈路狀態。POMMDP框架可以包括多種查詢方法。其次，在低功耗無線傳感器網絡節點上部署最優策略，然后在測試床實驗中評估其性能。

[1]Lu R, Li X, Liang X,et al. GRS: Thhe green, reliabbility, and secuurity of emerginng machine tomachine commmunications[J]. Communiications Magaazine, IEEE, 22011, 49(4): 288-35.

[2]Fadlullahh Z M, Fouda MM M, Kato N,et al. Toward iintelligent mmachine-to-macchine communnications in ssmart grid[J].Communicationns Magazine,IEEE, 2011, 449(4): 60-65.

[3]簡鑫, 曾孝平, 賈云健, 等. 機器類通信流量建模與過載控制[JJ]. 通信學報, 22013, 34(9): 1223-131.

[4]DemirelB, Zou Z, Solddati P, et al. MModular co-desiggn of controlleers and transmiission schedules in WirelessHHART [C]. Deccision and Conttrol and European Control Coonference (CCDC-ECC), 2011 50th IEEE CConference on. IIEEE, 2011: 59951-5958.

[5]Jaramilloo J J, Srikant RR, Ying L. Schheduling for opttimal rate alloocation in ad hhoc networks wwith heterogenneous delay constraints [J]. Seelected Areas iin Communicattions, IEEE Jouurnal on, 2011,29(5): 979-9877.

[6]Saifullahh A, Xu Y, LuC, et al. Real-time scheduling for WirelesssHART networkks[C]. Real-Timme Systems Symmposium (RTTSS), 2010 IEEEE 31st. IEEE, 22010: 150-159.

[7]陳一驕,盧澤新,孫志剛,等.可重構路由器報文轉發引擎設計與實現[J].通信學報, 2012, 33(8)): 42-51.

[8]Zou Z, SSoldati P, Zhanng H, et al. Energy-efficient ddeadline-consstrained maximmum reliabilityforwarding in llossy networkss [J].WirelessCommunicatioons, IEEE Trannsactions on,2012, 11(10):3474-3483.

[9]Zou Z, Joohansson M. MMinimum-energyy packet forwarrding over lossy networks unnder deadlineand reliabilityconstraints[CC]. Modelingand Optimizattion in Mobile, Ad Hoc andd Wireless Netwworks (WiOpt),2012 10th Inteernational Syymposium on. IEEE, 2012: 2244-231.

[10]Kaelblinng L P, LittmanM L, Cassandraa A R. Planningg and acting inn partially obseervable stochasttic domains [J]. Artificial inntelligence, 19998, 101(1): 99-1134.

[11]Gershmaan A B, Sidiropoulos N D, Shaahbazpanahi S,et al. Convexoptimization-bbased beamformming: From recceive to transmmit and networkk designs [J]. IEEEE Signal Proocess, 2010, 277(3): 62-75.

Research on Packet Forwarding Strategies Based on Deadline Constraints in Wireless Multi-hop Networks

Liu Meng
(Dongguan Science and Technology School, Dongguan 523000, China)

This paper researches on the problem of real-time packet forwarding in wireless multi-hop networks with lossy and bursty links. The objective is to maximize the probability that individual packets reach their destination before a hard deadline. While the instantaneous channel statuses are not accessible, they can be estimated by observations of success and failure rate during the actual packet transmissions. The packet forwarding problem can be regarded as a partial observable Markov decision process and it can also get the optimal transmission strategy for maximizing the probability of on-time packet delivery. In addition, the approximate solution based on maximum-volume inscribed ellipsoids is obtained to reduce the complexity of implementation. The simulation results also show the effectiveness of the proposed scheme.

Wireless Multi-hop Networks; Packet Forwarding; Deadline; Markov Chains; Optimal Forwarding Policy; Maximum-volume Inscribed Ellipsoids

TP393

A

2015.02.09）

1007-757X(2015)04-0027-05

劉猛（1981-），男，邳州人，東莞理工學校，講師，研究方向：網絡安全、信息檢索，東莞，523000