基于網絡編碼的無線Mesh網絡啟發式定向調度算法研究

虞 洋

(宿遷學院，江蘇 宿遷 223800)

0 引言

在無線網絡中引入網絡編碼思想的研究成果顯著，因為無線信道本質上具有“多發”特性，其廣播特性使得無線網絡應用網絡編碼具有先天性優勢。利用網絡編碼，無線網絡中各個節點相互配合，使得一個節點發出的信號達到其非目的節點時，不再被當作無用的干擾，反而成為提高傳輸效率的潛在動力。網絡編碼比較傳統的存儲-轉發方式，多了一步編碼譯碼過程。網絡編碼在提高網絡吞吐量、減小傳輸延遲、改善負載均衡、增強網絡魯棒性以及節省節點能耗等多個方面都具有獨特的優勢，可以廣泛應用于無線組織網、網絡安全、應用層內容的分發以及分布式的文件存儲等領域?，F已有楊林等[1-2]、郝建軍等[3]、劉晗[4]、湯恒勝等[5]從不同角度對網絡編碼研究。本文運用結合定向天線技術的網絡編碼對多接口多信道無線Mesh網絡公平性優化進行了研究，對網絡公平性問題進行了建模，并在此基礎上提出了鏈路調度與信道分配算法D-LSCA。仿真實驗表明，通過與已有算法進行對比，D-LSCA算法表現出的網絡性能更優。

1 算法描述

假設k(a)是會話a的預設的流權重，a∈A，k(a)越大，會話a所需的流速率越高。假設λ是比例因子，優化的目標為尋求最大化λ使得會話a的λk(a)比例的吞吐量得到公平的調度。考慮公平約束、定向天線約束、鏈路流量約束、數據流保護約束、傳輸干擾約束、鏈路容量約束，最終形成線性規劃模型Max Fairness LP。

假設節點的每一個定向天線都能夠在一定時隙Ts內分配個固定信道，同時，每隔Ts時隙進行一次信道狀態的更新。定義π(e)為鏈路e的調度，調度π(e)包括鏈路e在時隙t與信道m上，傳輸那種類型的數據流b。那么，π(e)可以看作是一個三元組(t,m,b)，其中，t表示不同的時隙，m，m∈M表示信道，b表示數據流類型，b=0代表單播數據流，b=1代表編碼數據流。由于最優信道分配是一個NP-hard問題，因此，通過求解Max Fairness LP，進一步提出一個啟發式算法對進行鏈路調度與信道分配。

所提的算法目的是尋求一組近似的可行解以優化網絡吞吐量。該鏈路調度與信道分配算法的關鍵在于用盡量少的時隙完成數據流對信道的分配。信道每Ts時隙更新一次，因此，每個Ts時隙，該算法都將被執行一次。Max Fairness LP已經對單播流與編碼流的分配給出了解，不需要在對每一個信道上的流進行分配，而是簡單地將網絡內所有單播流看作一條單播流，即：fU(e)=∑m∈MfmU(e)，類似地，也將所有信道上的編碼流看作是一條編碼流，即：fNC(e)=∑m∈MfmNC(e)。

2 算法實現

在每個調度時隙Ts內，先對編碼流進行調度，再對普通單播流進行調度。在對編碼流進行調度時，首先，對未分配的編碼流進行降序排列；其次，將第一條編碼流分配給能夠提供最大流速率的信道。假如信道m空閑，并且鏈路兩端節點在定向天線的傳輸范圍內，調度成功。網絡內的節點通過發送HELLO消息通知鄰居節點自身的定向天線角度信息，接收HELLO信息的節點通過更新自身天線緩存表保存一跳鄰居節點的天線信息，并更新定向天線指標函數數值。當所有該編碼流完成信道的分配，算法將所有與編碼鏈路ENC的鏈路設為0，以保證編碼鏈路不會重復分配，同時，節點的天線個數也要減1。

D-LSCA通過上述循環直到所有的編碼鏈路得到分配后，算法開始對單播流進行分配，分配方法與編碼流分配方法相似。當網絡內所有數據流都得到分配，算法調度時隙增加，進入下一個調度周期。

Max Fairness LP規劃的解已經包含了每一個會話的路由信息，因此，鏈路調度與信道分配算法的最后輸出即為鏈路調度、信道分配與路由的聯合算法，通過該算法，能夠獲得每一次會話的最優吞吐量的近似解。

3 仿真實驗與結果分析

本文將D-LSCA與已有的路由算法進行性能比較。為了更好地分析網絡編碼、定向天線帶來的策略優勢，仿真結果與SP-omni，COPE，DDSR這3種算法進行比較。本文的網絡拓撲結構選擇經典的32節點的隨機網絡。每個節點的天線數量固定為4，會話數固定為50。

實驗1：考察四種算法的吞吐量指標。仿真結果如圖1所示。從仿真結果可以發現，隨著可用信道數量的增加，每一種算法的網絡吞吐量也隨之增加，其變化趨勢基本一致。4種算法中，D-LSCA與COPE對吞吐量的提升效果接近，D-LSCA略優于COPE，其次是DDSR，效果最差的為SP-omni。

圖1 吞吐量的變化

實驗2：考察4種算法的公平性指標。仿真結果如圖2所示。從仿真結果可以發現， D-LSCA在公平性方面明顯優于其他3種算法。SP-omni完全沒有對公平性的考慮，顯然會導致網絡不平衡問題。COPE性能的下降。DDSR優于前面兩種算法，但仍劣于D-LSCA算法。雖然兩種算法都運用了定向天線機制，但D-LSCA通過規劃求解考慮了網絡公平性問題，因此，能夠為無線Mesh網絡提供更好的公平機制。

圖2 公平性的變化

4 結語

本文研究了定向天線技術、網絡編碼技術對多接口多信道無線Mesh網絡公平性問題的影響。通過求解線性規劃初步獲得了編碼流與普通單播流組合，并在此基礎上進一步提出了鏈路調度與信道分配算法D-LSCA。通過與SP-omni，COPE，DDSR算法進行仿真對比實驗，結果表明，D-LSCA算法在網絡吞吐量以及公平性問題上優于對比算法，優化效果明顯。