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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 式(5)的誤差分布

圖2 式(6)的誤差分布

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

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

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

其中，t是連續(xù)值的重傳次數(shù)，s是分布函數(shù)的平移量。圖3給出了p=0.2，R=5時(shí)不同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時(shí)式(8)的計(jì)算值分別相當(dāng)于E[M]的下限、上限和近似值，這3種情況與式(3)的1 380樣點(diǎn)的平均絕對(duì)誤差分別為0.536、0.464和0.138。前2種情況的精度優(yōu)于式(5)，后一種優(yōu)于式(5)和式(6)。為保證E[M]的計(jì)算結(jié)果不小于1，s=0.5的式(8)可修改如下

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

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

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

圖4 式(9)的誤差分布

5 高精度的E[M]近似表達(dá)式

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

將附錄B中的式(16)代入式(9)，并進(jìn)行多項(xiàng)式合并，可得(推導(dǎo)過程參見附錄C)

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

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

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

6 結(jié)束語

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

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

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

當(dāng)01p＜≤時(shí)，對(duì)數(shù)函數(shù)lnp可展開為如下形式的冪級(jí)數(shù)

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

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

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

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

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

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

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

分部積分法

令x=pt-s，則

積分逐級(jí)降階

由式(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] 姜博,曹志剛,晏堅(jiān).PLFEC 可靠多播解決方案分組長度研究[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版）, 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] 祝峰, 武玲霜, 谷源濤.可靠多播方案的最佳有效負(fù)載長度研究[J].通信學(xué)報(bào), 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.