王開云，李幼平，孔思淇，趙強，馬衛(wèi)東

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

1 引言

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

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

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

2 相關(guān)研究工作

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

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

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

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

3 符號定義和已有的分析結(jié)果

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

p：收方分組丟失率，各收方分組的丟失是不相關(guān)的事件；

R：接收用戶的數(shù)量；

m：一個分組重傳的次數(shù)；

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

Hn：n階調(diào)和數(shù)，n為正整數(shù)；

γ：歐拉常數(shù)，γ≈0.577 215 664 9。

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

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

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

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

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

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

圖1 式(5)的誤差分布

圖2 式(6)的誤差分布

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

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

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

其中，t是連續(xù)值的重傳次數(shù)，s是分布函數(shù)的平移量。圖3給出了p=0.2，R=5時不同s值的概率分布，其中，F(xiàn)(int(t)，0)與式(1)的離散概率分布相同，圖中各分布曲線的左邊的面積為相應(yīng)的期望值。將連續(xù)分布函數(shù)(1-pt-s)n在區(qū)間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種情況的精度優(yōu)于式(5)，后一種優(yōu)于式(5)和式(6)。為保證E[M]的計算結(jié)果不小于1，s=0.5的式(8)可修改如下

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

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

圖3 3種s值的連續(xù)概率分布和離散概率分布

圖4 式(9)的誤差分布

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

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

將附錄B中的式(16)代入式(9)，并進行多項式合并，可得(推導(dǎo)過程參見附錄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更大時的結(jié)果。在計算分析過程發(fā)現(xiàn)，將上式最后的指數(shù)項由R調(diào)整為exp(HR)，可使這6種情形的誤差分別降低到0.059 5、0.015、0.005 46、0.002 55、0.001 47和0.001 02。綜合考慮表達式的復(fù)雜性和計算精度，選用k=3時的式(10)作為E[M]的高精度近似式

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

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

6 結(jié)束語

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

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

附錄A 對數(shù)函數(shù)冪級數(shù)部分和的估計

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

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

據(jù)此可構(gòu)造一種rn(p)的表達式

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

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

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

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

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

分部積分法

令x=pt-s，則

積分逐級降階

由式(14)可得

附錄C 式(10)推導(dǎo)過程

[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.