可靠廣播單組傳輸次數的期望

王開云，李幼平，孔思淇，趙強，馬衛東

（1.中國工程物理研究院 計算機應用研究所, 四川 綿陽 621900；2. 中國工程院, 北京 100000；3. 中國工程物理研究院 電子工程研究所, 四川 綿陽 621900）

1 引言

網絡和信息服務技術的快速發展，使得訪問形式服從冪律分布的點對點傳輸網絡極易發生擁塞，難以滿足用戶需求，進而推動了數據廣播/多播理論和技術的研究。在一對多的信息傳播模式中，與單播技術相比，廣播能夠提供更高的數據傳輸效率，在數據廣播、大文件分發、音視頻點播等方面得到了廣泛的應用。

常見的可靠廣播機制包括輪播、ARQ(automatic repeat-request)廣播、HARQ(混合ARQ)廣播和網絡編碼（NC, network coding）廣播，后者包含ARQ_NC和數字噴泉碼2種方式。在單跳、誤碼傳輸環境中，如果被傳送的數據只有一個分組，除了HARQ廣播外，這些廣播機制均簡化為單組重傳。令M為所有用戶正確接收一個分組所需的傳輸次數，參照文獻[1,2]，設它的數學期望為E[M]，它與分組丟失率和用戶數有關，是分析可靠廣播效率的基礎參數。

迄今為止，相關文獻基于單組數據重傳的多用戶接收正確率的離散概率分布函數得出了兩類E[M]的解：精確的級數解和用于分析復雜度的近似解。前者可能耗費較多的時間，計算復雜，后者的精度在部分區間相當差。本文在研究了對數函數冪級數部分和與相應的連續概率分布函數期望的基礎上，通過將級數解和基于連續概率分布的近似解進行有機組合，得到了計算簡單、精度較高、物理意義更加明確的E[M]的近似解析解。

2 相關研究工作

本節簡單描述部分文獻給出的可靠廣播/多播的實現機制，并指出E[M]的研究現狀。

Pingali、Towsley和Kurose對3種可靠多播協議進行了深入的分析[1,2]。第一種協議的接收方發送ACK（acknowledgments）消息，差錯控制以發送方為主完成；后2種協議中，接收方發送NAK（negative acknowledgments）消息（即時發送和隨機延時發送），收方主導差錯控制的過程。為了比較3種協議的性能，給出E[M]的3種表達式：無窮級數、有限級數和近似解析解。前2個計算比較復雜，后者除了E[M]非常接近于1的情況外，誤差較大。Levine等人[3]將文獻[1,2]的協議與基于樹（tree-based）和基于環（ring-based）的可靠多播協議進行了比較，得到了基于樹可靠多播性能更優的結論。對E[M]的分析仍然是該文的重要內容之一，分析方法與文獻[1,2]類似。

當信道比較差的時候（尤其是無線傳輸情形），ACK和NAK差錯控制的效率非常低，就需要應用前向糾錯（FEC）技術。目前可靠廣播FEC方案主要包括RS碼（reed-solomon code）和噴泉碼[5～8]，它們將k個分組組成數據塊進行編碼，生成n(n＞k)個包括糾錯冗余的分組發送到接收端，用戶只要收到足夠多的分組（數量不小于k，噴泉碼要求的數量稍多一些），就能完整地恢復整塊數據。然而，對于非噴泉碼的FEC，當錯誤分組數超過糾錯能力時，還是需要重傳，重傳次數的分析方法與E[M]類似，只不過是將分組重傳的過程換成了分塊(包括多個分組)重傳，分組丟失率變成了FEC后的分塊丟失率。這些文獻也沒有給出E[M]簡單、精度較高的近似解。

還有一些非傳統的多播糾錯方案。Banerjee[4]提出了一種覆蓋網絡彈性多播，其基本機制為：在樹型多播系統中，收到數據分組的節點，以較小的概率向其他分支葉子節點隨機發布該分組數據，如果該節點以前未收到此數據，則糾正錯誤。此方法的開銷和延遲較低，效率較高。Nguyen[9]等人提出了一種基于網絡編碼的可靠多播方法，發送方采用異或計算(⊕)減少需要錯誤分組重發的數量。例如，收方1只丟失了a分組，收方2只丟失了b分組，發方僅需發送一個分組a⊕b，收方1通過b⊕(a⊕b)可以恢復a分組，收方2通過a⊕(a⊕b)可以恢復b分組。文獻[4,9]的分析中還是沒有E[M]的簡單、精確近似解。Ghaderi[10]等人對無線網絡中網絡編碼的可靠性增益進行了定量分析，他們采用單組傳輸次數的期望作為可靠性性能指標，并給出了E[M]極限表達式，它在E[M]為1～10的范圍內，除了接收者數量很少的情況外，誤差非常明顯。

3 符號定義和已有的分析結果

本文研究的問題可描述為：一個發送方負責發送分組數據到多個接收者，傳輸誤碼引起的各接收方分組丟失率相同且相互獨立，一個單組數據平均經過多少次重復傳遞，所有接收方才能正確接收到該分組數據。符號的定義如下。

p：收方分組丟失率，各收方分組的丟失是不相關的事件；

R：接收用戶的數量；

m：一個分組重傳的次數；

M：所有接收用戶正確接收一個分組所需的重傳次數；

Hn：n階調和數，n為正整數；

γ：歐拉常數，γ≈0.577 215 664 9。

根據文獻[1～3,7～10]，E[M]的分析過程如下。

一個分組經過m次重傳后，所有用戶正確接收該分組的概率為

這里的m為非負整數，式(1)是一種離散的概率分布函數。

所有接收者均正確接收單個分組數據所需的平均重傳次數，即M的數學期望為

式(2)～式(4)的計算量是不可控的，當R很大時，式(4)數值計算難度較大，甚至在計算上是不可行的。鑒于精確公式計算的復雜性，文獻[2]和文獻[10]給出了下列2種簡單的近似公式

為了分析上述近似公式存在的誤差，對R取20，21，22，…，228和229共30種值，對p取46個值，其范圍為[10-8, 0.839 67]，后一個值為當前值的1.5倍，總的計算樣點數為1 380個，本文后面在檢驗其他E[M]近似公式的精度時，都將采用這里的實驗方案。式(5)和式(6)與式(3)的1 380樣點的平均絕對誤差分別為1.32和0.306。圖1和2給出了式(5)和式(6)誤差分布的情況，E3[M]表示式(3)的計算值。計算數據按式(3)結果從小到大進行了排序，式(3)的計算精度為10-10。顯然，簡單的式(5)和式(6)用于計算E[M]的下限和上限尚可，但用作它的近似式，則精度明顯不足。

圖1 式(5)的誤差分布

圖2 式(6)的誤差分布

4 基于連續概率分布的E[M]近似式及其物理意義分析

式(1)是一個離散的概率分布函數，在計算E[M]時，可以用一個連續概率分布函數

將式(2)的級數計算近似等效為積分計算

其中，t是連續值的重傳次數，s是分布函數的平移量。圖3給出了p=0.2，R=5時不同s值的概率分布，其中，F(int(t)，0)與式(1)的離散概率分布相同，圖中各分布曲線的左邊的面積為相應的期望值。將連續分布函數(1-pt-s)n在區間a≤t≤b的期望（附錄B的式(16)）代入式(7)可得

由圖3可知，s=0、s=1和s=0.5時式(8)的計算值分別相當于E[M]的下限、上限和近似值，這3種情況與式(3)的1 380樣點的平均絕對誤差分別為0.536、0.464和0.138。前2種情況的精度優于式(5)，后一種優于式(5)和式(6)。為保證E[M]的計算結果不小于1，s=0.5的式(8)可修改如下

它與式(3)的1 380樣點的平均絕對誤差為0.091 1，圖4給出了式(9)與式(3)的誤差分布。

式(3)是一個無窮級數表達式，雖然其計算結果是精確的，但從公式結構來看，只能定性地表明E[M]是p和R的單調增長函數。在此基礎上，式(5)和式(6)明確了E[M]與R的關系：當p不變的情況下，若不考慮常數項，E[M]與lnR成正比(lnR是式(6) HR的核心部分)。考慮到所需的前提條件，這種關系是半定量的。式(9)則進一步明確了E[M]與p的半定量關系：若不考慮常數項，E[M]與lnR成正比，與lnp-1成反比，或者說E[M]是以p-1為底的R的對數函數。式(9)的精度明顯高于式(5)和式(6)，收斂速度更快，故該式展現變量之間的關系，更接近E[M]的本質。

圖3 3種s值的連續概率分布和離散概率分布

圖4 式(9)的誤差分布

5 高精度的E[M]近似表達式

當E[M]比較小時，如果用式(9)取代式(3)仍然存在比較明顯的相對誤差。通過觀察可以發現，在限定結果誤差的條件下，如果E[M]較小，式(2)一般僅需要計算前幾項的和，即可滿足精度要求，計算量并不大；若E[M]較大，采用式(9)能夠獲得符合精度要求的計算結果。因此，將基于離散分布和連續分布的E[M]計算方法結合在一起，可以獲得計算簡單、精度較高的E[M]表達式

將附錄B中的式(16)代入式(9)，并進行多項式合并，可得(推導過程參見附錄C)

對于k為1到6的情形，式(10)與式(3)1 380樣點的平均絕對誤差分別為0.071 1、0.021 1、0.009 11、0.005 04、0.003 26和0.002 41。隨著k的增加，精度改善的幅度越來越小，故未列出k更大時的結果。在計算分析過程發現，將上式最后的指數項由R調整為exp(HR)，可使這6種情形的誤差分別降低到0.059 5、0.015、0.005 46、0.002 55、0.001 47和0.001 02。綜合考慮表達式的復雜性和計算精度，選用k=3時的式(10)作為E[M]的高精度近似式

圖5給出了式(11)與式(3)的誤差分布。為便于與式(6)的精度進行直觀的比較，圖5還列出了式(6)與式(3)的誤差分布。導致式(11)存在誤差的主要原因有2個，k的取值不夠大，近似處理采用的式(16)本身就存在誤差。在本文給定的實驗參數條件下，式(11)盡管沒有完全消除誤差，但其平均精度比式(5)提高了接近3個量級，比式(6)提高了接近2個量級，與式(3)相比，計算更簡單。

圖5 式(11)和式(6)的誤差分布

6 結束語

在可靠廣播/多播理論中，求解單組數據重傳次數的數學期望是一個比較重要的問題。本文通過概率分布函數的連續化近似處理，獲得了精度優于已有文獻的近似公式，其物理解釋更加明確。在此基礎上，將它與已有的無窮級數解相結合，得到了一個高精度的近似公式，能夠幫助廣播/多播系統更加精確地控制單組數據的播發次數，既避免接收不完整，又避免過分冗余，進而提高系統的效率。

本研究并未限定是否存在回傳信道。因此，導出的E[M]表達式，既適用于純單向的廣播傳輸，也可用于雙向網絡的ARQ廣播/多播模式。

附錄A 對數函數冪級數部分和的估計

當01p＜≤時，對數函數lnp可展開為如下形式的冪級數

其中，n為正整數，rn(p)為余項，應該滿足下列4個條件：

據此可構造一種rn(p)的表達式

由式(12)和式(13)可得，對數函數冪級數部分和的近似式為

為了檢驗上述近似帶來的誤差情況，分別定義

圖6 對數函數冪級數部分和近似式的誤差分布

附錄B 連續分布函數(1-pt-s)n 在區間a≤t≤b的期望

設(1-pt-s)n是隨機變量ξ的分布函數。其中，0≤p≤1，n為正整數，a≤t≤b，s≥0，a≥s。隨機變量ξ在區間a≤t≤b的期望為

分部積分法

令x=pt-s，則

積分逐級降階

由式(14)可得

附錄C 式(10)推導過程

[1] PINGALI S, KUROSE J F, TOWSLEY D. A comparison of sender-initiated and receiver-initiated reliable multicast protocols[A].Sigmetrics’94[C]. New York, USA, 1994. 221-230.

[2] TOWSLEY D, KUROSE J, PINGALI S. A comparison of sender-initiated and receiver-initiated reliable multicast protocols[J]. IEEE Selected Areas in Communications, 1997, 15(3):398-406.

[3] LEVINE B N, GARCIA-LUNA-ACCEVES J J. A comparison of reliable multicast protocols[J]. Multimedia Systems, 1998, 6(5): 334-348.

[4] BANERJEE S, LEE S, BHATTACHARJEE B, etal. Resilient multicast using overlays[J]. IEEE/ACM Transaction on Networking, 2006,14(2): 237-248.

[5] PELTOTALO J, PELTOTALO S, HARJU J. Analysis of the flute data carousel[A].Proceedings of EUNICE Summer School 2005[C]. Colmenarejo, Spain, 2005.138-142.

[6] LUBY M, WATSON M, GASIBA T, etal. Raptor codes for reliable download delivery in wireless broadcast systems[A]. CCNC'06[C].2005.192-197.

[7] 姜博,曹志剛,晏堅.PLFEC 可靠多播解決方案分組長度研究[J].清華大學學報（自然科學版）, 2008,48(4): 567-570.JIANG B, CAO Z G, YAN J. Packet lengths of PLFEC-based reliable multicast solutions[J]. Journal of Tsinghua University, 2008, 48(4):567-570.

[8] 祝峰, 武玲霜, 谷源濤.可靠多播方案的最佳有效負載長度研究[J].通信學報, 2011, 32(6) :101-106.ZHU F, WU L S, GU Y T. Optimial payload lengths of reliable multicast schemes[J]. Journal on Communications, 2011, 32(6):101-106.

[9] NGUYEN D, TRAN T, NGUYEN T, etal. Wireless broadcast using network coding[J]. IEEE Transactions on Vehicular Technology, 2009,58(2): 914-925.

[10] GHADERI M, TOWSLEY D, KUROSE J. Reliability gain of network coding in lossy wireless networks[A]. INFOCOM 2008, Phoenix[C].AZ:IEEE Press, 2008. 2171-2179.