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

虞 洋

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

0 引言

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

1 算法描述

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

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

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

2 算法實(shí)現(xiàn)

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

圖1 吞吐量的變化

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

圖2 公平性的變化

4 結(jié)語(yǔ)

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