[發(fā)明專利]一種基于噴泉碼的網(wǎng)絡(luò)編碼方法

無效

• 申請?zhí)枺?/td>: 200910085527.8
• 申請日: 2009-05-25
• 公開（公告）號: CN101567755A
• 公開（公告）日: 2009-10-28
• 發(fā)明（設(shè)計(jì)）人: 安建平;袁磊;李祥明;楊靜
• 申請（專利權(quán)）人: 北京理工大學(xué)
• 主分類號: H04L1/00
• 分類號: H04L1/00;H03M13/00
• 代理公司: 北京理工大學(xué)專利中心
• 代理人: 張利萍

技術(shù)領(lǐng)域

本發(fā)明涉及一種在無線通信網(wǎng)絡(luò)中實(shí)現(xiàn)可靠網(wǎng)絡(luò)編碼的方法，屬于通訊編 碼技術(shù)領(lǐng)域。

背景技術(shù)

2000年，李彥碩和蔡寧等人在IEEE信息論匯刊上發(fā)表了題為“網(wǎng)絡(luò)信息流” 的文章，提出了網(wǎng)絡(luò)編碼的概念。根據(jù)網(wǎng)絡(luò)編碼的理論，對于一個(gè)多節(jié)點(diǎn)的通 信網(wǎng)絡(luò)，如果允許各節(jié)點(diǎn)對多條輸入信道上的信息進(jìn)行一定的線性或非線性操 作(編碼)，然后再轉(zhuǎn)發(fā)出去，則該網(wǎng)絡(luò)的組播傳輸速率可以達(dá)到最大流最小割 定理所決定的網(wǎng)絡(luò)容量的上限。網(wǎng)絡(luò)編碼理論激發(fā)了人們對網(wǎng)絡(luò)信息論新的研 究興趣。研究發(fā)現(xiàn)，網(wǎng)絡(luò)編碼不但能夠節(jié)約網(wǎng)絡(luò)的帶寬資源，還可以節(jié)約終端 節(jié)點(diǎn)能量消耗、均衡網(wǎng)絡(luò)負(fù)載、提高網(wǎng)絡(luò)的魯棒性、提升網(wǎng)絡(luò)的安全性等。最 近十年，人們對網(wǎng)絡(luò)編碼理論進(jìn)行了大量研究，提出了很多有價(jià)值的理論和方 法。

人們在研究網(wǎng)絡(luò)編碼的時(shí)候，隱含地使用了一條重要假設(shè)：網(wǎng)絡(luò)中各節(jié)點(diǎn) 之間的信道是可靠的。對于Internet或電話骨干網(wǎng)絡(luò)，由于傳輸?shù)目煽啃愿撸? 這樣的假設(shè)與實(shí)際相符。然而，一個(gè)實(shí)際的無線網(wǎng)絡(luò)，各節(jié)點(diǎn)之間的鏈路不如 有線鏈路可靠，允許節(jié)點(diǎn)對輸入的各支路數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)編碼再轉(zhuǎn)發(fā)，確實(shí)能夠 實(shí)現(xiàn)最大流最小割理論指出的組播容量，但使用編碼轉(zhuǎn)發(fā)，各轉(zhuǎn)發(fā)節(jié)點(diǎn)的一個(gè) 輸入差錯(cuò)會(huì)由于編碼造成多個(gè)輸出支路輸出數(shù)據(jù)出現(xiàn)差錯(cuò)，此差錯(cuò)還會(huì)繼續(xù)沿 著網(wǎng)絡(luò)向下游擴(kuò)散。這種差錯(cuò)擴(kuò)散帶來的可靠性下降會(huì)削弱甚至很快超過使用 網(wǎng)絡(luò)編碼有效性提高的好處。為了降低網(wǎng)絡(luò)編碼對每段鏈路傳輸可靠性的要求， 人們提出了基于網(wǎng)絡(luò)編碼的差錯(cuò)控制技術(shù)。基于網(wǎng)絡(luò)編碼的差錯(cuò)控制是針對網(wǎng) 絡(luò)、而非一條鏈路或一條路徑進(jìn)行操作的。這種網(wǎng)絡(luò)編碼差錯(cuò)控制是一種比較 新的差錯(cuò)控制方式，但使用此方式構(gòu)造糾錯(cuò)編碼，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較多時(shí)，糾錯(cuò) 碼需要在很大的有限域下進(jìn)行構(gòu)造。因而這種碼的編碼復(fù)雜度和譯碼復(fù)雜度都 非常高。

數(shù)字噴泉碼是一種應(yīng)用于刪除信道的糾錯(cuò)編碼技術(shù)。噴泉編碼的典型應(yīng)用 包括無線組播和廣播業(yè)務(wù)、無線協(xié)作與中繼、分布式網(wǎng)絡(luò)存儲(chǔ)等。數(shù)字噴泉編 碼的基本思想是，在發(fā)送端，使用無比率編碼方法將K個(gè)信源數(shù)據(jù)包編成半無窮 數(shù)據(jù)包序列再進(jìn)行發(fā)送。每一個(gè)接收點(diǎn)正確接收到K個(gè)編碼包(或者略大于K個(gè) 編碼包)即可解出原發(fā)送的K個(gè)信源數(shù)據(jù)包。接收機(jī)正確譯出所發(fā)送K個(gè)源數(shù)據(jù) 包后，即向發(fā)送機(jī)發(fā)送單次確認(rèn)信號。使用數(shù)字噴泉技術(shù)，不論接收點(diǎn)收到哪K 個(gè)編碼數(shù)據(jù)包，也不論接收到的這K個(gè)數(shù)據(jù)包順序如何，接收端都能夠正確地譯 出源數(shù)據(jù)包序列。噴泉編碼應(yīng)用到無線組播業(yè)務(wù)，與傳統(tǒng)的反饋重傳技術(shù)相比 不但可大大減小反饋開銷，更重要的是，這種方法能夠顯著提高數(shù)據(jù)吞吐能力。

網(wǎng)絡(luò)編碼和噴泉碼都可應(yīng)用于組播系統(tǒng)提高網(wǎng)絡(luò)的數(shù)據(jù)吞吐能力，但二者 各自獨(dú)立應(yīng)用于無線衰落環(huán)境下的多節(jié)點(diǎn)分布式網(wǎng)絡(luò)，都具有其自身的局限， 因此，有必要融合網(wǎng)絡(luò)編碼和數(shù)字噴泉編碼，研究無線信道環(huán)境下新型網(wǎng)絡(luò)糾 錯(cuò)編碼方法，同時(shí)實(shí)現(xiàn)最大流最小割決定的網(wǎng)絡(luò)容量以及有噪有擾衰落信道的 信道容量。

發(fā)明內(nèi)容

本發(fā)明的目的在于將網(wǎng)絡(luò)編碼與噴泉編碼相結(jié)合，提供一種基于噴泉碼的 網(wǎng)絡(luò)編碼方法，能夠在無線網(wǎng)絡(luò)中實(shí)現(xiàn)高效、可靠的數(shù)據(jù)傳輸。

本發(fā)明的目的是通過下述技術(shù)方案實(shí)現(xiàn)的。

一種基于噴泉碼的網(wǎng)絡(luò)編碼方法，其具體步驟如下：

步驟一、對信源進(jìn)行噴泉編碼

對包含K個(gè)信源符號的信源進(jìn)行第一級噴泉編碼，產(chǎn)生K個(gè)第一級噴泉編 碼符號。假定要往N個(gè)中間節(jié)點(diǎn)傳輸，將K個(gè)第一級噴泉編碼符號按照N個(gè)傳 輸信道的容量大小關(guān)系劃分為N個(gè)子集。

步驟二、將第一級噴泉編碼符號構(gòu)成的N個(gè)子集再以噴泉編碼的方式向N 個(gè)中間節(jié)點(diǎn)傳輸。

假定要往第n個(gè)中間節(jié)點(diǎn)(n∈{1，…，N})傳輸K_n(1≤K_n≤K)個(gè)第一級噴泉 編碼符號，則把這K_n個(gè)第一級噴泉編碼符號當(dāng)作新的信源符號進(jìn)行第二級的噴 泉編碼，然后向第n個(gè)中間節(jié)點(diǎn)傳輸。

步驟三、對中間節(jié)點(diǎn)進(jìn)行噴泉譯碼

當(dāng)?shù)趎個(gè)中間節(jié)點(diǎn)接收到K_n個(gè)第二級噴泉編碼符號后，進(jìn)行噴泉譯碼，可 以采用BP譯碼算法或者高斯消元算法。當(dāng)譯碼成功時(shí)，中間節(jié)點(diǎn)向發(fā)送節(jié)點(diǎn)發(fā) 送一個(gè)譯碼成功的確認(rèn)信號。

步驟四、對中間節(jié)點(diǎn)進(jìn)行噴泉編碼