基于網(wǎng)絡(luò)編碼的協(xié)作恢復(fù)機(jī)制線性可解性研究

殷俊，沙雪琪，王磊，張登銀，楊余旺

（1.南京郵電大學(xué)江蘇省寬帶無線通信重點(diǎn)實驗室，江蘇 南京 210003；2.南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003；3.南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210004）

1 引言

無線廣播/多播是一種經(jīng)典且高效的信息分發(fā)方式。但由于無線電波傳播特性，信源傳輸?shù)讲煌邮斩说臄?shù)據(jù)包具有獨(dú)立刪除特征，如何保證多接收方可靠接收是現(xiàn)代廣播/多播系統(tǒng)設(shè)計的難點(diǎn)[1-2]。注意到，無線通信節(jié)點(diǎn)的一個典型發(fā)展趨勢是多接口化，如各類智能終端、車聯(lián)網(wǎng)車輛[3]均配置了遠(yuǎn)程通信接口和短程通信接口，基于此研究人員提出了協(xié)作恢復(fù)（CR,cooperative recovery/repair）機(jī)制。CR 通過利用相鄰節(jié)點(diǎn)間的短程通信來恢復(fù)彼此在遠(yuǎn)程廣播通信中丟失的數(shù)據(jù)包。大量實踐結(jié)果表明，CR可有效地提高多播吞吐量，增強(qiáng)網(wǎng)絡(luò)可靠性[4-5]。CR 在車聯(lián)網(wǎng)中的一種典型應(yīng)用場景如圖1 所示，路側(cè)單元（RSU,road side unit）需要通過廣播方式向覆蓋范圍內(nèi)的車輛廣播信息。由于車輛通常會快速駛離RSU 的通信覆蓋范圍，因此無法持續(xù)依賴RSU 進(jìn)行出錯數(shù)據(jù)包的修復(fù)?？紤]到不同車輛在RSU 廣播階段接收正確或出錯的數(shù)據(jù)包各異，使用CR 機(jī)制的車輛在移出RSU 覆蓋范圍后依然可以依靠短距離通信接口互相修復(fù)彼此在RSU 廣播過程中丟失的數(shù)據(jù)包。

圖1 CR 在車聯(lián)網(wǎng)中的一種典型應(yīng)用場景

與傳統(tǒng)的自動重傳請求（ARQ,automatic repeat request）、信源重傳等可靠傳輸方案相比，CR 具有較明顯的優(yōu)勢。首先，CR 降低了源節(jié)點(diǎn)的重傳負(fù)擔(dān)。其次，鄰居節(jié)點(diǎn)之間在交互階段使用短距離通信接口，信道質(zhì)量較廣播源與節(jié)點(diǎn)間的長程信道更高，使CR 交互過程的丟包率遠(yuǎn)小于源節(jié)點(diǎn)傳輸過程。需要指出的是，鄰居節(jié)點(diǎn)間可以采用ad-hoc 模式進(jìn)行分布式管理，因此CR 的交互過程整體控制負(fù)擔(dān)較小。大量研究表明，在CR 基礎(chǔ)上引入網(wǎng)絡(luò)編碼可以進(jìn)一步提高節(jié)點(diǎn)協(xié)作效率[6-14]。網(wǎng)絡(luò)編碼由Ahlswede 等[15]提出，其核心思想是允許中間節(jié)點(diǎn)對接收到的信息進(jìn)行再編碼，打破了傳統(tǒng)網(wǎng)絡(luò)中間節(jié)點(diǎn)僅對信息進(jìn)行存儲轉(zhuǎn)發(fā)的限制，可以有效提升通信網(wǎng)絡(luò)的吞吐量和可靠性。

Park 等[6]最早提出將隨機(jī)線性網(wǎng)絡(luò)編碼（RLNC,random linear network coding）[16]應(yīng)用于CR 過程，協(xié)作節(jié)點(diǎn)需要將接收到的數(shù)據(jù)包進(jìn)行隨機(jī)線性組合生成多個線性無關(guān)的編碼包，信宿節(jié)點(diǎn)收到這些編碼包后進(jìn)行解碼，得到原始數(shù)據(jù)包。但由于RLNC在解碼時需要信宿節(jié)點(diǎn)必須接收到足夠多的編碼包，因此信宿節(jié)點(diǎn)等待解碼的時延較大。近年來，隨著直連通信（D2D,device to device）的理念提出，基于網(wǎng)絡(luò)編碼的CR 機(jī)制往往與D2D 相結(jié)合[7]。Yan等[8]提出基于機(jī)會網(wǎng)絡(luò)編碼（ONC,opportunistic network coding）的CR 機(jī)制，數(shù)據(jù)包的編碼組合僅依賴每個協(xié)作節(jié)點(diǎn)當(dāng)前接收或丟失的狀態(tài)。與RLNC 相比，ONC 更加靈活，節(jié)點(diǎn)待解碼的時延更小。綜合來看，當(dāng)前本領(lǐng)域的研究主要集中在以下2 個方面。

1) 尋找更優(yōu)的機(jī)會網(wǎng)絡(luò)編碼碼字構(gòu)造方法。其中典型的有立即可解網(wǎng)絡(luò)編碼（IDNC,instantly decodable network coding）[9-11]。由于IDNC 的編解碼復(fù)雜度較低，解碼過程具有及時性，因此適用于時延敏感型的近鄰視頻交互、實時對戰(zhàn)游戲等應(yīng)用場景。

2) 尋找更合理的節(jié)點(diǎn)協(xié)作傳輸策略，降低CR過程開銷。與傳統(tǒng)的一對多網(wǎng)絡(luò)傳輸過程不同，CR在網(wǎng)絡(luò)重傳階段的信源轉(zhuǎn)變?yōu)槟骋粋€或多個網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)，所以協(xié)作過程的另一個重要研究內(nèi)容是結(jié)合具體編碼和底層傳輸協(xié)議尋找協(xié)作節(jié)點(diǎn)的內(nèi)容傳輸策略[10-14]。文獻(xiàn)[10]提出在D2D 網(wǎng)絡(luò)中采用集中化方式選擇IDNC 的編碼包，降低單次重傳的解碼時延增量。在此基礎(chǔ)上，文獻(xiàn)[11]提出一種構(gòu)造終端節(jié)點(diǎn)間協(xié)作傳輸?shù)拿軋D算法，通過搜索極大獨(dú)立集選擇并行協(xié)作重傳終端，降低節(jié)點(diǎn)間協(xié)作重傳開銷。文獻(xiàn)[12]引出了節(jié)點(diǎn)協(xié)作過程的公平性問題。針對此問題，文獻(xiàn)[13]將CR 過程抽象為廣播和協(xié)作傳輸2 個階段，并設(shè)計了一種分布式的調(diào)度算法，提高了協(xié)作傳輸階段的信息恢復(fù)效率。出于同樣的思想，文獻(xiàn)[14]基于時分多址接入（TDMA,time division multiple access）協(xié)議提出了一種面向車聯(lián)網(wǎng)的分布式CR 重傳實施方法。

然而，上述2 類研究在分析和討論節(jié)點(diǎn)解碼時的線性可解性上均直接采用經(jīng)典RLNC 方法的結(jié)論[16]。經(jīng)典RLNC 線性可解性理論認(rèn)為當(dāng)編碼有限域足夠大時，只要某個目的節(jié)點(diǎn)成功接收到的編碼包個數(shù)和源數(shù)據(jù)包個數(shù)相等就能以極高的概率解碼[17]。例如，對于有限域GF(216)，當(dāng)源數(shù)據(jù)包個數(shù)為5 時，接收到5 個隨機(jī)線性編碼數(shù)據(jù)包的目的節(jié)點(diǎn)解碼概率超過96%。而本質(zhì)上CR 編碼過程是一種機(jī)會的網(wǎng)絡(luò)編碼，與RLNC 的編解碼過程不可等價，直接利用RLNC 結(jié)論假設(shè)CR 協(xié)作恢復(fù)階段目的節(jié)點(diǎn)收到與源數(shù)據(jù)包相同數(shù)量的編碼包即可解碼顯然是不合理的。本文針對基于網(wǎng)絡(luò)編碼的CR 機(jī)制應(yīng)用中線性可解性這一關(guān)鍵、基礎(chǔ)問題展開研究，主要貢獻(xiàn)如下。

1) 建立了基于網(wǎng)絡(luò)編碼的CR機(jī)制線性可解性分析模型；給出了不同包刪除率、編碼伽羅華域階、協(xié)作節(jié)點(diǎn)數(shù)等多種參數(shù)綜合影響下，基于網(wǎng)絡(luò)編碼的CR 機(jī)制網(wǎng)絡(luò)內(nèi)任意節(jié)點(diǎn)解碼出所有源數(shù)據(jù)包的概率上下界。數(shù)值實驗驗證了該理論上、下界的準(zhǔn)確性和緊密性。

2) 提出了一種CR 線性可解性在線判定算法。協(xié)作簇內(nèi)節(jié)點(diǎn)可根據(jù)該算法在協(xié)作恢復(fù)過程進(jìn)行編碼包部分解碼，不需要等待協(xié)作階段結(jié)束。理論分析和實驗表明，該算法降低了傳統(tǒng)高斯方法的解碼等待時延和存儲開銷。

2 系統(tǒng)模型

由于應(yīng)用場景差異，不同研究中基于網(wǎng)絡(luò)編碼的CR 系統(tǒng)模型會有細(xì)微區(qū)別，本文考慮如圖1 所示的典型應(yīng)用場景下的兩階段CR 模型[12-13]。遠(yuǎn)程基站需要向其覆蓋范圍內(nèi)的所有移動節(jié)點(diǎn)廣播源信息S（不失一般性，假設(shè)S包含N個數(shù)據(jù)包并記）。采用CR 機(jī)制，S的交付過程將被分為2 個階段。第一階段，基站順序廣播S。由于廣播信道的刪除特性，網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)可能無法全部正確接收N個數(shù)據(jù)包。為了恢復(fù)丟失的包，相鄰的節(jié)點(diǎn)根據(jù)地理位置或者移動特征，預(yù)先形成了若干個協(xié)作簇。第二階段，網(wǎng)絡(luò)編碼協(xié)作恢復(fù)過程。協(xié)作簇內(nèi)節(jié)點(diǎn)間可以通過短距離無線通信接口交換網(wǎng)絡(luò)編碼包，從而恢復(fù)彼此在第一階段接收過程中丟失的包。假設(shè)某協(xié)作簇包含M個協(xié)作中繼節(jié)點(diǎn)，并記為，簇內(nèi)的任意節(jié)點(diǎn)CRi進(jìn)行網(wǎng)絡(luò)編碼協(xié)作恢復(fù)的過程。若CRi第一階段成功接收了k個源數(shù)據(jù)包，首先，CRi在有限域上隨機(jī)生成前k個元素非零編碼向量a={a1,a2,…,ak}；然后，進(jìn)行線性編碼cpi=asi產(chǎn)生編碼結(jié)果cpi；最后，將編碼結(jié)果cpi和編碼向量a打包成一個編碼包傳遞給簇內(nèi)的鄰居節(jié)點(diǎn)。

通過如圖2 所示的基于網(wǎng)絡(luò)編碼的CR 系統(tǒng)模型詳細(xì)展示上述過程。遠(yuǎn)程基站需要盡最大可能向覆蓋范圍內(nèi)節(jié)點(diǎn)交付信息S={s1,s2,s3}。經(jīng)過第一階段基站廣播傳輸后，網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)CR1、CR2和CR3分別接收到了部分?jǐn)?shù)據(jù)包（如圖2(a)所示，其中畫×的數(shù)據(jù)包表示對應(yīng)節(jié)點(diǎn)未能成功接收該數(shù)據(jù)包）。第二階段，3 個節(jié)點(diǎn)形成一個協(xié)作簇，簇內(nèi)采用網(wǎng)絡(luò)編碼進(jìn)行丟失信息修復(fù)。CR1節(jié)點(diǎn)根據(jù)第一輪接收到的源數(shù)據(jù)包have1={s2,s3}，從有限域里隨機(jī)生成一個編碼系數(shù)向量（假設(shè)為(1,2)），根據(jù)編碼向量對源數(shù)據(jù)包進(jìn)行線性組合，生成一個編碼包c(diǎn)p1=s2+2s3，并占用一個時間片傳輸給了鄰居節(jié)點(diǎn)。類似地，節(jié)點(diǎn)CR2編碼并傳輸了cp2=2s1+3s3。對于節(jié)點(diǎn)CR3，由于它偵聽到了2 個編碼數(shù)據(jù)包，結(jié)合在第一階段節(jié)點(diǎn)收到的源數(shù)據(jù)包（也可視作以編碼向量為單位向量的編碼包），CR3節(jié)點(diǎn)共接收到3 個線性無關(guān)數(shù)據(jù)包，因此可以通過高斯消去解碼出源數(shù)據(jù)包S={s1,s2,s3}，完成CR 修復(fù)過程。

通過圖2 的例子可以發(fā)現(xiàn)，如果節(jié)點(diǎn)間協(xié)作傳輸MAC 協(xié)議采用CSMA/CA 或TDMA 協(xié)議，簇內(nèi)節(jié)點(diǎn)在協(xié)作恢復(fù)過程同一時間片只有一個節(jié)點(diǎn)處于發(fā)送狀態(tài)，簇內(nèi)其他節(jié)點(diǎn)均處于接收狀態(tài)可監(jiān)聽到該數(shù)據(jù)包（存在一定的刪除率）。例如在圖2 中，對于含有M（M=3）個節(jié)點(diǎn)的協(xié)作簇，在整個第二階段共需要消耗M個時間片，任意節(jié)點(diǎn)均消耗一個時間片進(jìn)行編碼傳輸，消耗M? 1個時間片進(jìn)行接收。由于采用網(wǎng)絡(luò)編碼的CR 機(jī)制工作時簇內(nèi)節(jié)點(diǎn)間直接交互編碼數(shù)據(jù)包而不是源數(shù)據(jù)包，而編碼數(shù)據(jù)包是多個源數(shù)據(jù)包信息的混合，每個簇內(nèi)節(jié)點(diǎn)只要在兩階段時間片內(nèi)接收到N個線性無關(guān)編碼包即可解碼出所有源數(shù)據(jù)。因此，基于網(wǎng)絡(luò)編碼的CR 傳輸過程可自組織，減少了傳統(tǒng)CR 過程中修復(fù)過程的時延，也避免了借助額外的控制機(jī)制所帶來的資源開銷。本文推導(dǎo)經(jīng)過一輪這樣的CR 傳輸后，簇內(nèi)任意節(jié)點(diǎn)能夠成功解碼出N個源數(shù)據(jù)包的概率，這也是基于網(wǎng)絡(luò)編碼的CR 機(jī)制里一個待解決的基礎(chǔ)問題。

圖2 基于網(wǎng)絡(luò)編碼的CR 系統(tǒng)模型

注意到，解碼過程不僅受到協(xié)作恢復(fù)的節(jié)點(diǎn)數(shù)量、具體網(wǎng)絡(luò)編碼有限域影響，還在很大程度上受到數(shù)據(jù)包在兩階段物理信道上傳輸時的刪除率影響。本文采用基于文獻(xiàn)[13,18]的具體物理信道模型建模數(shù)據(jù)包刪除率：假設(shè)兩階段傳輸信道均為加性白高斯噪聲（AWGN,additive white Gaussian noise）信道，并且各信道間獨(dú)立。本文信道模型只是CR傳輸領(lǐng)域若干模型中的一種典型模型[13,18]，而基于網(wǎng)絡(luò)編碼的CR 過程線性可解性不僅受物理信道參數(shù)影響，還受到編碼有限域、協(xié)作節(jié)點(diǎn)數(shù)等參數(shù)影響。為了保證本文結(jié)論可適應(yīng)其他信道模型，后文所提出的線性可解性及其結(jié)論僅依賴于信道上傳輸?shù)臄?shù)據(jù)包刪除率，獨(dú)立于具體底層所使用的物理信道。因此，應(yīng)用了其他信道模型的CR 機(jī)制容易在本文信道模型建模思路上修改使用。在基站廣播階段，簇內(nèi)任意節(jié)點(diǎn)CRi收到的信號為

其中，Pbase表示基站傳輸功率；hbase,i表示基站和節(jié)點(diǎn)CRi間的信道增益，是一個均值為0、方差為的循環(huán)對稱復(fù)高斯變量；s是基站廣播的信號；nbase,i是均值為0、方差為的復(fù)AWGN 噪聲。同理，在協(xié)作傳輸階段，任意節(jié)點(diǎn)CRi接收到來自節(jié)點(diǎn)CRj的信號為

其中，esr表示第一階段廣播信道的刪除率，erd表示第二階段協(xié)作交互信道的刪除率；Ethreshold表示預(yù)設(shè)的頻譜效率門限值。據(jù)此，可以建模CR 過程，記M為協(xié)作簇的節(jié)點(diǎn)個數(shù)，F(xiàn)q為階為q的網(wǎng)絡(luò)編碼運(yùn)算有限域，模型詳細(xì)參數(shù)如表1 所示。不失一般性，從M個協(xié)作節(jié)點(diǎn)中任選一個節(jié)點(diǎn)CRi為目標(biāo)節(jié)點(diǎn)，下面將分析經(jīng)過一次完整的兩階段CR 數(shù)據(jù)傳輸過程之后，節(jié)點(diǎn)CRi能夠成功解碼出全部N個源數(shù)據(jù)包的概率。

表1 模型參數(shù)及其含義

3 基于網(wǎng)絡(luò)編碼的CR 線性可解性分析

根據(jù)第2 節(jié)的系統(tǒng)模型可知，對于包含M個節(jié)點(diǎn){CR1,CR2,…,CRM}的協(xié)作簇，簇內(nèi)任意節(jié)點(diǎn)CRi在整個CR 傳輸過程中可以接收的（編碼）數(shù)據(jù)包有2 個來源：第一階段廣播信道上基站發(fā)送的N個源數(shù)據(jù)包和第二階段交互信道上簇內(nèi)其他鄰居節(jié)點(diǎn)發(fā)送的M? 1個編碼數(shù)據(jù)包。假設(shè)節(jié)點(diǎn)CRi在廣播階段成功接收了k(0≤k≤N)個數(shù)據(jù)包，其概率為Prsuc_brod(k)，由于信道傳輸過程獨(dú)立，因此由二項分布得

其中，esr表示廣播信道的刪除率。由全概率公式可得，經(jīng)過一輪完整的CR 數(shù)據(jù)傳輸過程之后CRi成功解碼出所有N個源數(shù)據(jù)包的概率Prsuc為

其中，Ek×k是k階單位陣；QN×N是N階初等列變換陣，可交換矩陣 (Ek×k0)列次序使(Ek×k0)QN×N=Ck×N。

示例1如圖2 所示的CR 過程，節(jié)點(diǎn)CR3在兩階段接收的編碼包CP=[s3s2+2s32s1+3s3]T及其傳輸矩陣按式(7)分解過程

因此，CRi在接收到CP后是否能夠成功解碼出所有源數(shù)據(jù)包SN問題等價于式(7)的線性方程組是否有唯一解，因此從列秩考慮解碼失敗的概率為

式(8)成立是因為只有傳輸矩陣C的秩為N時，方程組才可由CP解碼出SN?？紤]到rank(QN×N)=N，且 rank(Ek×k)=k，有。因此，CRi成功解碼的概率可以通過判斷是否列滿秩來判定。為了簡便，下文將簡記為C'。事實上，QN×N僅交換了C的列次序，使矩陣C'各列對應(yīng)的是CRi第一階段未成功接收的N?k個數(shù)據(jù)包，并未改變C'元素值，而C'元素值在上隨機(jī)分布，由兩階段傳輸過程共同決定。記εl表示簇內(nèi)除CRi外第l(1≤l≤M?1)個節(jié)點(diǎn)傳輸?shù)紺Ri節(jié)點(diǎn)的編碼包刪除率，顯然 Pr{εl}=erd，。如果啞變量θ來自Fq，則C'中第l行上任意元素clj(1≤j≤N?k)的取值概率為

這是由于對于CRi節(jié)點(diǎn)而言，若在交互的過程中來自第l個節(jié)點(diǎn)的編碼包發(fā)生刪除，則矩陣C'的第l行所有元素clj(1≤j≤N?k)一定全為0；反之，則clj由第l個節(jié)點(diǎn)在廣播過程是否接收到源數(shù)據(jù)包sj來確定元素是否為0。若2 個階段均未發(fā)生刪除，則clj值可以為q階有限域Fq中任意一個非零元。因此，clj取到某一確定的非零元的概率為

綜上，CR 可解性分析思路是由式(9)的CR 過程編碼矩陣C'元素取值概率，然后根據(jù)式(8)分析C'的秩，從而求解CRi協(xié)作階段不能成功解碼出剩余N?k個數(shù)據(jù)包的概率的上下界，進(jìn)而根據(jù)式(6)得到CRi解碼出所有N個源數(shù)據(jù)包Prsuc的上界Pmax和下界Pmin。

4 基于網(wǎng)絡(luò)編碼的CR 線性可解性上界

與第3 節(jié)分析的場景一致，本文依舊假設(shè)簇內(nèi)任意節(jié)點(diǎn)CRi在廣播階段僅收到N個源數(shù)據(jù)包里的k(0≤k≤N)個。根據(jù)CR 傳輸過程容易發(fā)現(xiàn)，若簇內(nèi)所有節(jié)點(diǎn)均未能在廣播階段成功接收某一個源數(shù)據(jù)包，則通過基于網(wǎng)絡(luò)編碼的CR 過程也一定不能成功解碼出這一源數(shù)據(jù)包。例如，在圖2 所示例子中，若節(jié)點(diǎn)CR2廣播階段未能接收到源數(shù)據(jù)包s1，則簇內(nèi)任意節(jié)點(diǎn)無法通過協(xié)作過程解碼恢復(fù)出s1。因此，根據(jù)二項分布容易得到簇內(nèi)任意節(jié)點(diǎn)CRi解碼失敗概率的一個簡單下界為

容易發(fā)現(xiàn)，式(10)給出的下界僅考慮了廣播階段數(shù)據(jù)包刪除率，忽略了更關(guān)鍵的交互階段。因此，下面，本文將基于文獻(xiàn)[20]的稀疏矩陣線性可解性判定思想，給出的另一個下界。

定理1在基于網(wǎng)絡(luò)編碼的CR 機(jī)制中，對于包含M個節(jié)點(diǎn)的協(xié)作簇，若簇內(nèi)任意節(jié)點(diǎn)CRi在廣播階段僅收到N個源數(shù)據(jù)包里的k(0≤k≤N)個，則CRi在協(xié)作階段不能夠完全解碼出其余N?k個源數(shù)據(jù)包的概率的一個下界可以表示為

其中，η=min(erd+(1?erd)esr,(1?esr)(1?erd)/(q? 1))。

證明詳見附錄1。

因此，綜合式(10)和定理1，即可得到的一個較緊密下界為

其中，η=min(erd+(1?erd)esr,(1?esr)(1?erd)/(q? 1)。由簇內(nèi)任意節(jié)點(diǎn)CRi在廣播階段僅收到N個源數(shù)據(jù)包里的k個，且0≤k≤N，因此將式(12)代入式(6)，即可得到CRi經(jīng)過一次完整的數(shù)據(jù)傳輸過程之后成功解碼出N個數(shù)據(jù)包的概率Prsuc的一個較緊密上界Pmax為

5 基于網(wǎng)絡(luò)編碼的CR 線性可解性下界

與上界分析的模型一致，本節(jié)分析CR 線性可解性的下界。

定理2在基于網(wǎng)絡(luò)編碼的CR 機(jī)制中，對于包含M個節(jié)點(diǎn)的協(xié)作簇，若簇內(nèi)任意節(jié)點(diǎn)CRi在廣播階段僅收到N個源數(shù)據(jù)包里的k(0≤k≤N)個，則CRi在協(xié)作階段不能夠完全解碼出其余N?k個源數(shù)據(jù)包的概率的一個上界為

其中，esr和erd分別是兩階段的數(shù)據(jù)包刪除率，q是編碼有限域階。

證明詳見附錄2。

實驗表明，定理2 所得到的上界在編碼有限域階q的值較小時緊密；而當(dāng)q較大時，其值趨近于1，失去指導(dǎo)價值，需要進(jìn)一步優(yōu)化。注意到，由定理1 的證明過程，解碼失敗概率的上界還可以表示為

其中，?=max(erd+(1?erd)esr,(1?esr)(1?erd)/(q? 1))。證明過程與定理1 相同，此處不再贅述。

其中，?=max(erd+(1?erd)esr,(1?esr)(1?erd)/(q? 1))。將上式代入式(6)，即可得到簇內(nèi)任意節(jié)點(diǎn)CRi經(jīng)過一次完整的數(shù)據(jù)傳輸過程之后成功解碼出N個數(shù)據(jù)包的概率Prsuc的一個較緊密下界Pmin為

6 基于網(wǎng)絡(luò)編碼的CR 線性可解性在線判定算法設(shè)計

在已有基于網(wǎng)絡(luò)編碼的CR 研究中，簇內(nèi)節(jié)點(diǎn)對編碼數(shù)據(jù)包的解碼發(fā)生在整個CR 協(xié)作恢復(fù)階段完成之后，采用Gauss 消去法對其所有接收到的編碼包進(jìn)行統(tǒng)一解碼。若能解碼出所有源數(shù)據(jù)包，則說明線性可解，反之則不可解。因此，傳統(tǒng)研究中每個簇內(nèi)節(jié)點(diǎn)在整個協(xié)作階段均需要偵聽所有編碼包，然后在協(xié)作階段完成后統(tǒng)一解碼，因此解碼的等待時延較高，節(jié)點(diǎn)持續(xù)偵聽引起的能耗也較高，并且節(jié)點(diǎn)還需要預(yù)留足夠的存儲空間以緩存待解碼數(shù)據(jù)包。針對該問題，本文提出一種在線判定算法——改進(jìn)Gauss-Jordan 法，工作流程如圖3 所示，每個簇內(nèi)節(jié)點(diǎn)能夠在CR 協(xié)作恢復(fù)過程中就根據(jù)自身接收到的編碼包進(jìn)行部分解碼，不需要等待協(xié)作階段完成再進(jìn)行，不僅降低了傳統(tǒng)高斯方法的解碼等待時延，也避免了需預(yù)設(shè)編碼包緩存空間所引起的存儲開銷。

圖3 改進(jìn)Gauss-Jordan 法的工作流程

簇內(nèi)任意節(jié)點(diǎn)CRi采用改進(jìn)Gauss-Jordan 法的解碼過程描述如算法1 所示，注意，可解性在線判定過程也是逐步解碼的過程。對于圖2 所示例子，采用所提算法的節(jié)點(diǎn)CR3在兩階段CR 過程在線解碼過程如表2 所示，該過程共消耗了5 個時間片，3 個為廣播階段接收源數(shù)據(jù)包，2 個為協(xié)作修復(fù)階段接收編碼包。

表2 改進(jìn)Gauss-Jordan 算法解碼過程

算法1改進(jìn)Gauss-Jordan 算法的CR 協(xié)作過程可解性判定與漸進(jìn)解碼算法

7 改進(jìn)Gauss-Jordan 算法與傳統(tǒng)Gauss 方法性能對比分析

7.1 解碼時延對比分析

1) 傳統(tǒng)Gauss 方法

在傳統(tǒng)Gauss 方法解碼過程中，協(xié)作簇內(nèi)任意節(jié)點(diǎn)CRi在第二階段完成后才嘗試進(jìn)行高斯消去解碼，因此解碼出源數(shù)據(jù)包的時延GaussianT就是兩階段CR 傳輸過程所消耗的時間，即廣播階段基站發(fā)送N個源數(shù)據(jù)包的發(fā)送（傳輸）時延Tbroad和協(xié)作恢復(fù)階段的編碼數(shù)據(jù)包排隊待解碼的時延Tcoop。為了簡化分析過程，解碼時延分析未考慮無線信號的傳播時延和解碼過程的運(yùn)算處理時延。若協(xié)作簇包含M個節(jié)點(diǎn)，并且為了分析方便，將兩階段信道傳輸一個數(shù)據(jù)包或編碼包的時延均記為一個時間片，則Gauss 方法CRi解碼成功的時延恒定，值為TGaussian=Tbroad+Tcoop=N+M，單位為時間片。

2) 改進(jìn)Gauss-Jordan 算法

與傳統(tǒng)Gauss 方法相比，簇內(nèi)任意節(jié)點(diǎn)CRi采用改進(jìn)Gauss-Jordan 算法的時延TGauss-Jordan也包括兩部分：廣播階段消耗的時間片Tbroad（Tbroad=N）和協(xié)作階段在線解碼時延。由于CRi在協(xié)作修復(fù)階段采用所提出的改進(jìn)Gauss-Jordan 算法可在線判斷可解性，隨著接收編碼包累積的過程，一旦發(fā)現(xiàn)解碼矩陣CP線性可解即停止偵聽并完成解碼。因此，CRi協(xié)作階段解碼時延是隨著編碼包接收過程直到解碼矩陣CP滿秩的平均時間。為了量化分析，本文將節(jié)點(diǎn)采用改進(jìn)Gauss-Jordan 算法的解碼過程建模為一種齊次吸收馬爾可夫過程（AMP,absorbing Markov process）。

定義1在CR 協(xié)作恢復(fù)階段，當(dāng)且僅當(dāng)rank(CP)=r，k≤r≤N，簇內(nèi)任意節(jié)點(diǎn)的解碼狀態(tài)對應(yīng)AMP 的狀態(tài)sr。

改進(jìn)Gauss-Jordan 算法的解碼AMP 模型如圖4 所示。為了合理估算簇內(nèi)任意節(jié)點(diǎn)的平均解碼時延，AMP 的初始狀態(tài)設(shè)置為廣播階段完成后簇內(nèi)任意節(jié)點(diǎn)成功接收到的數(shù)據(jù)包個數(shù)期望。因此，sk為節(jié)點(diǎn)協(xié)作階段解碼矩陣CP秩的初始值，且，其中?為取整運(yùn)算。AMP 的吸收態(tài)為CP滿秩狀態(tài)sN，因此此狀態(tài)下轉(zhuǎn)移概率pN,N=1。為了求解AMP 的狀態(tài)轉(zhuǎn)移矩陣以分析平均時延，本文接下來給出一些基礎(chǔ)的定理。

圖4 改進(jìn)Gauss-Jordan 算法的解碼AMP 模型

引理1[20]對于一個n×n矩陣M，若其矩陣元素均從有限域GF(q)上隨機(jī)選取，且選取值為0 的概率為1?p，選取GF(q)上任意非0 元的概率為p/(q?1)，則矩陣M非奇異的概率至少為其中π=max{p/(q?1),1 ?p}。

證明見參考文獻(xiàn)[20]“Theorem 6.3”。

推論 1在 CR 協(xié)作恢復(fù)階段采用改進(jìn)Gauss-Jordan 算法解碼，協(xié)作簇內(nèi)任意節(jié)點(diǎn)的解碼矩陣記為CP，若某時間片編碼矩陣CP秩為t，則后續(xù)時間片該節(jié)點(diǎn)若成功接收一個新的編碼包，更新解碼矩陣為CP'后，解碼矩陣CP'秩增為t+1 的概率為

其中，esr是CR 廣播階段數(shù)據(jù)包平均刪除率。

證明詳見附錄3。

由于尋找p(t,N)的精確解一直是數(shù)論領(lǐng)域的一個待解難題，尚未尋找到其解析解[21]，在下文AMP 的狀態(tài)轉(zhuǎn)移概率分析中，本文采用推論1 的結(jié)論來近似p(t,N)，即

基于此，本文分析協(xié)作恢復(fù)階段任意節(jié)點(diǎn)解碼過程AMP 的任意兩狀態(tài)間的轉(zhuǎn)移概率。

引理2在CR 協(xié)作恢復(fù)階段采用Gauss-Jordan算法解碼，若協(xié)作階段編碼包刪除率為erd，則間隔一個時間片簇內(nèi)任意節(jié)點(diǎn)的馬爾可夫過程由當(dāng)前狀態(tài)si轉(zhuǎn)移至狀態(tài)sj的概率pi,j為

證明詳見附錄4。

引理2 給出了AMP 任意兩狀態(tài)轉(zhuǎn)移概率，將它作為矩陣元素容易得到AMP 的一步狀態(tài)轉(zhuǎn)移概率矩陣P，按標(biāo)準(zhǔn)型[22]分塊排列后形如

其中，P的第一行和第一列對應(yīng)AMP 吸收態(tài)sn，其余行列按次序分別對應(yīng)瞬時態(tài)sk,…,sn?1，(n?k) ×(n?k)矩陣Q為所有瞬時態(tài)間的一步轉(zhuǎn)移概率矩陣。接下來，本文將根據(jù)P和吸收馬爾可夫鏈性質(zhì)估算出改進(jìn)Gauss-Jordan 算法AMP 從初始態(tài)sk轉(zhuǎn)移至吸收態(tài)sn的平均步數(shù)，而AMP 每移動一步均消耗一個時間片，即可得到改進(jìn)Gauss-Jordan 算法的平均解碼時延。

定理3M個節(jié)點(diǎn)在CR 協(xié)作階段采用改進(jìn)Gauss-Jordan 算法恢復(fù)N個源數(shù)據(jù)包，其在線解碼過程平均時延T=(I?Q)?1，其中I為單位陣，Q為所有瞬時態(tài)間的一步轉(zhuǎn)移概率矩陣。

證明詳見附錄5。

由于改進(jìn)Gauss-Jordan 算法總時延TGauss-Jordan包括固定的廣播階段時延Tbroad(Tbroad=N)和協(xié)作階段在線解碼時延兩部分，由定理3 得

因此，在解碼時延方面改進(jìn)Gauss-Jordan 算法明顯優(yōu)于傳統(tǒng)高斯方法（TGaussian=N+M），且只有在最壞情況即解碼失敗時才會等于傳統(tǒng)高斯方法。

7.2 算法復(fù)雜度對比分析

采用傳統(tǒng)Gauss 方法解碼時，解碼過程發(fā)生在兩階段CR 傳輸過程結(jié)束后，在解碼時需將兩階段接收到的所有編碼包聯(lián)立方程組求解。由伯努利過程性質(zhì)知，具有M個節(jié)點(diǎn)的協(xié)作簇，任意節(jié)點(diǎn)在廣播階段平均收到N個源數(shù)據(jù)包中的Nesr個，在協(xié)作恢復(fù)階段平均收到(M?1)erd個編碼包，因此基于高斯消去的 Gauss 方法的解碼時間復(fù)雜度為O((esrN+erd(M?1))3)。

本文所提出的改進(jìn)Gauss-Jordan 算法在協(xié)作恢復(fù)階段，每個時間片成功接收到新的編碼包后會執(zhí)行一次消元處理，這樣的消元處理共有（N?esrN）次。由算法1 知，協(xié)作階段若第i次收到編碼數(shù)據(jù)包，則第i次消元運(yùn)算規(guī)模為(esrN+i)2次，因此改進(jìn)Gauss-Jordan 算法的總時間復(fù)雜度為即與Gauss 方法對比，2 種解碼方法均為多項式復(fù)雜度，但改進(jìn)Gauss-Jordan 算法復(fù)雜度較小，且問題規(guī)模不受協(xié)作簇節(jié)點(diǎn)數(shù)影響，更適應(yīng)于大范圍的部署應(yīng)用。

8 數(shù)值結(jié)果

本節(jié)通過數(shù)值模擬與實際部署相結(jié)合的思路來檢驗上文給出的結(jié)論和算法。仿真過程采用控制變量法，控制編碼有限域階數(shù)、協(xié)作節(jié)點(diǎn)數(shù)、源數(shù)據(jù)包數(shù)、兩階段信道刪除率等多種變量參數(shù)，檢驗CR 過程結(jié)果并與上文結(jié)論進(jìn)行對比。例如，對于解碼成功率檢測實驗，通過實驗協(xié)作網(wǎng)絡(luò)內(nèi)任意目標(biāo)節(jié)點(diǎn)解碼出所有源節(jié)點(diǎn)數(shù)據(jù)包的概率，再與式(13)給出的理論上界Pmax和式(15)給出的理論下界Pmin進(jìn)行對比驗證。為了降低誤差，每組實驗均運(yùn)行了106次?？山庑岳碚撋舷陆珧炞C實驗參數(shù)設(shè)置如表3 所示。

表3 可解性理論上下界驗證實驗參數(shù)設(shè)置

首先，實驗編碼有限域階對目標(biāo)節(jié)點(diǎn)線性可解性的影響。固定源數(shù)據(jù)包數(shù)N=10，協(xié)作節(jié)點(diǎn)數(shù)M=15，節(jié)點(diǎn)廣播信道刪除率esr=0.5和協(xié)作信道刪除率均為erd=0.5，當(dāng)編碼有限域Fq階q變化范圍為2～216時，簇內(nèi)節(jié)點(diǎn)經(jīng)過CR 過程解碼成功率如圖5 所示。

圖5 編碼有限域階對解碼成功率的影響

從圖5 可以發(fā)現(xiàn)，在不同編碼有限域階下，所提出的理論上下界均有效，并且當(dāng)編碼有限域階小于24時，隨著有限域階的增加，節(jié)點(diǎn)解碼成功率迅速上升，這一趨勢在編碼階處于24～28時會變緩，而當(dāng)編碼階大于28時，編碼有限域選擇不再對線性可解性和理論上下界產(chǎn)生明顯影響（編碼有限域階從28增加到216，但解碼成功率僅從0.788增加到0.794）。這說明編碼有限域階選取過小會造成CR 機(jī)制可解性差，而當(dāng)有限域階超過一定值時就不再成為可解性的主要約束因素，因此設(shè)計具體CR 機(jī)制需要在考慮編解碼效率基礎(chǔ)上合理地選擇編碼有限域。

在此基礎(chǔ)上，進(jìn)一步實驗所提出的改進(jìn)Gauss-Jordan 算法在不同編碼有限域下的漸進(jìn)解碼算法解碼時延，實驗時維持源數(shù)據(jù)包數(shù)、協(xié)作節(jié)點(diǎn)數(shù)、廣播信道刪除率均與圖5 所示實驗一致，實驗結(jié)果如圖6 所示。結(jié)果顯示，在同一個編碼有限域下，隨著協(xié)作階段數(shù)據(jù)包刪除率增加，解碼時延明顯遞增，最終趨近于傳統(tǒng)Gauss 方法解碼時延。這是由于隨著協(xié)作刪除率增加，節(jié)點(diǎn)的線性可解性下降直至解碼失敗。橫向?qū)Ρ炔煌蛟谀骋粋€協(xié)作信道刪除率下的解碼時延可以發(fā)現(xiàn)，編碼有限域階越小，解碼時延越大，但當(dāng)編碼有限域階大于28時，編碼有限域階對解碼時延影響變?nèi)?，如圖6 中28和216這2 種編碼有限域，雖然編碼有限域階擴(kuò)大了一倍，但平均解碼時延僅降低了0.1，該現(xiàn)象說明合理提高編碼有限域階能夠增加CR 機(jī)制的協(xié)作過程解碼成功率，降低解碼時延，但當(dāng)編碼有限域階超過一定閾值時，則提升效果有限。

圖6 改進(jìn)Gauss-Jordan 算法與傳統(tǒng)Gauss 方法解碼時延比較

由7.2 節(jié)算法復(fù)雜性分析可知，2 種解碼算法的復(fù)雜性主要受到源數(shù)據(jù)包數(shù)N、協(xié)作節(jié)點(diǎn)數(shù)M和節(jié)點(diǎn)廣播信道刪除率esr決定，而網(wǎng)絡(luò)編碼運(yùn)算是基于有限域的運(yùn)算，在實際節(jié)點(diǎn)上的運(yùn)行復(fù)雜度還受到具體有限域運(yùn)算實現(xiàn)方法影響。為了對比2 種解碼算法的計算復(fù)雜度，基于一維查找表和二維查找表2 種有限域?qū)嵤┓椒╗23]分別實現(xiàn)了2 種解碼算法，并部署在 Freescale MC13213 節(jié)點(diǎn)上（MC13213 是 Freescale 生產(chǎn)的一種基于經(jīng)典HCS08 系列微程序控制器的RF 片上系統(tǒng)（SiP），在WPAN、ZigBee 等各類無線組網(wǎng)應(yīng)用領(lǐng)域得到廣泛使用）。實驗時關(guān)閉了節(jié)點(diǎn)天線，并通過隨機(jī)函數(shù)來模擬CR 過程中是否成功接收到編碼數(shù)據(jù)包（對天線的收發(fā)處理需要處理器的介入，而解碼算法復(fù)雜度本身與天線編碼包接收過程獨(dú)立。因此，不關(guān)閉天線會造成算法復(fù)雜度測試結(jié)果不準(zhǔn)確），具體實驗參數(shù)設(shè)置如表4 所示。在節(jié)點(diǎn)上共執(zhí)行了4 組對比實驗，每次實驗均編碼32 KB的隨機(jī)數(shù)據(jù)，每組實驗重復(fù)106次，實驗結(jié)果如圖7 所示。

表4 改進(jìn)Gauss-Jordan 算法復(fù)雜度實驗參數(shù)設(shè)置

圖7 改進(jìn)Gauss-Jordan 算法與傳統(tǒng)Gauss 方法運(yùn)算復(fù)雜度比較

實驗結(jié)果表明，在2 種有限域?qū)崿F(xiàn)方法上本文所提出的改進(jìn)Gauss-Jordan 算法均較傳統(tǒng)Gauss 方法復(fù)雜度低約35%，這是因為改進(jìn)算法的消元迭代次數(shù)較少。同時也能發(fā)現(xiàn)，有限域階對2 種解碼算法的復(fù)雜度影響較明顯，這是因為有限域階對有限域運(yùn)算方法的RAM 存儲需求差異顯著。對于一維查表法，在24階有限域上共需要設(shè)置96 B 的指數(shù)表和對數(shù)表，而28域則需要4 160 B；同樣，對于二維查表法，在24階域上共需要設(shè)置528 B 的指數(shù)表和乘、除法表，而28域需要超過128 KB 閃存空間。相較于有限域的一維查表實現(xiàn)法，2 種解碼算法在二維查表法下運(yùn)算效率提升顯著，但二維表法的RAM存儲需求較高，尤其是對于需要高階有限域的CR協(xié)作過程，本質(zhì)上來說，有限域的二維查表實現(xiàn)就是一種以存儲空間來換取運(yùn)算效率的方法。

接下來，本文仿真實驗廣播階段數(shù)據(jù)包刪除率對目標(biāo)節(jié)點(diǎn)線性可解性的影響。設(shè)置廣播信道的刪除率esr變化范圍為0.1～0.9、編碼有限域固定為GF(24)、交互階段數(shù)據(jù)包的刪除率固定為erd=0.4，當(dāng)源數(shù)據(jù)包個數(shù)N=10、協(xié)作節(jié)點(diǎn)數(shù)M=15時，實驗結(jié)果如圖8 所示。從實驗網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)解碼成功率對比上，仿真結(jié)果曲線落在下界曲線和上界曲線之間，并且更逼近下界。例如在編碼有限域為GF(24)的情況下，理論下界與實際結(jié)果誤差區(qū)間僅為0.83%。統(tǒng)計發(fā)現(xiàn)，上界平均誤差區(qū)間為19.46%，在首尾端較緊密。這是由于隨著廣播信道刪除率增加，當(dāng)esr超過0.35 時協(xié)作節(jié)點(diǎn)的編碼向量稀疏度會急速增大，引起由定理1 作用的理論上界松弛度擴(kuò)大，這一過程會持續(xù)到esr=0.7 時，此時理論上界會切換到由式(10)所形成的約束，緊密度會得到提高。

圖8 廣播階段數(shù)據(jù)包刪除率對目標(biāo)節(jié)點(diǎn)線性可解性的影響

最后，分析源數(shù)據(jù)包數(shù)和協(xié)作簇內(nèi)節(jié)點(diǎn)數(shù)對線性可解性上下界影響。固定廣播信道刪除率固定為esr=0.7，協(xié)作信道刪除率固定為erd=0.4，編碼有限域為GF(24)，分別考察源數(shù)據(jù)包數(shù)N為5～15、協(xié)作簇內(nèi)節(jié)點(diǎn)數(shù)M為10～25 時的解碼成功率，實驗結(jié)果分別如圖9 和圖10 所示。實驗發(fā)現(xiàn)，本文所提出的改進(jìn)Gauss-Jordan 算法的上下界在不同源數(shù)據(jù)包數(shù)、協(xié)作簇內(nèi)節(jié)點(diǎn)數(shù)下均能夠較精確地估算解碼成功率，并且當(dāng)CR 機(jī)制各性能參數(shù)固定時，源數(shù)據(jù)包數(shù)和協(xié)作節(jié)點(diǎn)數(shù)對線性解碼率影響較大，說明傳輸策略和節(jié)點(diǎn)協(xié)作簇建立策略是CR 機(jī)制的重要內(nèi)容。同時實驗也驗證了一個直觀結(jié)論，即在相同的信道條件下，中繼節(jié)點(diǎn)數(shù)越大，節(jié)點(diǎn)的解碼成功率越大；源數(shù)據(jù)包數(shù)越小，節(jié)點(diǎn)的解碼成功率越大。

圖9 協(xié)作節(jié)點(diǎn)數(shù)對線性可解性的影響

9 結(jié)束語

線性可解性是基于網(wǎng)絡(luò)編碼的CR 機(jī)制應(yīng)用中的關(guān)鍵基礎(chǔ)問題，本文建立了CR 可解性的量化分析模型，并給出了緊密的理論上下界。在此基礎(chǔ)上設(shè)計了一種在線判定算法，降低了節(jié)點(diǎn)可解性識別的等待時延。下一步的工作可分成兩個方向：一方面繼續(xù)探索線性可解性精確解，鑒于該問題求解難度和稀疏隨機(jī)矩陣的線性可解性探索等效，是數(shù)論領(lǐng)域待解難題，一個可行的解決思路是利用蒙特卡洛方法使用計算機(jī)實驗出一個精確解再尋求理論驗證；另一方向是基于本文所提出的理論上下界和漸進(jìn)解碼算法，設(shè)計流式協(xié)作恢復(fù)機(jī)制，實現(xiàn)廣播和恢復(fù)兩階段的流水線聯(lián)動，完成數(shù)據(jù)包的數(shù)據(jù)的在線編碼傳輸功能，進(jìn)一步在提高網(wǎng)絡(luò)傳輸可靠性的同時降低CR 恢復(fù)時延。

附錄1 定理1的證明

證明根據(jù)式(8)知因此可以通過判斷(M? 1) ×(N?k)矩陣C'所有列向量是否均線性無關(guān)來估算界。若假設(shè)C'的前j(j=1,2,…,N?k?1)個列向量c1,c2,…,cj已被證明線性獨(dú)立，則當(dāng)且僅當(dāng)cj+1不在這些向量所張成的線性子空間Vj中時，第j+1個列向量cj+1與這些向量線性無關(guān)。記其概率為pj+1，則根據(jù)增量思想C'的所有N?k個列向量均線性無關(guān)的概率可表示為因此問題關(guān)鍵在于求解pj+1。

考慮C'中前j個列向量c1,c2,…,cj形成的矩陣，由于這j個列向量線性無關(guān)，因此可以通過矩陣的初等列變換，類似高斯消去，形成存在j×j單位陣的變換陣。不失一般性，本文假設(shè)C'前j行形成了新陣的單位陣。因為初等列變換不改變空間的基，所以新陣的列向量張成的線性子空間與原空間Vj相同。由于新陣的列向量構(gòu)成了子空間Vj的一組基，因此容易發(fā)現(xiàn)屬于子空間的所有向量前j個系數(shù)可以任意取值，而其余(M? 1)?j個系數(shù)取值由前j個系數(shù)唯一確立。又由式(9)知C'里任意元素取域Fq中0 元的概率為erd+(1?erd)esr，且任意一個非0 元概率為(1?esr)(1?erd)/(q? 1)，因此向量cj+1落在Vj里的概率pj+1至多為1?η(M?1)?j，從而定理1 得證。

附錄2 定理2的證明

證明由式(8)可知

其中，θ≠ 0(θ∈Fq)。從式(20)可以整理得

將式(23)代入式(18)，定理2 即可得證。

附錄3 推論1 的證明

證明由式(9)知，在協(xié)作恢復(fù)階段，任意簇內(nèi)節(jié)點(diǎn)成功接收到的編碼包編碼系數(shù)是一個1×N維的稀疏向量，該向量的稀疏度即為廣播階段數(shù)據(jù)包刪除率esr。當(dāng)簇內(nèi)節(jié)點(diǎn)成功接收到一個新編碼包后，解碼矩陣秩由t增加為t+1，這一過程等價于新接收的編碼包編碼系數(shù)向量c與由原秩為t解碼陣CP的行向量所組成的向量組線性無關(guān)。根據(jù)算法1 可知，秩為t的解碼陣CP共含t行向量且呈行階梯型分布，因此當(dāng)c與CP階梯對應(yīng)的前t個元素值確立后，稀疏隨機(jī)向量c與CP是否線性相關(guān)取決于剩余的N?t個元素，且線性相關(guān)時的解取值唯一，代入引理1，推論1 即可得證。

附錄4 引理2的證明

證明若簇內(nèi)任意節(jié)點(diǎn)CRi在當(dāng)前時間片末（假設(shè)為t）的解碼矩陣秩為i（此時對應(yīng)圖4 所示的解碼過程吸收馬爾可夫鏈應(yīng)處于si狀態(tài)），則在第t+1 時間片末CRi的解碼矩陣秩只可能出現(xiàn)2 種情況。

情況1秩增1 變?yōu)閕+1。這種情況發(fā)生的條件是CRi在t+1 時間片成功接收到一個編碼包，并且該編碼包的編碼系數(shù)向量與原解碼矩陣線性無關(guān)，此時AMP 由si轉(zhuǎn)移至狀態(tài)si+1，因此這種情況的轉(zhuǎn)移概率pi,i+1=(1?erd)p(i,N)。

情況2秩維持i不變。這種情況發(fā)生有2 種可能，一種是CRi在t+1 時間片未能成功偵聽到一個編碼包，即發(fā)生了刪除；另一種是成功接收到編碼包但是編碼系數(shù)與已有編碼矩陣線性相關(guān)，因此這種情況的轉(zhuǎn)移概率pi,i=erd+(1?erd) (1?p(i,N))=1 ? (1?erd)p(i,N)，引理2 得證。

附錄5 定理3 的證明

證明由M個節(jié)點(diǎn)組成的 CR 協(xié)作簇采用改進(jìn)Gauss-Jordan 算法恢復(fù)N個源數(shù)據(jù)包，其成功解碼過程包括2 種情況。

情況1由于CR 協(xié)作恢復(fù)階段總時長只有M個時間片，改進(jìn)Gauss-Jordan 算法需在此時間片內(nèi)判定解碼矩陣是否可解，超過M則終止算法，因此解碼時延

情況2對任意吸收馬爾可夫鏈AMP 從瞬時態(tài)si出發(fā)至吸收態(tài)時經(jīng)過瞬態(tài)sj的平均次數(shù)Yij為

若記任意AMP 瞬時狀態(tài)轉(zhuǎn)移矩陣為Q，由式(24)得Yij是聯(lián)合矩陣I+Q+Q2+Q3+…的(i,j)元素，又

根據(jù)瞬時態(tài)轉(zhuǎn)移特性知，當(dāng)n→∞時任意AMP 的n步轉(zhuǎn)移概率陣極限，因此I+Q+Q2+Q3+…=(I?Q)?1，即Yij是(I?Q)?1的(i,j)元素，若記T=(I?Q)?1，則Yij=Tij。

記Si表示任意AMP 從瞬時態(tài)si到達(dá)吸收態(tài)的平均步數(shù)，Sij表示到達(dá)吸收態(tài)前經(jīng)過瞬時態(tài)sj的次數(shù)，則