采用噴泉碼的無線協(xié)同多跳信息累積廣播協(xié)議

(解放軍理工大學(xué) 通信工程學(xué)院，南京 210007)

1 引 言

在無線網(wǎng)絡(luò)中，廣播作為一種可以將信息從源節(jié)點(diǎn)發(fā)送到多個(gè)目的節(jié)點(diǎn)的傳輸方式，在多跳網(wǎng)絡(luò)通信中起著重要的作用。廣播方案的效率受多種因素影響，如系統(tǒng)的可靠性、能量效率、可擴(kuò)展性、復(fù)雜度和延時(shí)等。針對(duì)不同的場(chǎng)合，不同因素所起的作用也不一樣，如在廣播流媒體時(shí)，延時(shí)是需要重點(diǎn)考慮的因素；當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)要更新軟件時(shí)，傳輸?shù)目煽啃跃惋@得十分重要。

在無線通信系統(tǒng)環(huán)境中，系統(tǒng)中節(jié)點(diǎn)的能量是受限的，因此降低系統(tǒng)的能量消耗顯得十分重要，它已經(jīng)成為廣播協(xié)議的一個(gè)研究熱點(diǎn)。Maric提出利用無線組播優(yōu)勢(shì)，節(jié)點(diǎn)可以接收可靠傳輸范圍以外的信息，并進(jìn)行信息的累積，系統(tǒng)通過獲得分集增益來提高能量效率[1]。Kailas提出了帶有判決門限的機(jī)會(huì)大陣列協(xié)議[2]，通過對(duì)接收信號(hào)信噪比的檢測(cè)，系統(tǒng)只允許在下一次傳輸中發(fā)揮作用較大的節(jié)點(diǎn)進(jìn)行發(fā)送，發(fā)揮作用較小的節(jié)點(diǎn)不發(fā)送。這種算法在節(jié)點(diǎn)密度較高的環(huán)境下適用，當(dāng)密度節(jié)點(diǎn)較低時(shí)系統(tǒng)性能將受影響。

在廣播通信中，一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)，N個(gè)目的節(jié)點(diǎn)接收數(shù)據(jù)。如果有目的節(jié)點(diǎn)沒有成功接收，為保證傳輸?shù)目煽啃?，則發(fā)送節(jié)點(diǎn)需要重新發(fā)送。沒有成功接收的節(jié)點(diǎn)通過反饋告知發(fā)送節(jié)點(diǎn)它需要哪些數(shù)據(jù)，由發(fā)送節(jié)點(diǎn)對(duì)應(yīng)發(fā)送。由于通常這些未成功譯碼目的節(jié)點(diǎn)所需重傳的數(shù)據(jù)是不同的，源節(jié)點(diǎn)向某一個(gè)節(jié)點(diǎn)重傳的數(shù)據(jù)對(duì)于其它節(jié)點(diǎn)來說是沒有用的，這樣就浪費(fèi)了系統(tǒng)資源。噴泉碼的出現(xiàn)很好地解決了這個(gè)問題[3-5]。源節(jié)點(diǎn)的數(shù)據(jù)通過噴泉編碼可以產(chǎn)生遠(yuǎn)大于原信息長(zhǎng)度的編碼信息，它發(fā)送的編碼信息對(duì)于每一個(gè)沒有成功譯碼的接收節(jié)點(diǎn)都是有用的。此外，噴泉碼可以自適應(yīng)信道鏈路狀態(tài)，無需信道狀態(tài)反饋信息就可以達(dá)到信道容量，因此考慮到將噴泉碼引入到廣播傳輸系統(tǒng)中來提高系統(tǒng)的能量效率。

本文提出了采用噴泉碼的信息累積傳輸協(xié)議：接收節(jié)點(diǎn)利用可靠傳輸范圍之外的信息，直至接收節(jié)點(diǎn)積累的信息量可以成功譯碼。根據(jù)節(jié)點(diǎn)是否擁有網(wǎng)絡(luò)的全局鏈路信息，給出了集中式信息累積協(xié)議和分布式信息累積協(xié)議，并將提出的這兩個(gè)協(xié)議與現(xiàn)有的能量累積廣播協(xié)議進(jìn)行了比較。

2 系統(tǒng)模型

在信息累積廣播協(xié)議中，系統(tǒng)所需的最小能量可以通過兩方面來實(shí)現(xiàn)，首先要確定由哪些節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，然后再確定節(jié)點(diǎn)的發(fā)送功率。這個(gè)問題與最小能量廣播問題相似。在最小能量廣播問題中，若廣播樹確定，則發(fā)送功率也就確定了[8-9]。廣播樹中一個(gè)父節(jié)點(diǎn)的發(fā)送功率由到達(dá)它所在組中信道質(zhì)量最差的子節(jié)點(diǎn)決定，但是在信息累積廣播中，節(jié)點(diǎn)從很多其它發(fā)送節(jié)點(diǎn)接收信息，節(jié)點(diǎn)之間沒有明確的父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系。除此以外，節(jié)點(diǎn)的發(fā)送功率的最優(yōu)解可能不是正好使某個(gè)節(jié)點(diǎn)成功接收的功率值，因?yàn)檫@個(gè)接收節(jié)點(diǎn)還可以從將來發(fā)送的節(jié)點(diǎn)接收到所需信息。

信息累積廣播協(xié)議最為關(guān)鍵的步驟是確定發(fā)送節(jié)點(diǎn)的發(fā)送次序，然后根據(jù)這個(gè)發(fā)送次序進(jìn)行線性規(guī)劃，確定節(jié)點(diǎn)的最優(yōu)發(fā)送功率。文獻(xiàn)[1]中指出尋找這樣一個(gè)最優(yōu)次序是不可實(shí)現(xiàn)的，基于此，下面就給出兩種典型場(chǎng)景下的啟發(fā)式算法。

3 集中式信息累積廣播協(xié)議(CIABP)

在CIABP協(xié)議中，假設(shè)所有信道增益系數(shù)的信息在各個(gè)節(jié)點(diǎn)處都是已知的，還要求每一個(gè)成功譯碼節(jié)點(diǎn)的注水速率都是已知的，并且節(jié)點(diǎn)發(fā)送的功率可以確定，恰好使一個(gè)未成功譯碼節(jié)點(diǎn)在一個(gè)時(shí)隙內(nèi)成功接收。網(wǎng)絡(luò)中成功譯碼的節(jié)點(diǎn)集合記為S，如果節(jié)點(diǎn)j是在S之外的下一個(gè)要成功接收的節(jié)點(diǎn)，則S中的節(jié)點(diǎn)發(fā)送的功率應(yīng)使j成功接收。如果說要使j成功接收所發(fā)送的功率使得節(jié)點(diǎn)i先于節(jié)點(diǎn)j成功接收，則應(yīng)安排節(jié)點(diǎn)i作為下一個(gè)接收節(jié)點(diǎn)。這是因?yàn)楣?jié)點(diǎn)j的發(fā)送不能使節(jié)點(diǎn)i獲得信息，而節(jié)點(diǎn)i發(fā)送可能會(huì)使節(jié)點(diǎn)j獲得信息。

算法代碼如下：

S=[1];p=0

while(S

k=argmaxi∈S∑j∈Uhj,i;

S←[S,j]

end

假定源節(jié)點(diǎn)為1，未成功譯碼的節(jié)點(diǎn)集合為U，任一節(jié)點(diǎn)k的注水速率定義為節(jié)點(diǎn)k到所有未成功譯碼節(jié)點(diǎn)的信道增益系數(shù)之和：

(1)

則CIABP協(xié)議的貪婪注水算法描述如下：

(1)找出成功譯碼節(jié)點(diǎn)中注水速率最大的節(jié)點(diǎn)k；

(2)確定節(jié)點(diǎn)k的發(fā)送功率，使得某一個(gè)節(jié)點(diǎn)j在下一個(gè)時(shí)隙可以成功譯碼；

(3)將節(jié)點(diǎn)j加到成功譯碼的節(jié)點(diǎn)集合S中去。

將源節(jié)點(diǎn)標(biāo)識(shí)為1，其后續(xù)成功接收節(jié)點(diǎn)依次標(biāo)記為2,3,…， 如果節(jié)點(diǎn)m在其它發(fā)送節(jié)點(diǎn)發(fā)送的基礎(chǔ)上成功譯碼，則發(fā)送速率可表示為

(2)

式中，pk為節(jié)點(diǎn)k的發(fā)送功率，若節(jié)點(diǎn)k沒有進(jìn)行發(fā)送，則pk=0。

現(xiàn)將CIABP與文獻(xiàn)[1]提出的集中式能量累積廣播協(xié)議(CEABP)進(jìn)行比較。系統(tǒng)仿真參數(shù)設(shè)置如下:信道帶寬W為200 kHz，單邊帶功率譜密度N0設(shè)定為5×10-6，要求達(dá)到的通信速率為270.833 kbit/s，仿真次數(shù)為100。從圖1中可以看到，在3種衰落系數(shù)下，CIABP性能都比CEABP好，但是隨著衰落系數(shù)的增加，CIABP相比于CEABP的性能優(yōu)勢(shì)在減小。CIABP和CEABP都隨著節(jié)點(diǎn)數(shù)目的增加，系統(tǒng)需要的總的能量降低，這是因?yàn)楣?jié)點(diǎn)密度增加以后，發(fā)送節(jié)點(diǎn)和未成功譯碼節(jié)點(diǎn)的平均距離降低，未成功譯碼的節(jié)點(diǎn)可以從發(fā)送節(jié)點(diǎn)處接收更多的信息。當(dāng)α=2時(shí)，在N=10時(shí)，CIABP比CEABP能量消耗少1.5 dB；在N=150時(shí)能量消耗少1.9 dB。當(dāng)α=4時(shí)，在N=10時(shí)，CIABP比CEABP能量消耗少1.09 dB；在N=150時(shí)能量消耗少1.13 dB。

圖1 兩種集中式廣播協(xié)議的能量消耗Fig.1 Energy consumed of the two centralized broadcast protocols

4 分布式信息累積廣播協(xié)議(DIABP)

在CIABP協(xié)議中，不僅要求節(jié)點(diǎn)知道所有鏈路增益系數(shù)的信息，還要求每一個(gè)成功譯碼節(jié)點(diǎn)的注水速率都是已知的，并且節(jié)點(diǎn)發(fā)送的功率可以確定，恰好使一個(gè)未成功譯碼節(jié)點(diǎn)在一個(gè)時(shí)隙內(nèi)成功接收。這些條件要求過于苛刻，下面提出一個(gè)只需要局部網(wǎng)絡(luò)信息的分布式廣播協(xié)議。

Si=S∩NR(i)，Ui=U∩NR(i)

(3)

式中，Si代表節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中成功譯碼的節(jié)點(diǎn)的集合，Ui代表節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中未成功譯碼的節(jié)點(diǎn)的集合，S代表成功譯碼的節(jié)點(diǎn)的集合，U代表未成功譯碼的節(jié)點(diǎn)的集合，NR(i)代表節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)。在發(fā)送之初，任一節(jié)點(diǎn)i初始化為Si=?。

(4)

式中，B為發(fā)送信息的長(zhǎng)度，tk為節(jié)點(diǎn)k的發(fā)送時(shí)間。

(2)一旦節(jié)點(diǎn)i成功譯碼，節(jié)點(diǎn)i發(fā)送ACKi，促使節(jié)點(diǎn)i的鄰居中任一未成功譯碼的節(jié)點(diǎn)k接收到ACKi后發(fā)送LGk給節(jié)點(diǎn)i。節(jié)點(diǎn)i接收到所有鏈路增益控制幀LG之后就可以計(jì)算出自己的注水速率，然后將它的注水速率用控制幀F(xiàn)Ri廣播給它的鄰居節(jié)點(diǎn)。在本文中，如果兩個(gè)節(jié)點(diǎn)同為某一個(gè)節(jié)點(diǎn)的鄰居，則認(rèn)為這兩個(gè)節(jié)點(diǎn)可以可靠接收對(duì)方的控制幀F(xiàn)R。

(3)成功譯碼的節(jié)點(diǎn)i收到ACKj后，如果它正在發(fā)送，則停止發(fā)送。節(jié)點(diǎn)i更新Si、Ui和注水速率Ri，并將自己的注水速率用控制幀F(xiàn)Ri廣播給它的鄰居節(jié)點(diǎn)，然后由Si中注水速率最大的節(jié)點(diǎn)進(jìn)行發(fā)送，當(dāng)節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)都成功譯碼時(shí)，這個(gè)過程停止。

在節(jié)點(diǎn)i的發(fā)送過程中，與能量累積協(xié)議中重復(fù)發(fā)送相同的編碼信息不同，節(jié)點(diǎn)i一直在發(fā)送不同的編碼信息，這依賴于噴泉碼可以產(chǎn)生源源不斷的編碼信息的特性。在本算法中，節(jié)點(diǎn)的動(dòng)作都是由ACK幀觸發(fā)的。

圖2對(duì)DIABP協(xié)議與文獻(xiàn)[1]提出的分布式能量累積協(xié)議(DEABP)進(jìn)行了比較，仿真參數(shù)設(shè)置如下：信道帶寬W為200 kHz，單邊帶功率譜密度N0為5×10-6，幀長(zhǎng)B為1.56，仿真次數(shù)為100。為保證網(wǎng)絡(luò)節(jié)點(diǎn)的全連通，根據(jù)文獻(xiàn)[10]，將節(jié)點(diǎn)的可靠發(fā)送范圍設(shè)為r=2.6，節(jié)點(diǎn)的發(fā)送信息功率p=1.56，發(fā)送控制幀的功率pc=1.56。從圖中可以看出，DIABP協(xié)議比DEABP協(xié)議的能量效率要高。更重要的是隨著節(jié)點(diǎn)數(shù)目的增加，DIABP協(xié)議所需的能量逐漸降低，而DEABP則有緩慢上升的趨勢(shì)。這是因?yàn)殡S著節(jié)點(diǎn)間距離的降低，復(fù)用增益產(chǎn)生的作用比分集增益的作用更加明顯。在N=80時(shí)，DIABP比DEABP協(xié)議所需的能量少0.64 dB；在N=300時(shí)，DIABP比DEABP協(xié)議所需的能量少1.56 dB。圖中也給出了CIABP協(xié)議和DIABP協(xié)議的比較，可以看出DIABP相比于CIABP協(xié)議性能還是下降較大。

圖2 兩種分布式廣播協(xié)議的能量消耗Fig.2 Energy consumed of the two distributed broadcast protocols

5 結(jié) 論

本文將噴泉碼引入到協(xié)同多跳廣播傳輸系統(tǒng)中，令成功譯碼中注水速率最大的節(jié)點(diǎn)發(fā)送，接收節(jié)點(diǎn)成功接收后，再由更新后注水速率最大的節(jié)點(diǎn)發(fā)送。接收節(jié)點(diǎn)對(duì)接收到的噴泉編碼信息進(jìn)行累積，直至成功譯碼。針對(duì)不同的應(yīng)用環(huán)境，提出了CIABP和DIABP協(xié)議，并將這兩種協(xié)議與現(xiàn)有的能量累積廣播協(xié)議進(jìn)了仿真比較。結(jié)果表明，采用噴泉碼的信息累積協(xié)議其能量效率要明顯優(yōu)于能量累積廣播協(xié)議。下一步的研究方向是簡(jiǎn)化DIABP協(xié)議設(shè)計(jì)，提高協(xié)議的空分復(fù)用性。

參考文獻(xiàn)：

[1] Maric I, Yates R D. Cooperative multi-hop broadcast for wireless networks [J]. IEEE Journal on Selected Areas in Communications, 2004, 22(6):1080-1088.

[2] Kailas A, Thanayamkizil L, Ingram M A. A simple cooperative transmission protocol for energy-efficient broadcasting over muti-hop wireless networks [J]. IEEE Journal of Communications and Networks, 2008, 10(2):213-220.

[3] Byers J W, Luby M, Mitzenmacher M , et al. A digital fountain approach to reliable distribution of bulk data[C]//Proceedings of ACM Special Interest Group on Data Communication.Vancouver,Canada: IEEE, 1998:56-67.

[4] Luby M. LT Codes[C]//Proceedings of the 43rd Annual IEEE Symposium on Foundations Computer Science.Vancouver,Canada:IEEE,2002:271-280.

[5] Shokrollahi A. Raptor codes[J].IEEE Transactions on Information Theory, 2006,52(6):2551-2567.

[6] Molish A F, Methta N B, Yedida J S, et al. Performance of fountain codes in collaborative relay networks [J]. IEEE Transactions on Wireless Communications, 2007,6(11):4108-4119.

[7] Castura J, Mao Y. Rateless coding for wireless relay channels [J].IEEE Transactions on Wireless Communications, 2007, 6(5):1638-1642.

[8] Li F,Nikolaidis I. On minimum-energy broadcasting in all-wireless networks[C]//Proceedings of Local Computer Networks.Tampa,FL,USA:IEEE,2001:193-202.

[9] Ahluwalia A, Modiano E, Shu L. On the complexity and distributed construction of energy-efficient broadcast trees in ad-hoc wireless networks [J].IEEE Transactions on Wireless Communications, 2005, 4(5):2136-2147.

[10] Li N, Hou C. BLMST: A scalable, power efficient broadcast algorithm for wireless networks[C]//Proceeding of Quality of Service in Heterogeneous Wired/Wireless Networks. Dallas, TX, USA: IEEE, 2004:44-51.