基于網(wǎng)絡編碼的無線Mesh網(wǎng)絡啟發(fā)式定向調度算法研究

虞 洋

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

0 引言

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

1 算法描述

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

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

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

2 算法實現(xiàn)

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

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

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

3 仿真實驗與結果分析

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

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

圖1 吞吐量的變化

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

圖2 公平性的變化

4 結語

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