（信息與通信工程專業(yè)論文）無線網(wǎng)絡(luò)編碼及其安全性研究.pdf

南京郵電大學(xué)碩士研究生學(xué)位論文摘要 摘要 網(wǎng)絡(luò)編碼是一種新穎的網(wǎng)絡(luò)傳輸技術(shù) 它從網(wǎng)絡(luò)總體或系統(tǒng)性的角度出發(fā) 能有效解 決最大流量 路由策略等問題 網(wǎng)絡(luò)編碼可以利用其在網(wǎng)絡(luò)節(jié)點(diǎn)上對(duì)所要求傳送的消息作 適當(dāng)?shù)木€性或非線性處理來改善網(wǎng)絡(luò)的傳輸效率 可靠性 魯棒性 安全性 節(jié)點(diǎn)能耗等 性能 是有別于傳統(tǒng)方法的一種新的思路 因而受到高度重視 成為當(dāng)前網(wǎng)絡(luò)信息論中一 個(gè)重要的研究方向 與多數(shù)技術(shù)一樣 網(wǎng)絡(luò)編碼在充分利用網(wǎng)絡(luò)理論組播速率的同時(shí) 也 伴隨著對(duì)應(yīng)的開銷 如何在應(yīng)用網(wǎng)絡(luò)編碼技術(shù)充分利用網(wǎng)絡(luò)傳輸能力的同時(shí) 盡可能地減 少付出的各種開銷 是網(wǎng)絡(luò)編碼在實(shí)際應(yīng)用中所要解決的重要問題 本文首先對(duì)網(wǎng)絡(luò)編碼進(jìn)行了綜述 介紹了它的理論背景 研究概況和發(fā)展趨勢 重點(diǎn) 討論了當(dāng)前它在無線網(wǎng)絡(luò)中的一些應(yīng)用及優(yōu)勢 并針對(duì)其中一種基于稀疏網(wǎng)絡(luò)編碼的p 2 p 內(nèi)容分發(fā)算法進(jìn)行了詳細(xì)研究和仿真驗(yàn)證 仿真實(shí)驗(yàn)表明 與一般網(wǎng)絡(luò)編碼相比 稀疏網(wǎng) 絡(luò)編碼能夠減小分發(fā)系統(tǒng)中編碼分塊的線性相關(guān)性 降低編碼計(jì)算復(fù)雜度 并且解碼成功 率較高 與無編碼的分發(fā)系統(tǒng)相比 基于稀疏網(wǎng)絡(luò)編碼的分發(fā)系統(tǒng)在吞吐量 平均下載時(shí) 間和總分發(fā)時(shí)間等方面的性能都要優(yōu)于前者 雖然在多數(shù)需要承載廣播業(yè)務(wù)的網(wǎng)絡(luò)中 網(wǎng)絡(luò)編碼技術(shù)的引入可以提高和改善多項(xiàng)網(wǎng) 絡(luò)性能指標(biāo) 但由于網(wǎng)絡(luò)編碼是在各個(gè)節(jié)點(diǎn)處對(duì)接收的信息進(jìn)行組合后發(fā)送出去 因此數(shù) 據(jù)包在傳遞的過程中很容易被篡改或遭受其他類型的攻擊 信息的安全性遇到了嚴(yán)重的考 驗(yàn) 為此 本文還重點(diǎn)研究了網(wǎng)絡(luò)編碼在安全性方面的應(yīng)用 討論了抵御不同安全攻擊的 網(wǎng)絡(luò)編碼方案 其中以竊聽攻擊為研究重點(diǎn) 同時(shí) 本文還針對(duì)網(wǎng)絡(luò)的外部竊聽攻擊提出 了一種改進(jìn)的安全網(wǎng)絡(luò)編碼方案 從理論上證明了其安全性和可達(dá)性 并證明該方案的計(jì) 算復(fù)雜度較已有方案更低 最后 論文就今后工作的發(fā)展方向提出了一些個(gè)人的觀點(diǎn)和看法 關(guān)鍵詞 網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)安全 安全網(wǎng)絡(luò)編碼 內(nèi)容分發(fā) a b s t r a c t n e t w o r kc o d i n gi sab r a n dn e wi n f o r m a t i o nt r a n s m i s s i o nt e c h n o l o g y w h i c hs o l v e s p r o b l e m ss u c ha sm a xf l o wa n dr o u t i n gs t r a t e g i e si np e r s p e c t i v eo f t h ew h o l en e t w o r ko rs y s t e m n e t w o r kc o d i n ga l l o w st h ei n t e r m e d i a t en o d e st os e n do u tp a c k e t st h a ta r el i n e a ro rn o n l i n e a r c o m b i n a t i o n so fi t sr e c e i v e di n f o r m a t i o n a n d t h u st oi m p r o v et h ep e r f o r m a n c eo ft r a n s m i s s i o n e f f i c i e n c y r e l i a b i l i t y r o b u s t n e s s s e c u r i t ya n de n e r g ye f f i c i e n c y c u r r e n t l y t h er e s e a r c ho f n e t w o r kc o d i n gh a sr e c e i v e dg r e a ti n t e r e s t sa n dh a sb e c o m eo n eo ft h em o s ti m p o r t a n tf i e l d si n n e t w o r ki n f o r m a t i o nt h e o r y h o w e v e r l i k em o s to t h e rt e c h n o l o g i e s t h ea d v a n t a g eo fn e t w o r k c o d i n gg e t sa l o n gw i t hs o m eo v e r h e a d h o w t or e d u c et h e s eo v e r h e a db e c o m e sab i gc h a l l e n g e i nt h i st h e s i s w ef i r s tr e v i e wt h et e c h n o l o g yo fn e t w o r kc o d i n gb yi n t r o d u c i n gi t s t h e o r e t i c a lb a c k g r o u n da n dc u r r e n td e v e l o p m e n t s t h e n w ef o c u so ni t sa p p l i c a t i o n sa n d a d v a n t a g ei nw i r e l e s sn e t w o r k s a d d r e s s i n gt h ep r o b l e mo fp 2 pc o n t e n td i s t r i b u t i o n w e c a r e f u l l ys t u d ya c o n t e n td i s t r i b u t i o ns y s t e mb a s e do ns p a r s en e t w o r kc o d i n g a n dc a r r yo u t s i m u l a t i o n st ov e r i f yi t sp e r f o r m a n c ec o m p a r e dt os y s t e m su s i n gg e n e r a ln e t w o r kc o d i n ga n d w i t h o u tn e t w o r kc o d i n g s i m u l a t i o nr e s u l t ss h o wt h a tc o m p a r e dw i t hg e n e r a ln e t w o r kc o d i n g s p a r s en e t w o r kc o d i n gc a l lr e d u c et h el i n e a rd e p e n d e n c eb e t w e e nc o d e db l o c k sa n dt h e c o m p u t a t i o n a lc o m p l e x i t yo fe n c o d i n go p e r a t i o n s a sw e l l a se n s u r i n gah i g hs u c c e s s f u l l y d e c o d i n gr a t e s i m u l a t i o nr e s u l t sa l s od e m o n s t r a t et h a ts p a r s en e t w o r kc o d i n gs y s t e m sc a n a c h i e v eb e t t e rp e r f o r m a n c et h a nn o n c o d i n gs y s t e m si nt e r m so ft h r o u g h p u t a v e r a g e d o w n l o a d i n gt i m ea n dt o t a ld i s t r i b u t i o nt i m e a l t h o u g hn e t w o r kc o d i n g c a nb r i n gp e r f o r m a n c eg a i nf o rn e t w o r k sf r o ms e v e r a l p e r s p e c t i v e s i tw i l la l s om a k et h ei n f o r m a t i o ne x p o s e dt od i f f e r e n ta t t a c k sd u r i n gt r a n s m i s s i o n d u et oi t sp r o p e r t yo fm i x i n gd a t a t h e r e f o r e t h i st h e s i sa l s of o c u s e so ns e c u r i t yi s s u e so f n e t w o r kc o d i n g w es t u d yn e t w o r kc o d i n gs c h e m e su s e dt oc o u n t e rd i f f e r e n ta t t a c k s w i t h e m p h a s i so nw i r e t a p p i n gp r o b l e m s w et h e np r o p o s ea ni m p r o v e dn e t w o r kc o d i n gs c h e m e a g a i n s tw i r e t a p p i n ga t t a c kb a s e do ne x i s t i n gw o r k s a n dp r o v ei tt ob es e c u r ea n da d m i s s i b l ew i t h l o w e rc o m p u t a t i o n a lc o m p l e x i t yc o m p a r e dt oe x i s t i n gs c h e m e s f i n a l l y s o m ea s p e c t sn e e d e dt ob es t u d i e df o rf u r t h e rr e s e a r c ha r ep o i n t e do u t k e y w o r d s n e t w o r kc o d i n g n e t w o r ks e c u r i t y s e c u r en e t w o r kc o d i n g c o n t e n td i s t r i b u t i o n i i 南京郵電大學(xué)碩士研究生學(xué)位論文 縮略詞表 n c i u n c w m a p n c p 2 p s l n c c s w n w m n w s n l c m i p f e c m i m o d a s d o s p a e s 縮略詞表 l i s to f a b b r e v i a t i o n s n e t w o r kc o d i n g r a n d o ml i n e a rn e t w o r kc o d i n g w i r e l e s sm u l t i c a s ta d v a n t a g e p r a c t i c a ln e t w o r kc o d i n g p e e r t o p e e r s p a r s el i n e a rn e t w o r kc o d i n g c o m m u n i c a t i o ns y s t e mo n aw i r e t a pn e t w o r k w i r e l e s sm e s hn e t w o r k s w i r e l e s ss e n s o rn e t w o r k s l i n e a r c o d em u l t i e a s t i n t e r n e tp r o t o c a l f o r w a r de r r o rc o r r e c t i o n m u l t i p l e i n p u tm u l t i p l e o u t p u t d i s t r i b u t e da n t e n n as y s t e m d e n i a lo fs e r v i c e p u b l i ck e yi n 仔a s t n j c t u r e a d v a n c e de n c r y p t i o ns t a n d a r d 1 1 1 網(wǎng)絡(luò)編碼 隨機(jī)線性網(wǎng)絡(luò)編碼 無線組播特性 實(shí)際網(wǎng)絡(luò)編碼 對(duì)等網(wǎng)絡(luò) 稀疏線性網(wǎng)絡(luò)編碼 竊聽網(wǎng)絡(luò)上的通信系統(tǒng) 無線網(wǎng)狀網(wǎng) 無線傳感器網(wǎng)絡(luò) 線性碼組播 因特網(wǎng)協(xié)議 前向糾錯(cuò)編碼 多輸入多輸出 分布式天線系統(tǒng) 拒絕服務(wù)攻擊 公鑰基礎(chǔ)設(shè)施 高級(jí)加密標(biāo)準(zhǔn) 南京郵電大學(xué)學(xué)位論文原創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得 的研究成果 盡我所知 除了文中特別加以標(biāo)注和致謝的地方外 論文中不包 含其他人已經(jīng)發(fā)表或撰寫過的研究成果 也不包含為獲得南京郵電大學(xué)或其它 教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料 與我一同工作的同志對(duì)本研究所做的 任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意 研究生簽名 叢鑒日期 南京郵電大學(xué)學(xué)位論文使用授權(quán)聲明 南京郵電大學(xué) 中國科學(xué)技術(shù)信息研究所 國家圖書館有權(quán)保留本人所送 交學(xué)位論文的復(fù)印件和電子文檔 可以采用影印 縮印或其它復(fù)制手段保存論 文 本文電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致 除在保密期內(nèi)的保密論文 外 允許論文被查閱和借閱 可以公布 包括刊登 論文的全部或部分內(nèi)容 論文的公布 包括干i j 登 授權(quán)南京郵電大學(xué)研究生部辦理 研究生簽名 避導(dǎo)師簽名 日期 南京郵電大學(xué)碩士研究生學(xué)位論文 第一章緒論 第一章緒論 網(wǎng)絡(luò)編碼 n e t w o r k c o d i n g 是一種融合了編碼和路由的信息傳輸技術(shù) 在傳統(tǒng)的存 儲(chǔ)一轉(zhuǎn)發(fā)路由方式的基礎(chǔ)上 通過允許對(duì)接收的多個(gè)數(shù)據(jù)包進(jìn)行編碼信息融合來增加單次 傳輸?shù)男畔⒘?從而提高網(wǎng)絡(luò)的整體性能 a h l s w e d e 等人 1 于2 0 0 0 年提出了網(wǎng)絡(luò)編碼的概 念 指出對(duì)組播網(wǎng)絡(luò)中的某些節(jié)點(diǎn)附加額外的編碼操作 能使源與組播成員間達(dá)到最大流 最小割定理所定義的組播速率 網(wǎng)絡(luò)編碼一經(jīng)提出便引起了國際學(xué)術(shù)界的廣泛關(guān)注 其理論和應(yīng)用己成為通信領(lǐng)域研 究的新熱點(diǎn) 網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量 改善負(fù)載均衡 減小傳輸延遲 節(jié)省節(jié)點(diǎn)能耗 增強(qiáng)網(wǎng)絡(luò)魯棒性等方面均顯示出其優(yōu)越性 可廣泛應(yīng)用于a d h o c 網(wǎng)絡(luò) 9 7 傳感器網(wǎng)絡(luò) 9 4 p 2 p 內(nèi)容分發(fā) 8 2 分布式文件存儲(chǔ) 1 0 和網(wǎng)絡(luò)安全 4 等領(lǐng)域 經(jīng)過幾年的發(fā)展 網(wǎng)絡(luò)編碼的理論研究己取得重要進(jìn)展 而其在應(yīng)用基礎(chǔ)和工程實(shí)踐方面的研究正在全方位 展開 網(wǎng)絡(luò)編碼己成為一項(xiàng)融合信息論 代數(shù)學(xué) 圖論 網(wǎng)絡(luò)流理論和優(yōu)化理論等多學(xué)科 的交叉技術(shù) 且日益引起更多研究者的關(guān)注 可以說 網(wǎng)絡(luò)編碼對(duì)現(xiàn)有的網(wǎng)絡(luò)體系結(jié)構(gòu) 協(xié)議設(shè)計(jì)方法 信息交換方式和網(wǎng)絡(luò)管理模式帶來了革命性的變化 國外多所著名大學(xué)如 麻省理工學(xué)院 多倫多大學(xué) 瑞士e p f l 學(xué)院等和多家知名i t 研究機(jī)構(gòu)包括微軟研究院 貝 爾實(shí)驗(yàn)室等都在積極開展網(wǎng)絡(luò)編碼的理論和應(yīng)用研究 而國內(nèi)針對(duì)網(wǎng)絡(luò)編碼的研究尚處于 起步階段 1 1 網(wǎng)絡(luò)編碼的概念 網(wǎng)絡(luò)通信的目的是在源點(diǎn)和目的節(jié)點(diǎn)之間傳遞信息 因此 網(wǎng)絡(luò)設(shè)計(jì)中最基本的問題 就是怎樣增加傳輸?shù)男畔⒘?計(jì)算機(jī)通信網(wǎng)絡(luò)的飛速發(fā)展以及邊緣學(xué)科的興起 使人們的 目光越來越多地投入到網(wǎng)絡(luò)信息論上面 2 0 0 0 年 香港中文大學(xué)的r w y e u n g 和n c a i 等 人首次將網(wǎng)絡(luò)和編碼進(jìn)行結(jié)合 提出了網(wǎng)絡(luò)編碼的概念 其核心思想是在網(wǎng)絡(luò)中參與傳輸 的節(jié)點(diǎn)不單純地執(zhí)行存儲(chǔ) 轉(zhuǎn)發(fā)功能 而可對(duì)來自多條鏈路的數(shù)據(jù)信息進(jìn)行一定的線性或非 線性處理 即編碼 然后發(fā)送出去 并保證接收節(jié)點(diǎn)可正確恢復(fù)出源節(jié)點(diǎn)所發(fā)送的信息 從而達(dá)到通信網(wǎng)絡(luò)的最大容量 最大限度的利用網(wǎng)絡(luò)的現(xiàn)有資源 下面通過一個(gè)簡單的例子對(duì)網(wǎng)絡(luò)編碼的基本思想進(jìn)行解釋 圖1 1 所示的通信網(wǎng)絡(luò)是一 個(gè)組播網(wǎng)絡(luò) 圖中箭頭代表有向鏈路 假設(shè)每條鏈路容量為1 b i t 單位時(shí)間 信源節(jié)點(diǎn)s 向接 墮塞堂皇奎堂堡主里 壅生堂垡堡塞墨二蘭絲絲 收節(jié)點(diǎn)r 1 和r 2 同時(shí)發(fā)送兩個(gè)比特信息a 和b 圖 a 中采用傳統(tǒng)的多播技術(shù) 節(jié)點(diǎn)s 分別向節(jié)點(diǎn) 1 7 r 鉑2 發(fā)送a g l b 節(jié)點(diǎn)l 和節(jié)點(diǎn)2 再分別將接收到的數(shù)據(jù)轉(zhuǎn)發(fā)給其他節(jié)點(diǎn) 這樣節(jié)點(diǎn)l 可以直接 獲得a 節(jié)點(diǎn)2 可以直接獲得b 但是當(dāng)a 和b 準(zhǔn)備通過節(jié)點(diǎn)3 進(jìn)行轉(zhuǎn)發(fā)時(shí) 由于節(jié)點(diǎn)3 和節(jié)點(diǎn)4 之間的鏈路容量為1 a 或b 必須在此排隊(duì)等候一個(gè)單位時(shí)間 這樣每個(gè)接收節(jié)點(diǎn)在單位時(shí)間 內(nèi)收到的比特?cái)?shù)為1 5 圖 b 則采用網(wǎng)絡(luò)編碼技術(shù) 中間節(jié)點(diǎn)3 將兩條輸入鏈路上收到的信 息a 和b 進(jìn)行線性編碼l 得到a o b 異或加 然后送出 在接收節(jié)點(diǎn)r l 處 根據(jù)接收到 的a 和a o b 即可恢復(fù)出來b 同樣 在接收節(jié)點(diǎn)r 2 處也可以恢復(fù)處a 由于解決了節(jié)點(diǎn)3 處 的傳輸瓶頸 每個(gè)接收節(jié)點(diǎn)在單位時(shí)間都可以收n 2 個(gè)比特 并達(dá)到了多播的最大流量 a b 圖1 1 網(wǎng)絡(luò)編碼原理圖 網(wǎng)絡(luò)編碼本質(zhì)上是一種編碼算法 支持者們聲稱它可以將現(xiàn)有的網(wǎng)絡(luò)吞吐量提高許 多 同時(shí)還能改善網(wǎng)絡(luò)的可靠性和防范攻擊的能力 網(wǎng)絡(luò)編碼技術(shù)最熱心的支持者們說 該技術(shù)將會(huì)引發(fā)網(wǎng)絡(luò)的下一代革命 其他人則認(rèn)為 網(wǎng)絡(luò)編碼技術(shù)更有可能會(huì)潛移默化地 改變目前基于路由的網(wǎng)絡(luò)架構(gòu) 1 2 網(wǎng)絡(luò)編碼的研究現(xiàn)狀 自從網(wǎng)絡(luò)編碼的思想提出以來 這個(gè)新興的領(lǐng)域受到了眾多研究學(xué)者的關(guān)注 下面簡 單介紹一下網(wǎng)絡(luò)編碼的發(fā)展概況 首先按網(wǎng)絡(luò)編碼的構(gòu)造方式分 主要又兩種 一種是由r w y e u n g 和n c a i 提出的 從向量空間構(gòu)造網(wǎng)絡(luò)編碼的方式 而另一種則是由r k o e t t e r 和m m e d a r d 給出的代數(shù)構(gòu) 造方式 y e u n g 和c a i 等在文獻(xiàn) 4 6 中提出了向量空間構(gòu)造線性網(wǎng)絡(luò)編碼的方法 并指出線 性編碼是最簡單的編碼方法 他們將鏈路上輸出的信息分組看成一定有限域下的向量 允 許節(jié)點(diǎn)通過線性方式對(duì)信息進(jìn)行編碼處理然后再傳輸 并證明線性編碼可以達(dá)到多播的最 南京郵電大學(xué)碩士研究生學(xué)位論文 第一蘋緒論 大流 ps a n d e r s 等人提出了一種實(shí)現(xiàn)網(wǎng)絡(luò)編碼的多項(xiàng)式時(shí)間算法 1 3 1 1 5 7 1 將 4 6 1 q b 提出的 網(wǎng)絡(luò)編碼的構(gòu)造進(jìn)一步簡化 不但把網(wǎng)絡(luò)編碼構(gòu)造的復(fù)雜度從指數(shù)級(jí)降到了多項(xiàng)式級(jí) 而 且大大降低了網(wǎng)絡(luò)編碼中所采用的字母表的下限 r k o e t t e r 和m m e d a u r d 提出的代數(shù)構(gòu)造 方式 4 7 4 8 用一個(gè)系統(tǒng)轉(zhuǎn)移矩陣來描述信源輸入信息和信宿上接收到的信息之間的關(guān) 系 并通過構(gòu)造符合要求的系統(tǒng)轉(zhuǎn)移矩陣來實(shí)現(xiàn)網(wǎng)絡(luò)編碼 這是一種指數(shù)時(shí)間算法 算法 復(fù)雜度比較大 上述方法都是基于已知整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?幾乎同時(shí)有人又提出了不需網(wǎng)絡(luò)拓?fù)湫?息的分布式網(wǎng)絡(luò)編碼和隨機(jī)網(wǎng)絡(luò)編碼 分布式網(wǎng)絡(luò)編碼 6 的實(shí)現(xiàn)是在網(wǎng)絡(luò)中傳輸?shù)拿總€(gè)數(shù) 據(jù)包上留出一些比特用來記載此數(shù)據(jù)包在前面各個(gè)節(jié)點(diǎn)上所經(jīng)歷的操作 那么接收節(jié)點(diǎn)就 可以從接收到的數(shù)據(jù)包中直接譯出信源所發(fā)送的信息 這種方法可以在不知道網(wǎng)絡(luò)拓?fù)湫?息的情況下實(shí)現(xiàn)網(wǎng)絡(luò)編碼 但是增加了網(wǎng)絡(luò)負(fù)載 但是仿真表明 在這個(gè)信息組播的過程 中 這種處理方式帶來的負(fù)載代價(jià)并不大 另一種不需網(wǎng)絡(luò)拓?fù)涞姆椒ㄊ请S機(jī)網(wǎng)絡(luò)編碼 3 6 0 即在網(wǎng)絡(luò)的中間節(jié)點(diǎn)上對(duì)接收到的信息在一個(gè)有限域內(nèi)隨機(jī)選擇一個(gè)元素作為組 合的系數(shù) 研究已經(jīng)表明 只要有限域取得足夠大 這種方法的失敗率就可以很低 這種 方法帶來的缺點(diǎn)一個(gè)是以一定的概率實(shí)現(xiàn)正確無誤的傳輸 另一個(gè)是需增大通信網(wǎng)絡(luò)中所 需字母表的大小 文獻(xiàn) 3 2 1 提出了基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)糾錯(cuò)碼的概念 網(wǎng)絡(luò)糾錯(cuò)碼不同于傳統(tǒng)的基于逐 個(gè)鏈路的錯(cuò)誤糾正的經(jīng)典糾錯(cuò)碼 它是采用分布式的方式來對(duì)整個(gè)網(wǎng)絡(luò)中的差錯(cuò)進(jìn)行糾 正 只要鏈路上發(fā)生傳輸錯(cuò)誤的符號(hào)數(shù)不超過糾錯(cuò)范圍 不用經(jīng)過重傳 接收節(jié)點(diǎn)通過一 定的譯碼就可恢復(fù)信息 文獻(xiàn) 1 1 1 1 1 2 將網(wǎng)絡(luò)編碼與卷積碼相結(jié)合 探討了單位延遲網(wǎng)絡(luò) 模型下的網(wǎng)絡(luò)編碼問題 文獻(xiàn) 1 1 3 1 分析了簡單的具有兩接收端的多元網(wǎng)絡(luò)編碼 文獻(xiàn) 1 1 4 探討了相關(guān)信源下的網(wǎng)絡(luò)信息理論 文獻(xiàn) 1 1 5 指出基于差錯(cuò)控制的網(wǎng)絡(luò)編碼和傳統(tǒng)差錯(cuò)控 制碼的設(shè)計(jì)有很強(qiáng)的聯(lián)系 這為基于差錯(cuò)控制的網(wǎng)絡(luò)編碼設(shè)計(jì)提供了方向 p o p o v s k i 等人 1 0 5 研究了現(xiàn)有各類物理層編碼方案在兩路中繼信道下如何最大化通信 速率的問題 并給出了各方案中對(duì)系統(tǒng)性能影響最大的關(guān)鍵要素 文獻(xiàn) 1 0 6 對(duì)基于網(wǎng)絡(luò)編 碼的協(xié)作通信進(jìn)行了系統(tǒng)的理論分析 相對(duì)于傳統(tǒng)的協(xié)作方案 基于網(wǎng)絡(luò)編碼的方案在同 等的頻譜效率下可達(dá)到更高的分集增益 在提高無線網(wǎng)絡(luò)的吞吐量方面 l e o n g 1 0 0 等提出了 種隨機(jī)網(wǎng)絡(luò)編碼算法 并將該 算法與基于在線s t e i n e r 樹生成算法 d i j k s t r a 最短路徑算法和最近節(jié)點(diǎn)優(yōu)先算法的路由算法 進(jìn)行比較 結(jié)果表明 分布式隨機(jī)網(wǎng)絡(luò)編碼方法在組播吞吐量和魯棒性方面要明顯優(yōu)于基 于路由的算法 為了提高能量的利用效率 m i t 的p e t r o v i c 等人提出了一種結(jié)合網(wǎng)絡(luò)編碼的 3 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 對(duì)無線信號(hào)不進(jìn)行調(diào)制的策略 1 0 1 該策略由于節(jié)省了模擬器件進(jìn)行調(diào)制所消耗的能量 降低了節(jié)點(diǎn)成本 因此可以節(jié)省大量能量 k a t t i 等人 9 9 針對(duì)無線網(wǎng)狀網(wǎng) w i r e l e s sm e s hn e t w o r k s 提出了基于機(jī)會(huì)的網(wǎng)絡(luò)編碼 協(xié)議c o p e 并在2 0 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)測試床上完成了協(xié)議實(shí)現(xiàn) 這是網(wǎng)絡(luò)編碼首次在無線環(huán) 境中的協(xié)議層面上的具體實(shí)現(xiàn) 文獻(xiàn) 1 6 對(duì)基于c o p e 的無線網(wǎng)絡(luò)進(jìn)行了更深入的理論分 析 并給出了相應(yīng)的性能改進(jìn) 其他涉及節(jié)能和跨層設(shè)計(jì)的研究可參閱文獻(xiàn) 7 5 1 0 7 文獻(xiàn) 1 0 2 針對(duì)無線傳感器網(wǎng)絡(luò)提出了一種結(jié)合分布式源編碼和網(wǎng)絡(luò)編碼的優(yōu)化算法 目的是用來提高傳感器網(wǎng)絡(luò)的容錯(cuò)性和可靠性 同時(shí)對(duì)分布式源編碼的壓縮效率和網(wǎng)絡(luò)魯 棒性進(jìn)行了折衷考慮 d i m a k i s 等提出了一種傳感器網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的數(shù)據(jù)聚合算法 8 8 使得數(shù)據(jù)聚合的效率得到極大的提高 基于網(wǎng)絡(luò)編碼的p 2 p 內(nèi)容分發(fā)協(xié)議一直是網(wǎng)絡(luò)編碼的研究熱點(diǎn)之一 它在節(jié)省帶寬資源 提高系統(tǒng)的抗毀性和可擴(kuò)展性等方面都比無編碼協(xié)議優(yōu)勢明顯 但也面臨著解碼計(jì)算復(fù) 雜 延時(shí)過大導(dǎo)致系統(tǒng)性能下降的新問題 文獻(xiàn) 8 2 指出 在p 2 p 系統(tǒng)中采用隨機(jī)線性碼 僅在編碼塊數(shù)目較少且塊大小合適的情形下 其性能才可接受 m a 等人 8 4 實(shí)現(xiàn)了一個(gè) 基于稀疏線性編碼策略的p 2 p 內(nèi)容分發(fā)系統(tǒng) 通過鄰居選取 環(huán)路檢測和編碼區(qū)間劃分3 種 策略 降低了各編碼塊間的線性相關(guān)性 提升了系統(tǒng)的整體性能 文獻(xiàn) 1 0 9 提出了一種基 于網(wǎng)絡(luò)編碼的p 2 p 流媒體直播方案 仿真實(shí)驗(yàn)表明 采用網(wǎng)絡(luò)編碼后 節(jié)點(diǎn)的播放質(zhì)量得 到了普遍增強(qiáng) l a v a 1 1 0 是首個(gè)集成網(wǎng)絡(luò)編碼技術(shù)的p 2 p 流媒體協(xié)議實(shí)際系統(tǒng) 通過與 己實(shí)現(xiàn)的標(biāo)準(zhǔn)流媒體協(xié)議v a n i l l a 比較 網(wǎng)絡(luò)編碼協(xié)議在可用上傳帶寬略大于流媒體所需帶 寬時(shí)優(yōu)勢較明顯 a c e d a n s k i 等人 1 2 研究了在多個(gè)存儲(chǔ)資源受限的節(jié)點(diǎn)間進(jìn)行分布式文件存儲(chǔ)的問題 比較了無編碼存儲(chǔ) 基于糾刪碼存儲(chǔ)和采用隨機(jī)線性碼存儲(chǔ)3 種策略 仿真結(jié)果表明 基 于隨機(jī)線性碼的分布式存儲(chǔ)策略在無需全局文件服務(wù)器的參與時(shí) 其性能接近集中式全局 調(diào)度算法 文獻(xiàn) 9 3 關(guān)注基于糾刪碼的文件存儲(chǔ)在保持冗余度不變時(shí) 如何最小化網(wǎng)絡(luò)帶 寬的問題 網(wǎng)絡(luò)編碼在通信網(wǎng)絡(luò)安全性方面的應(yīng)用是網(wǎng)絡(luò)編碼研究中逐漸興起的一個(gè)領(lǐng)域 也是 本文的研究重點(diǎn) 2 0 0 2 年 y e u n g 和c a i 就網(wǎng)絡(luò)竊聽問題首先進(jìn)行了研究 1 8 設(shè)計(jì)了一種 安全的網(wǎng)絡(luò)編碼 在通信鏈路已經(jīng)被竊聽的情況下 在信源處將原始數(shù)據(jù)和隨機(jī)信息結(jié)合 起來進(jìn)行網(wǎng)絡(luò)編碼設(shè)計(jì) 該文獻(xiàn)從理論上證明了此方案使得只有接收方才能正確解碼 竊 聽者得到的信息包和原始數(shù)據(jù)包之間沒有任何相關(guān)性 互信息為零 就信息論而言 是安 全的 f e l d m a n 等人則在 1 8 的基礎(chǔ)上 改進(jìn)了構(gòu)造方法 并將其提出的定理細(xì)化 將組 4 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 播容量和構(gòu)造線性碼所需的字母表大小進(jìn)行了折衷 1 9 k b h a t t a d 等人 2 3 針對(duì)無環(huán)網(wǎng)絡(luò)的組播問題 提出了竊聽者不能得到任何有意義信息 的弱安全網(wǎng)絡(luò)編碼模型 他們通過理論證明 在該模型下 對(duì)于計(jì)算能力有限的竊聽者來 說 只要它們竊取的獨(dú)立信源信息數(shù)小于組播容量 就可以用安全網(wǎng)絡(luò)編碼來進(jìn)行保密通 信 并且不會(huì)降低傳輸速率 同樣是針對(duì)竊聽攻擊 k j a i n 等在 1 0 3 q b 得到了單源網(wǎng)絡(luò)中 可以有環(huán) 以單位速率安全單播的充要條件 利用哈希函數(shù)和網(wǎng)絡(luò)編碼相結(jié)合的方法 使得網(wǎng)絡(luò)以更高的速率安全傳輸數(shù)據(jù) 而搭線竊聽者得不到信源的任何有用信息 c h a n 等 人在文獻(xiàn) 1 0 4 中討論了多源網(wǎng)絡(luò)的安全通信問題 他們?cè)谝欢ǜ`聽范圍的限制下 利用隨 機(jī)網(wǎng)絡(luò)編碼的方法 給出了多源安全網(wǎng)絡(luò)編碼容量的內(nèi)界 外界和線性規(guī)劃界 這些界是 y e u n g 得到的界的推廣 中繼節(jié)點(diǎn)對(duì)編碼數(shù)據(jù)的惡意修改可能會(huì)導(dǎo)致網(wǎng)絡(luò)編碼使用受限 甚至不可用 因此消 除拜占庭攻擊的影響一直是網(wǎng)絡(luò)編碼安全應(yīng)用研究中各受關(guān)注的問題 文獻(xiàn) 4 提出了一種 用散列函數(shù)檢測拜占庭敵手的方法 首先對(duì)原始數(shù)據(jù)進(jìn)行簡單多項(xiàng)式函數(shù)哈希變換 然后 把得到的結(jié)果添加到每一個(gè)原始數(shù)據(jù)包內(nèi) 接收節(jié)點(diǎn)經(jīng)過比較解碼后的數(shù)據(jù)和哈希值就可 以判斷數(shù)據(jù)包是否被修改過 可以防止拜占庭攻擊 j a g g i 等人 3 3 1 0 8 進(jìn)一步給出了一種 多項(xiàng)式復(fù)雜度的分布式算法 在糾正敵手錯(cuò)誤的前提下 同時(shí)達(dá)到最優(yōu)組播速率 該方法 無需對(duì)編碼節(jié)點(diǎn)添加新的功能 對(duì)無線和有線網(wǎng)絡(luò)均適用 k r o h n 等人 3 6 提出了一種基于 同態(tài)散列函數(shù)的方法 用于檢測被修改的編碼分組 但該方法需要將計(jì)算好的散列值預(yù)先 通過其他通道分發(fā)給所有節(jié)點(diǎn) 因此該方法具有一定的局限性 文獻(xiàn) 3 5 乖t j 用橢圓曲線算 法給出了一種適用于網(wǎng)絡(luò)編碼的簽名方案 除了可檢測被修改的分組 還加入了對(duì)數(shù)據(jù)的 身份認(rèn)證功能 g k a n t s i d i s 等人 3 7 研究的是使用了網(wǎng)絡(luò)編碼技術(shù)的p 2 p 內(nèi)容分發(fā)網(wǎng)絡(luò)的安全問題 他 們集中研究了如何抵抗針對(duì)系統(tǒng)熵或試圖完全阻塞系統(tǒng)的安全攻擊 提出了一種能夠提高 驗(yàn)證效率的方案 他們還提出一種基于安全隨機(jī)校驗(yàn)和的 能夠防止偽造警報(bào)造成的d o s 攻擊的有效機(jī)制 o l i v e i r a 等人 4 3 通過研究證明 利用網(wǎng)絡(luò)編碼的優(yōu)勢 可以為傳感器網(wǎng) 絡(luò)設(shè)計(jì)出一種密鑰分配方案 它只需要用到少量預(yù)先存儲(chǔ)的密鑰 但仍然可以確保以概率 l 建立共享密鑰連接 并且移動(dòng)節(jié)點(diǎn)并不知道所分配的密鑰 總而言之 現(xiàn)在關(guān)于網(wǎng)絡(luò)編碼的研究是百家爭鳴 各種方法和應(yīng)用層出不窮 但是 沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn) 而且多數(shù)是基于理論分析 試驗(yàn)仿真很少 到目前為止 網(wǎng)絡(luò)編碼 應(yīng)用到實(shí)際網(wǎng)絡(luò)中去還比較少 所以關(guān)于網(wǎng)絡(luò)編碼的研究還有很多東西去做 5 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 1 3 論文主要工作及章節(jié)安排 本文在對(duì)網(wǎng)絡(luò)編碼的基本理論進(jìn)行深入學(xué)習(xí)和研究的基礎(chǔ)上 著重討論其在無線網(wǎng)絡(luò) 和網(wǎng)絡(luò)安全中應(yīng)用時(shí)的性能增益 首先 重點(diǎn)研究一種基于稀疏網(wǎng)絡(luò)編碼的p 2 p 內(nèi)容分發(fā) 算法 并對(duì)其進(jìn)行詳細(xì)研究和仿真驗(yàn)證 仿真實(shí)驗(yàn)表明 與一般網(wǎng)絡(luò)編碼相比 稀疏網(wǎng)絡(luò) 編碼能夠減小分發(fā)系統(tǒng)中編碼分塊的線性相關(guān)性 降低編碼計(jì)算復(fù)雜度 并且解碼成功率 較高 與無編碼的分發(fā)系統(tǒng)相比 基于稀疏網(wǎng)絡(luò)編碼的分發(fā)系統(tǒng)在吞吐量 平均下載時(shí)間 和總分發(fā)時(shí)間等方面的性能都要優(yōu)于前者 此外 本文還將對(duì)網(wǎng)絡(luò)編碼的安全性進(jìn)行重點(diǎn) 研究 討論抵御不同安全攻擊的網(wǎng)絡(luò)編碼方案 同時(shí)針對(duì)網(wǎng)絡(luò)的外部竊聽攻擊提出一種改 進(jìn)的安全網(wǎng)絡(luò)編碼方案 從理論上證明其安全性和可達(dá)性 且具有較低的計(jì)算復(fù)雜度 本文共分六章 其余幾章安排如下 第二章對(duì)網(wǎng)絡(luò)編碼的基本理論進(jìn)行討論 先對(duì)網(wǎng)絡(luò)編碼的數(shù)學(xué)模型和原理進(jìn)行研究 然后依次介紹線性網(wǎng)絡(luò)編碼 隨機(jī)網(wǎng)絡(luò)編碼和實(shí)際網(wǎng)絡(luò)編碼的概念 最后總結(jié)網(wǎng)絡(luò)編碼的 性能優(yōu)點(diǎn) 第三章首先介紹網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的一些典型應(yīng)用 接著就p 2 p 內(nèi)容分發(fā)問題 著重研究一種基于稀疏網(wǎng)絡(luò)編碼的內(nèi)容分發(fā)系統(tǒng) 并通過性能仿真 驗(yàn)證稀疏網(wǎng)絡(luò)編碼的 優(yōu)越性 最后 通過從安全性角度將網(wǎng)絡(luò)編碼方案分類以及將各種安全攻擊歸類 引出網(wǎng) 絡(luò)編碼在安全性方面的研究 第四章研究如何利用網(wǎng)絡(luò)編碼的特性來抵抗各種不同的安全攻擊 其中重點(diǎn)研究抵抗 竊聽攻擊的網(wǎng)絡(luò)編碼方案 并對(duì)方案性能進(jìn)行了詳細(xì)分析 第五章針對(duì)竊聽問題 在前人工作的基礎(chǔ)上 提出一種改進(jìn)的網(wǎng)絡(luò)編碼方案 并對(duì)其 性能進(jìn)行驗(yàn)證 第六章總結(jié)全文的工作 并指出今后有待進(jìn)一步深入研究的一些問題 6 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 本章首先從通信網(wǎng)絡(luò)的角度出發(fā) 介紹了圖論的相關(guān)知識(shí) 在此基礎(chǔ)上引出了網(wǎng)絡(luò)編 碼的基本原理及數(shù)學(xué)模型 并從信息論角度出發(fā)證明了其可以實(shí)現(xiàn)網(wǎng)絡(luò)中的最大流 而這 是傳統(tǒng)路由方式無法達(dá)到的 接著 本章重點(diǎn)描述了網(wǎng)絡(luò)編碼最主要的實(shí)現(xiàn)方式一線性網(wǎng) 絡(luò)編碼的原理以及兩種從不同角度出發(fā)的構(gòu)造方法 同時(shí)分析了線性網(wǎng)絡(luò)編碼的局限性 之后 本章研究了線性網(wǎng)絡(luò)編碼中最重要 也是最為實(shí)用的兩種方案一隨機(jī)網(wǎng)絡(luò)編碼和實(shí) 際網(wǎng)絡(luò)編碼 最后 本章從增加網(wǎng)絡(luò)容量以及節(jié)省網(wǎng)絡(luò)帶寬兩個(gè)角度分析了網(wǎng)絡(luò)編碼技術(shù) 的優(yōu)點(diǎn) 2 1 網(wǎng)絡(luò)編碼的數(shù)學(xué)模型 2 1 1 網(wǎng)絡(luò)編碼的預(yù)備知識(shí)一圖論和網(wǎng)絡(luò)流圖 2 1 1 1 圖論基礎(chǔ) 一個(gè)圖是由一些節(jié)點(diǎn)和連接兩個(gè)節(jié)點(diǎn)之間的連線所組成 至于連線的長度及節(jié)點(diǎn)的位 置是無關(guān)緊要的 定義2 1 一個(gè)圖是一個(gè)三元組 y g e g 哆 其中y g 是一個(gè)非空的節(jié)點(diǎn)集合 e g 是邊集合 唾是從邊集合e g 到節(jié)點(diǎn)無序偶 有序偶 集合上的函數(shù) 若把圖中的邊e l 看作總是與兩個(gè)節(jié)點(diǎn)關(guān)聯(lián) 那么一個(gè)圖亦可簡記為g 一v 1 1 k 專v 使得 七 v 七 e 3 a 七 l i a k i i 彳ti l l k k 使得兀i a i i 嘞 其中毛 l k k 七 1 七 f 女e 4 如果u k s 那么以 q a t 否則 六 兀4 寸a 其中q l 1 2 曲1 g 1 k 0 存在一個(gè)足夠大的囂 使圖g 上的 i j e 矗一g 口一碼對(duì)于 所有的邊 f e 均滿足 刀一l 0 9 2r f r g 2 1 2 這里理 l o g 7 是編碼后鏈路 f 力上的平均比特速率 定義2 8 兄 g 豆 天 h g 是口一可達(dá)的 定義2 9 有向圖g v e 中 信源為s 信宿f 1 t l 邊 f 力上的容量為r 則 硝 g 天 s 至l j t 1 1 乙 的最大流 塒 定理2 3 1 r 加 尺三g 文獻(xiàn) 1 給出了上述定理的詳細(xì)證明 此處從略 通過有關(guān)熵的理論 該定理證明了通 過網(wǎng)絡(luò)編碼 可以使網(wǎng)絡(luò)的傳輸容量達(dá)到最大流最小割給出的理論限 2 2 線性網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)編碼方案可分為線性和非線性兩種 所謂線性網(wǎng)絡(luò)編碼 4 6 也就是在實(shí)現(xiàn)網(wǎng)絡(luò)編 碼過程中所用到的編碼函數(shù)和譯碼函數(shù)均采用線性函數(shù)來實(shí)現(xiàn) 線性網(wǎng)絡(luò)編碼是中間節(jié)點(diǎn) 將接收數(shù)據(jù)在某有限域內(nèi)進(jìn)行線性組合 節(jié)點(diǎn)接收足夠數(shù)量的獨(dú)立數(shù)據(jù)包就可以通過正確 譯碼解得全部信息內(nèi)容 能充分利用網(wǎng)絡(luò)帶寬 假設(shè)每個(gè)信息數(shù)據(jù)包為l 比特 當(dāng)它與要 l s 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 組合的數(shù)據(jù)包長度不同時(shí) 較短的信息附加額外一串 0 將包中的j 個(gè)連續(xù)比特組成域 上的一個(gè)符號(hào) 則一個(gè)包中包含三 j 個(gè)符號(hào) 在線性編碼下 運(yùn)用乘法和加法運(yùn)算 使從 節(jié)點(diǎn)發(fā)送出去的數(shù)據(jù)為 該節(jié)點(diǎn)接收到信息的線性組合 5 6 文獻(xiàn) 1 3 4 6 4 8 5 3 5 4 5 5 等都討論了線性網(wǎng)絡(luò)編碼 的原理及實(shí)現(xiàn)問題 2 2 1 線性網(wǎng)絡(luò)編碼的基本原理 下面介紹線性網(wǎng)絡(luò)編碼的基本原理 即如何進(jìn)行編碼和解碼操作 2 2 1 1 編碼過程 假設(shè)一個(gè)源或多個(gè)源產(chǎn)生的原始數(shù)據(jù)包信息為m 則在線性網(wǎng)絡(luò)編碼中傳輸?shù)?數(shù)據(jù)可表示為 x g 鳩 2 1 3 i 1 其中蜀 g n 表示相應(yīng)的編碼系數(shù) 對(duì)每個(gè)符號(hào)有 彳七 膨 2 1 1 其中 彬和x 分別表示必和x 的第k 個(gè)符號(hào) 傳輸?shù)臄?shù)據(jù)包中既包括編碼向量 又包括信息向量 編碼向量用于接收端的 解碼 編碼過程采用迭代的方法 若一個(gè)節(jié)點(diǎn)己經(jīng)接收和存儲(chǔ)的包信息集合為 五 g 厶 則該節(jié)點(diǎn)可以通過選定編碼系數(shù)曩 和運(yùn)用算式 2 1 5 得到新 的信息包刀 x 么t 2 1 5 l 編碼向量g 可以通過 直接的代數(shù)計(jì)算得到 該過程可以在若干個(gè)節(jié)點(diǎn)中重復(fù)操作 g 乃g 2 1 6 l 2 2 1 2 解碼過程 假設(shè)節(jié)點(diǎn)接收集合為 g l 墨 以 為了恢復(fù)原始信息 需要求解 2 2 0 中的 1 6 南京郵電大學(xué)碩士研究生學(xué)位論文第二章網(wǎng)絡(luò)編碼基礎(chǔ) m 個(gè)等式中的甩個(gè)未知數(shù)必 因此恢復(fù)所有數(shù)據(jù)要求腳 刀 也就是說接收包的個(gè)數(shù)至少 要為原信息的個(gè)數(shù) 而有些線性組合可能是線性相關(guān)的 所以歷 r l 并不是充分條件 但 卻是網(wǎng)絡(luò)編碼的重要條件 g j m 2 1 7 j l 解碼需要求解一組線性方程 實(shí)際中 可以應(yīng)用高斯消去的方法 節(jié)點(diǎn)存儲(chǔ)編碼向量 以及編碼之后的結(jié)果 以行向量的形式 存儲(chǔ)在所謂解碼矩陣中 最初解碼矩陣中只包含 未經(jīng)該節(jié)點(diǎn)編碼的包以及與之相對(duì)應(yīng)的編碼向量 如果有的話 否則為空 當(dāng)接收到一個(gè) 已編碼包后 會(huì)從中抽取它的編碼向量以及編碼結(jié)果 放入到解碼矩陣中 解碼矩陣會(huì)經(jīng) 過等價(jià)變換變成行階梯型 最終變成行最簡型 如果所收到的某一個(gè)包可以增加矩陣的秩 則稱之為更新包 如果所收到的包是非更新的 它可以通過等價(jià)變換變?yōu)槿?從而可以 忽略 當(dāng)解碼矩陣變換成最簡型后 方程組得解 這種情況發(fā)生在當(dāng)接收到以個(gè)線性獨(dú)立 的編碼向量之后 2 2 2 線性網(wǎng)絡(luò)編碼的實(shí)現(xiàn)方案 編碼向量的選取可以采用確定性編碼策略和隨機(jī)編碼策略 確定性的方案是根據(jù)網(wǎng)絡(luò)拓?fù)錇楣?jié)點(diǎn)選取確定的編碼向量 y e u n g 等人 4 6 提出了線 性網(wǎng)絡(luò)編碼的向量實(shí)現(xiàn)方法 通過分析網(wǎng)絡(luò)結(jié)構(gòu) 根據(jù)節(jié)點(diǎn)的輸入輸出個(gè)數(shù)設(shè)計(jì)相應(yīng)的局 部編碼向量 用迭代的方式得到全局編碼向量 從而實(shí)現(xiàn)網(wǎng)絡(luò)編碼 k o e t t e r 等人 4 7 則提 出了較為完備的線性網(wǎng)絡(luò)編碼的代數(shù)實(shí)現(xiàn)方法 但他們的方法運(yùn)算量太高 于是j a g g i 等 人 1 3 5 7 又提出了一種確定的多項(xiàng)式時(shí)間編碼設(shè)計(jì)算法 可以為特定的廣播網(wǎng)絡(luò)找到可行 的網(wǎng)絡(luò)編碼 目前已有對(duì)此算法的各種改進(jìn) 確定性的編碼方案由于每個(gè)節(jié)點(diǎn)應(yīng)用的都是固定的編碼向量 因此網(wǎng)絡(luò)中傳 遞的數(shù)據(jù)中只需要包含信息向量 節(jié)省帶寬 并且所需的符號(hào)域比較小 但確定 性的網(wǎng)絡(luò)編碼需要了解全網(wǎng)的情況 拓?fù)浣Y(jié)構(gòu)等 復(fù)雜度比較高 難于分布式地實(shí)現(xiàn) 一旦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生了變化 就必須對(duì)整個(gè)編碼方案進(jìn)行修改 對(duì)無線環(huán)境變化的魯棒 性比較差 由于確定性網(wǎng)絡(luò)編碼的以上缺點(diǎn) h o 和m e d a r d 等人 2 1 1 5 8 1 提出了隨機(jī)網(wǎng)絡(luò)編碼的概 念 隨機(jī)網(wǎng)絡(luò)編碼是讓網(wǎng)絡(luò)中的節(jié)點(diǎn)以完全獨(dú)立的分布式方式 隨機(jī)選取編碼系數(shù) 對(duì)輸 入信息編碼 并把這組隨機(jī)向量作為報(bào)頭的一部分發(fā)送給收點(diǎn) 以便于解碼 已經(jīng)證明 1 7 南京郵屯大學(xué)碩士研究生學(xué)位論文第二章網(wǎng)絡(luò)編碼基礎(chǔ) 隨機(jī)方式選取的編碼向量成功的概率為1 1 i f l 其中f 為編碼的符號(hào)域 當(dāng)符號(hào)域?yàn)闊o 窮大時(shí) 采用隨機(jī)編碼 系統(tǒng)傳輸矩陣滿秩的概率為 1 隨機(jī)編碼可以分布式地實(shí)現(xiàn) 并可增加保密性 文獻(xiàn) 4 7 提出的代數(shù)實(shí)現(xiàn)框架指出 線性網(wǎng)絡(luò)編碼可以通過隨機(jī)編碼有效地構(gòu)建 c h o u 6 應(yīng)用隨機(jī)編碼 提出了第一個(gè)實(shí)用的 網(wǎng)絡(luò)編碼方案 為了保證隨機(jī)編碼成功概率 編碼向量的符 號(hào)域必須足夠大 這可能會(huì)增加數(shù)據(jù)包頭部的負(fù)擔(dān) 因此符號(hào)域的大小必須仔細(xì) 選擇 確定性編碼和隨機(jī)編碼分別用于不同的網(wǎng)絡(luò)應(yīng)用與構(gòu)架上 這些方案主要是基于理論 上的分析和實(shí)現(xiàn) 因此在實(shí)際網(wǎng)絡(luò)上需要針對(duì)不同的應(yīng)用設(shè)計(jì)相應(yīng)的編碼方式 如對(duì)于結(jié) 構(gòu)較小的網(wǎng)絡(luò) 可以選擇比較簡單的確定性算法 編碼過程中甚至可以通過轉(zhuǎn)換為對(duì)數(shù) 將乘法運(yùn)算轉(zhuǎn)換成加法運(yùn)算 降低總的編碼復(fù)雜度 而對(duì)于無線網(wǎng)絡(luò) 則應(yīng)用隨機(jī)編碼機(jī) 制是主要的研究趨勢 即令中間節(jié)點(diǎn)隨機(jī)生成編碼系數(shù) 對(duì)節(jié)點(diǎn)所有的可用信息應(yīng)用線性 編碼 并隨時(shí)更新編碼系數(shù) 還有一種半隨機(jī)的編碼方案 整個(gè)網(wǎng)絡(luò)被化分成若干區(qū)域 各區(qū)域都采用隨機(jī)編碼 但為了保證傳輸矩陣滿秩 區(qū)域間要相互傳遞信息 以使每個(gè)區(qū) 域在選擇編碼向量時(shí)盡量不選可能導(dǎo)致解碼失敗的那些向量 2 2 2 1 從向量空間角度構(gòu)造線性網(wǎng)絡(luò)編碼 繼r a h l s w e d e 等人 1 指出網(wǎng)絡(luò)的最大流可由網(wǎng)絡(luò)編碼實(shí)現(xiàn)以后 4 6 首先給出了網(wǎng)絡(luò) 編碼的具體實(shí)現(xiàn)方法 之后 1 3 5 7 又從信息流的角度對(duì)以上方法進(jìn)行了簡化 把算法的 時(shí)間復(fù)雜度從指數(shù)級(jí)降到了多項(xiàng)式時(shí)間級(jí) 設(shè)d 表示信源s 和任一非信源節(jié)點(diǎn)丁的最大流m a x f l o w t 的最大值 q 表示一足夠大 基域f 上的d 維向量空間 這里采用的信息速率單位為每單位時(shí)間信道上可以傳輸一個(gè)基 域上的符號(hào) 定義2 1 0 1 4 6 通信網(wǎng)絡(luò) g s 上的一個(gè)線性碼組播 l i n e a r c o d em u l t i c a s t l c m v 是 對(duì)每一節(jié)點(diǎn)x 分配一個(gè)向量空間v x 每一信道 x n e 分配一個(gè)全局編碼向量 v x 功 使得它們滿足以下條件 1 1 s q 2 對(duì)每一信道 腭有 v x n v x 3 對(duì)于網(wǎng)絡(luò)中的任何非信源節(jié)點(diǎn)集合 有 1 8 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 1 r r 艫 v 盯 x 茌矽 y 矽 2 1 8 4 給節(jié)點(diǎn)t 的輸出邊分配的編碼向量是其輸入邊所分配的編碼向量的線性組合 符號(hào) 表示線性張成 l c my 刻畫了一種信息數(shù)據(jù)在網(wǎng)絡(luò)中傳播的結(jié)構(gòu) 開始將源 節(jié)點(diǎn)s 中要傳輸?shù)男畔⒎殖蒬 維的向量組 稱作信息向量 在傳輸過程中 每條信道上承 載的數(shù)據(jù)符號(hào)是信息向量和該信道所分配的編碼向量的向量積 圖2 4 b 就是一個(gè)線性編碼組播的例子 在該例中 網(wǎng)絡(luò)編碼的的基域?yàn)槲?每一條 鏈路分配的編碼列向量為 v 跚 y 吣 叫u 朋 v c s y v c y 瓦 v c y c 2 9 v e 形 x v e x 互 v e x 瓦 信源s 的信息向量為 口 6 每一條鏈路上傳輸?shù)男畔⒎?hào)為信息向量 a b 和該鏈路 編碼列向量的向量積 對(duì)于一個(gè)線性網(wǎng)絡(luò)編碼組播 如果所有接收節(jié)點(diǎn)能夠恢復(fù)出信源發(fā) 送的信息向量 則稱其為有效的線性編碼組播 當(dāng)網(wǎng)絡(luò)中的任何m 1 m d 條鏈路 x z x e l 匕對(duì)應(yīng)的編碼向量線性無關(guān)時(shí) 就可以保證任何接收點(diǎn)能夠恢復(fù)出信源的 信息向量 當(dāng)編碼符號(hào)域足夠大時(shí) 就可以保證這一點(diǎn)成立 可以驗(yàn)證 上述線性碼組播可以實(shí)現(xiàn)圖2 4 b 中網(wǎng)絡(luò)的通信 但是對(duì)于任意復(fù)雜的通 信網(wǎng)絡(luò) 如何找到其所有的全局編碼向量呢 p s a n d e r s 等人 1 3 5 7 1 針對(duì)組播網(wǎng)絡(luò)給出了 一種多項(xiàng)式時(shí)間算法 現(xiàn)把其主要思想介紹如下 這種多項(xiàng)式時(shí)間算法是對(duì)從向量空間角度構(gòu)造線性網(wǎng)絡(luò)編碼的方法進(jìn)行的簡化 4 6 首先 對(duì)于任意給定的通信網(wǎng)絡(luò) 我們利用最小割最大流算法確定網(wǎng)絡(luò)中所能傳輸?shù)淖畲?信息量h 如果這個(gè)通信網(wǎng)絡(luò)是可解的 那么對(duì)每一個(gè)目的節(jié)點(diǎn) 我們都可以找到h 條邊 不相互重合的路徑 這h 條路徑組成了此目的節(jié)點(diǎn)的一個(gè)流 此網(wǎng)絡(luò)的最大信息傳輸量是 h 個(gè)符號(hào) 所以我們沿著每個(gè)目的節(jié)點(diǎn)的流上的h 條路徑 在每條路徑上分別傳輸一個(gè)符 號(hào) 則可實(shí)現(xiàn)所要的通信 也就是說 對(duì)每個(gè)目的節(jié)點(diǎn)的h 條路徑 它們傳輸了目的節(jié)點(diǎn) 所要的全部信息 所以這h 條路徑上的全局編碼向量必須張成整個(gè)信息空間 這種確定全 局編碼向量的方法可以在多項(xiàng)式時(shí)間內(nèi)完成 1 9 南京郵電大學(xué)碩上研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 圖2 4 線性碼組播 2 2 2 2 代數(shù)方法構(gòu)造線性網(wǎng)絡(luò)編碼 r k o e t t e r 和m m e d a r d 4 7 4 8 從另一個(gè)角度出發(fā) 提出了用抽象代數(shù)理論描述網(wǎng)絡(luò) 編碼的方法 該算法需要知道整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔⑶闆r 通過構(gòu)造符合要求的系統(tǒng)轉(zhuǎn)移矩 陣來實(shí)現(xiàn)網(wǎng)絡(luò)編碼 該算法雖然是一種指數(shù)時(shí)間算法 但為網(wǎng)絡(luò)編碼的實(shí)際實(shí)施提供了方 向 一 數(shù)學(xué)模型 定義2 1 1 g v 占 是無延遲的通信網(wǎng)絡(luò) 如果對(duì)于網(wǎng)絡(luò)中的每一條邊p v 群 e 上的隨 機(jī)過程y e 均滿足 v e x 1 z 歷 y e 2 2 0 1 1 g h e a d e t a i l e 在目的節(jié)點(diǎn) 處有 z v i 乃 y e 2 2 1 g h e a d e v 則稱這樣的g 為域t 上的線性網(wǎng)絡(luò) 其中 系數(shù)口 尾 一 勺 被稱為局部編碼向量 是有限域 中的元素 如圖2 5 所示 定義2 1 2 組播通信網(wǎng)絡(luò)g v e 中 信源s 礦的輸入可以看作是有限域只 上的向量 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 仃 仃2 o r 采用線性網(wǎng)絡(luò)編碼后 邊口 y 甜 e 上傳送的信息y 是信源輸入符號(hào) 向量的線性組合 用一個(gè)向量v e e 來表示組合的系數(shù)向量 稱其為全局編碼向量 則有 p v e e 2 2 2 可以看出 全局編碼向量和局部編碼向量之間的關(guān)系是 r e e 2 刪 仆刪 尾 v e e 7 2 2 3 在一個(gè)組播通信網(wǎng)絡(luò)中實(shí)現(xiàn)網(wǎng)絡(luò)編碼 可以通過對(duì)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)上的全局編碼向 量和局部編碼向量進(jìn)行必要的操作 所以如果一個(gè)通信網(wǎng)絡(luò)是可解的 那么網(wǎng)絡(luò)編碼的求 解可以通過兩個(gè)途徑實(shí)現(xiàn) 確定全局編碼向量或者確定局部編碼向量 它們具有同等的作 用 從向量角度出發(fā)實(shí)現(xiàn)網(wǎng)絡(luò)編碼 是求解全局編碼向量 求解