[發(fā)明專利]一種Ad Hoc網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由方法

無效

• 申請?zhí)枺?/td>: 201110394736.8
• 申請日: 2011-12-02
• 公開（公告）號: CN102547856A
• 公開（公告）日: 2012-07-04
• 發(fā)明（設(shè)計(jì)）人: 孫寶林;桂超;宋鶯;余慶春;黃曉武
• 申請（專利權(quán)）人: 湖北經(jīng)濟(jì)學(xué)院
• 主分類號: H04W28/08
• 分類號: H04W28/08;H04W40/02
• 代理公司: 武漢開元知識產(chǎn)權(quán)代理有限公司 42104
• 代理人: 潘杰

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

本發(fā)明屬于無線移動(dòng)Ad?Hoc網(wǎng)絡(luò)技術(shù)領(lǐng)域，具體為一種Ad?Hoc網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由方法，主要適用于Ad?Hoc網(wǎng)絡(luò)中多路徑路由的發(fā)現(xiàn)和數(shù)據(jù)傳輸路徑的選擇，有利于提高Ad?Hoc網(wǎng)絡(luò)的系統(tǒng)性能。?

背景技術(shù)

2000年，香港中文大學(xué)的幾位教授(R.Ahlswede，蔡寧，李碩彥和楊偉豪)在其著名論文“Network?Information?Flow”(R.Ahlswede，N.Cai，S.-Y.R.Li，and?R.W.Yeung.Network?information?flow.IEEETransactions?on?Information?Theory，2000，46(4)：1204-1216)中創(chuàng)造性地提出了“網(wǎng)絡(luò)編碼(Network?Coding，NC)”新概念，首次將網(wǎng)絡(luò)編碼與路由技術(shù)有機(jī)地融合為一體，建立了一種全新的網(wǎng)絡(luò)體系結(jié)構(gòu)，不僅解決了廣播路由這一信息論中的經(jīng)典難題，而且從理論上證明了網(wǎng)絡(luò)編碼可以達(dá)到最大傳輸容量和效率，其精髓來自于圖論中著名的Max-flow?Min-cut理論。?

2003年，李碩彥，楊偉豪和蔡寧又發(fā)表了著名論文“Linear?Network?Coding”(S.-Y.R.Li，R.W.Yeung，N.Cai.Linear?network?coding.IEEE?Transactions?on?Information?Theory，2003，49(2)：371-381)，指出線性網(wǎng)絡(luò)編碼可以達(dá)到多播傳輸?shù)淖畲笕萘俊ｋS后的研究成果構(gòu)建了網(wǎng)絡(luò)編碼的最基本框架，從此，網(wǎng)絡(luò)編碼成為了世界各位知名大學(xué)和實(shí)驗(yàn)室最熱門的研究領(lǐng)域之一。網(wǎng)絡(luò)編碼改變了傳統(tǒng)網(wǎng)絡(luò)中中間節(jié)點(diǎn)僅充當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)的特點(diǎn)，中間節(jié)點(diǎn)能夠?qū)π枰D(zhuǎn)發(fā)的信息?進(jìn)行相關(guān)的編碼，在接收節(jié)點(diǎn)處可以完成相關(guān)的解碼功能，從而還原信息本身。?

2005年，Katti等學(xué)者提出的COPE協(xié)議是第一個(gè)將網(wǎng)絡(luò)編碼應(yīng)用到實(shí)際網(wǎng)絡(luò)中的編碼協(xié)議，實(shí)驗(yàn)結(jié)果證明，此編碼協(xié)議顯著地提高了網(wǎng)絡(luò)吞吐量。2010年Yuan等學(xué)者(Yuan?Yuan，Kui?Wu，Weijia?Jia，and?Yuming?Jiang.Performance?of?Acyclic?Stochastic?Networks?with?Network?Coding.IEEE?Transactions?on?Parallel?and?Distributed?Systems，08?Nov.2010，DOI：10.1109/TPDS.2010.192)基于非周期性隨機(jī)網(wǎng)絡(luò)與網(wǎng)絡(luò)編碼也進(jìn)行了性能比較，并指出：與ARQ協(xié)議相比，網(wǎng)絡(luò)編碼明顯減少數(shù)據(jù)包重傳次數(shù)；這些性能分析比較說明網(wǎng)絡(luò)編碼技術(shù)對于無線網(wǎng)絡(luò)具有較好的特性。網(wǎng)絡(luò)編碼的思想是指網(wǎng)絡(luò)中的節(jié)點(diǎn)不再局限于只能對收到的信息進(jìn)行存儲和轉(zhuǎn)發(fā)，突破了傳統(tǒng)數(shù)據(jù)傳輸?shù)墓潭Ｊ剑梢詫?shí)現(xiàn)網(wǎng)絡(luò)流量的最大化。有了網(wǎng)絡(luò)編碼，傳統(tǒng)的路由方案就可以被看作是一種特殊形式的網(wǎng)絡(luò)編碼，只不過在這種方式下，節(jié)點(diǎn)的輸出是接收到的信息的排列。?

現(xiàn)有的Ad?Hoc網(wǎng)絡(luò)多路徑路由機(jī)制都在路由發(fā)現(xiàn)階段預(yù)先確定了傳輸路徑，沒有考慮到數(shù)據(jù)包傳輸過程中存在的網(wǎng)絡(luò)編碼機(jī)制。這些多路徑路由機(jī)制沒有很好地發(fā)揮利用網(wǎng)絡(luò)編碼機(jī)制的優(yōu)勢，因此網(wǎng)絡(luò)的吞吐量沒有被充分地發(fā)揮出來。?

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

本發(fā)明的目的是在現(xiàn)有的Ad?Hoc網(wǎng)絡(luò)多路由方法的基礎(chǔ)上，提供一種在關(guān)健節(jié)點(diǎn)上利用網(wǎng)絡(luò)編碼機(jī)制建立從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的Ad?Hoc網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由方法，以平衡各路徑的網(wǎng)絡(luò)流量，從而實(shí)現(xiàn)最大化地提高網(wǎng)絡(luò)的數(shù)據(jù)吞吐量以及延長網(wǎng)絡(luò)?生存期。?

為了實(shí)現(xiàn)上述目的，本發(fā)明所采用的技術(shù)方案是：?

一種Ad?Hoc網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由方法，其具體步驟為：?

1)確定Ad?Hoc網(wǎng)絡(luò)的多路徑路由方法的網(wǎng)絡(luò)模型?

一個(gè)Ad?Hoc網(wǎng)絡(luò)可表示成一個(gè)加權(quán)圖G(V，E，C)，其中V表示節(jié)點(diǎn)集，E表示連接節(jié)點(diǎn)的通信鏈路集，C表示連接節(jié)點(diǎn)通信鏈路的代價(jià)。|V|和|E|分別表示該網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和鏈路數(shù)。在G中，元素P∈E具有一組有序數(shù)列(v₁，v₂，...，v_m)作為P的屬性，或稱為弧P的權(quán)，用C來計(jì)算。假定從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的路徑可以用(v₁，v₂，...，v_m)，v₁＝S，v_m＝D表示。?

2)建立交換代數(shù)的網(wǎng)絡(luò)編碼構(gòu)造方法?