（信息與通信工程專業(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é)點上對所要求傳送的消息作 適當?shù)木€性或非線性處理來改善網(wǎng)絡(luò)的傳輸效率 可靠性 魯棒性 安全性 節(jié)點能耗等 性能 是有別于傳統(tǒng)方法的一種新的思路 因而受到高度重視 成為當前網(wǎng)絡(luò)信息論中一 個重要的研究方向 與多數(shù)技術(shù)一樣 網(wǎng)絡(luò)編碼在充分利用網(wǎng)絡(luò)理論組播速率的同時 也 伴隨著對應(yīng)的開銷 如何在應(yīng)用網(wǎng)絡(luò)編碼技術(shù)充分利用網(wǎng)絡(luò)傳輸能力的同時 盡可能地減 少付出的各種開銷 是網(wǎng)絡(luò)編碼在實際應(yīng)用中所要解決的重要問題 本文首先對網(wǎng)絡(luò)編碼進行了綜述 介紹了它的理論背景 研究概況和發(fā)展趨勢 重點 討論了當前它在無線網(wǎng)絡(luò)中的一些應(yīng)用及優(yōu)勢 并針對其中一種基于稀疏網(wǎng)絡(luò)編碼的p 2 p 內(nèi)容分發(fā)算法進行了詳細研究和仿真驗證 仿真實驗表明 與一般網(wǎng)絡(luò)編碼相比 稀疏網(wǎng) 絡(luò)編碼能夠減小分發(fā)系統(tǒng)中編碼分塊的線性相關(guān)性 降低編碼計算復(fù)雜度 并且解碼成功 率較高 與無編碼的分發(fā)系統(tǒng)相比 基于稀疏網(wǎng)絡(luò)編碼的分發(fā)系統(tǒng)在吞吐量 平均下載時 間和總分發(fā)時間等方面的性能都要優(yōu)于前者 雖然在多數(shù)需要承載廣播業(yè)務(wù)的網(wǎng)絡(luò)中 網(wǎng)絡(luò)編碼技術(shù)的引入可以提高和改善多項網(wǎng) 絡(luò)性能指標 但由于網(wǎng)絡(luò)編碼是在各個節(jié)點處對接收的信息進行組合后發(fā)送出去 因此數(shù) 據(jù)包在傳遞的過程中很容易被篡改或遭受其他類型的攻擊 信息的安全性遇到了嚴重的考 驗 為此 本文還重點研究了網(wǎng)絡(luò)編碼在安全性方面的應(yīng)用 討論了抵御不同安全攻擊的 網(wǎng)絡(luò)編碼方案 其中以竊聽攻擊為研究重點 同時 本文還針對網(wǎng)絡(luò)的外部竊聽攻擊提出 了一種改進的安全網(wǎng)絡(luò)編碼方案 從理論上證明了其安全性和可達性 并證明該方案的計 算復(fù)雜度較已有方案更低 最后 論文就今后工作的發(fā)展方向提出了一些個人的觀點和看法 關(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ò)編碼 隨機線性網(wǎng)絡(luò)編碼 無線組播特性 實際網(wǎng)絡(luò)編碼 對等網(wǎng)絡(luò) 稀疏線性網(wǎng)絡(luò)編碼 竊聽網(wǎng)絡(luò)上的通信系統(tǒng) 無線網(wǎng)狀網(wǎng) 無線傳感器網(wǎng)絡(luò) 線性碼組播 因特網(wǎng)協(xié)議 前向糾錯編碼 多輸入多輸出 分布式天線系統(tǒng) 拒絕服務(wù)攻擊 公鑰基礎(chǔ)設(shè)施 高級加密標準 南京郵電大學(xué)學(xué)位論文原創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得 的研究成果 盡我所知 除了文中特別加以標注和致謝的地方外 論文中不包 含其他人已經(jīng)發(fā)表或撰寫過的研究成果 也不包含為獲得南京郵電大學(xué)或其它 教育機構(gòu)的學(xué)位或證書而使用過的材料 與我一同工作的同志對本研究所做的 任何貢獻均已在論文中作了明確的說明并表示了謝意 研究生簽名 叢鑒日期 南京郵電大學(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)的存 儲一轉(zhuǎn)發(fā)路由方式的基礎(chǔ)上 通過允許對接收的多個數(shù)據(jù)包進行編碼信息融合來增加單次 傳輸?shù)男畔⒘?從而提高網(wǎng)絡(luò)的整體性能 a h l s w e d e 等人 1 于2 0 0 0 年提出了網(wǎng)絡(luò)編碼的概 念 指出對組播網(wǎng)絡(luò)中的某些節(jié)點附加額外的編碼操作 能使源與組播成員間達到最大流 最小割定理所定義的組播速率 網(wǎng)絡(luò)編碼一經(jīng)提出便引起了國際學(xué)術(shù)界的廣泛關(guān)注 其理論和應(yīng)用己成為通信領(lǐng)域研 究的新熱點 網(wǎng)絡(luò)編碼在提高網(wǎng)絡(luò)吞吐量 改善負載均衡 減小傳輸延遲 節(jié)省節(jié)點能耗 增強網(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 分布式文件存儲 1 0 和網(wǎng)絡(luò)安全 4 等領(lǐng)域 經(jīng)過幾年的發(fā)展 網(wǎng)絡(luò)編碼的理論研究己取得重要進展 而其在應(yīng)用基礎(chǔ)和工程實踐方面的研究正在全方位 展開 網(wǎng)絡(luò)編碼己成為一項融合信息論 代數(shù)學(xué) 圖論 網(wǎng)絡(luò)流理論和優(yōu)化理論等多學(xué)科 的交叉技術(shù) 且日益引起更多研究者的關(guān)注 可以說 網(wǎng)絡(luò)編碼對現(xiàn)有的網(wǎng)絡(luò)體系結(jié)構(gòu) 協(xié)議設(shè)計方法 信息交換方式和網(wǎng)絡(luò)管理模式帶來了革命性的變化 國外多所著名大學(xué)如 麻省理工學(xué)院 多倫多大學(xué) 瑞士e p f l 學(xué)院等和多家知名i t 研究機構(gòu)包括微軟研究院 貝 爾實驗室等都在積極開展網(wǎng)絡(luò)編碼的理論和應(yīng)用研究 而國內(nèi)針對網(wǎng)絡(luò)編碼的研究尚處于 起步階段 1 1 網(wǎng)絡(luò)編碼的概念 網(wǎng)絡(luò)通信的目的是在源點和目的節(jié)點之間傳遞信息 因此 網(wǎng)絡(luò)設(shè)計中最基本的問題 就是怎樣增加傳輸?shù)男畔⒘?計算機通信網(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ò)和編碼進行結(jié)合 提出了網(wǎng)絡(luò)編碼的概念 其核心思想是在網(wǎng)絡(luò)中參與傳輸 的節(jié)點不單純地執(zhí)行存儲 轉(zhuǎn)發(fā)功能 而可對來自多條鏈路的數(shù)據(jù)信息進行一定的線性或非 線性處理 即編碼 然后發(fā)送出去 并保證接收節(jié)點可正確恢復(fù)出源節(jié)點所發(fā)送的信息 從而達到通信網(wǎng)絡(luò)的最大容量 最大限度的利用網(wǎng)絡(luò)的現(xiàn)有資源 下面通過一個簡單的例子對網(wǎng)絡(luò)編碼的基本思想進行解釋 圖1 1 所示的通信網(wǎng)絡(luò)是一 個組播網(wǎng)絡(luò) 圖中箭頭代表有向鏈路 假設(shè)每條鏈路容量為1 b i t 單位時間 信源節(jié)點s 向接 墮塞堂皇奎堂堡主里 壅生堂垡堡塞墨二蘭絲絲 收節(jié)點r 1 和r 2 同時發(fā)送兩個比特信息a 和b 圖 a 中采用傳統(tǒng)的多播技術(shù) 節(jié)點s 分別向節(jié)點 1 7 r 鉑2 發(fā)送a g l b 節(jié)點l 和節(jié)點2 再分別將接收到的數(shù)據(jù)轉(zhuǎn)發(fā)給其他節(jié)點 這樣節(jié)點l 可以直接 獲得a 節(jié)點2 可以直接獲得b 但是當a 和b 準備通過節(jié)點3 進行轉(zhuǎn)發(fā)時 由于節(jié)點3 和節(jié)點4 之間的鏈路容量為1 a 或b 必須在此排隊等候一個單位時間 這樣每個接收節(jié)點在單位時間 內(nèi)收到的比特數(shù)為1 5 圖 b 則采用網(wǎng)絡(luò)編碼技術(shù) 中間節(jié)點3 將兩條輸入鏈路上收到的信 息a 和b 進行線性編碼l 得到a o b 異或加 然后送出 在接收節(jié)點r l 處 根據(jù)接收到 的a 和a o b 即可恢復(fù)出來b 同樣 在接收節(jié)點r 2 處也可以恢復(fù)處a 由于解決了節(jié)點3 處 的傳輸瓶頸 每個接收節(jié)點在單位時間都可以收n 2 個比特 并達到了多播的最大流量 a b 圖1 1 網(wǎng)絡(luò)編碼原理圖 網(wǎng)絡(luò)編碼本質(zhì)上是一種編碼算法 支持者們聲稱它可以將現(xiàn)有的網(wǎng)絡(luò)吞吐量提高許 多 同時還能改善網(wǎng)絡(luò)的可靠性和防范攻擊的能力 網(wǎng)絡(luò)編碼技術(shù)最熱心的支持者們說 該技術(shù)將會引發(fā)網(wǎng)絡(luò)的下一代革命 其他人則認為 網(wǎng)絡(luò)編碼技術(shù)更有可能會潛移默化地 改變目前基于路由的網(wǎng)絡(luò)架構(gòu) 1 2 網(wǎng)絡(luò)編碼的研究現(xiàn)狀 自從網(wǎng)絡(luò)編碼的思想提出以來 這個新興的領(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 等在文獻 4 6 中提出了向量空間構(gòu)造線性網(wǎng)絡(luò)編碼的方法 并指出線 性編碼是最簡單的編碼方法 他們將鏈路上輸出的信息分組看成一定有限域下的向量 允 許節(jié)點通過線性方式對信息進行編碼處理然后再傳輸 并證明線性編碼可以達到多播的最 南京郵電大學(xué)碩士研究生學(xué)位論文 第一蘋緒論 大流 ps a n d e r s 等人提出了一種實現(xiàn)網(wǎng)絡(luò)編碼的多項式時間算法 1 3 1 1 5 7 1 將 4 6 1 q b 提出的 網(wǎng)絡(luò)編碼的構(gòu)造進一步簡化 不但把網(wǎng)絡(luò)編碼構(gòu)造的復(fù)雜度從指數(shù)級降到了多項式級 而 且大大降低了網(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 用一個系統(tǒng)轉(zhuǎn)移矩陣來描述信源輸入信息和信宿上接收到的信息之間的關(guān) 系 并通過構(gòu)造符合要求的系統(tǒng)轉(zhuǎn)移矩陣來實現(xiàn)網(wǎng)絡(luò)編碼 這是一種指數(shù)時間算法 算法 復(fù)雜度比較大 上述方法都是基于已知整個網(wǎng)絡(luò)的拓撲信息 幾乎同時有人又提出了不需網(wǎng)絡(luò)拓撲信 息的分布式網(wǎng)絡(luò)編碼和隨機網(wǎng)絡(luò)編碼 分布式網(wǎng)絡(luò)編碼 6 的實現(xiàn)是在網(wǎng)絡(luò)中傳輸?shù)拿總€數(shù) 據(jù)包上留出一些比特用來記載此數(shù)據(jù)包在前面各個節(jié)點上所經(jīng)歷的操作 那么接收節(jié)點就 可以從接收到的數(shù)據(jù)包中直接譯出信源所發(fā)送的信息 這種方法可以在不知道網(wǎng)絡(luò)拓撲信 息的情況下實現(xiàn)網(wǎng)絡(luò)編碼 但是增加了網(wǎng)絡(luò)負載 但是仿真表明 在這個信息組播的過程 中 這種處理方式帶來的負載代價并不大 另一種不需網(wǎng)絡(luò)拓撲的方法是隨機網(wǎng)絡(luò)編碼 3 6 0 即在網(wǎng)絡(luò)的中間節(jié)點上對接收到的信息在一個有限域內(nèi)隨機選擇一個元素作為組 合的系數(shù) 研究已經(jīng)表明 只要有限域取得足夠大 這種方法的失敗率就可以很低 這種 方法帶來的缺點一個是以一定的概率實現(xiàn)正確無誤的傳輸 另一個是需增大通信網(wǎng)絡(luò)中所 需字母表的大小 文獻 3 2 1 提出了基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)糾錯碼的概念 網(wǎng)絡(luò)糾錯碼不同于傳統(tǒng)的基于逐 個鏈路的錯誤糾正的經(jīng)典糾錯碼 它是采用分布式的方式來對整個網(wǎng)絡(luò)中的差錯進行糾 正 只要鏈路上發(fā)生傳輸錯誤的符號數(shù)不超過糾錯范圍 不用經(jīng)過重傳 接收節(jié)點通過一 定的譯碼就可恢復(fù)信息 文獻 1 1 1 1 1 2 將網(wǎng)絡(luò)編碼與卷積碼相結(jié)合 探討了單位延遲網(wǎng)絡(luò) 模型下的網(wǎng)絡(luò)編碼問題 文獻 1 1 3 1 分析了簡單的具有兩接收端的多元網(wǎng)絡(luò)編碼 文獻 1 1 4 探討了相關(guān)信源下的網(wǎng)絡(luò)信息理論 文獻 1 1 5 指出基于差錯控制的網(wǎng)絡(luò)編碼和傳統(tǒng)差錯控 制碼的設(shè)計有很強的聯(lián)系 這為基于差錯控制的網(wǎng)絡(luò)編碼設(shè)計提供了方向 p o p o v s k i 等人 1 0 5 研究了現(xiàn)有各類物理層編碼方案在兩路中繼信道下如何最大化通信 速率的問題 并給出了各方案中對系統(tǒng)性能影響最大的關(guān)鍵要素 文獻 1 0 6 對基于網(wǎng)絡(luò)編 碼的協(xié)作通信進行了系統(tǒng)的理論分析 相對于傳統(tǒng)的協(xié)作方案 基于網(wǎng)絡(luò)編碼的方案在同 等的頻譜效率下可達到更高的分集增益 在提高無線網(wǎng)絡(luò)的吞吐量方面 l e o n g 1 0 0 等提出了 種隨機網(wǎng)絡(luò)編碼算法 并將該 算法與基于在線s t e i n e r 樹生成算法 d i j k s t r a 最短路徑算法和最近節(jié)點優(yōu)先算法的路由算法 進行比較 結(jié)果表明 分布式隨機網(wǎng)絡(luò)編碼方法在組播吞吐量和魯棒性方面要明顯優(yōu)于基 于路由的算法 為了提高能量的利用效率 m i t 的p e t r o v i c 等人提出了一種結(jié)合網(wǎng)絡(luò)編碼的 3 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 對無線信號不進行調(diào)制的策略 1 0 1 該策略由于節(jié)省了模擬器件進行調(diào)制所消耗的能量 降低了節(jié)點成本 因此可以節(jié)省大量能量 k a t t i 等人 9 9 針對無線網(wǎng)狀網(wǎng) w i r e l e s sm e s hn e t w o r k s 提出了基于機會的網(wǎng)絡(luò)編碼 協(xié)議c o p e 并在2 0 個節(jié)點的網(wǎng)絡(luò)測試床上完成了協(xié)議實現(xiàn) 這是網(wǎng)絡(luò)編碼首次在無線環(huán) 境中的協(xié)議層面上的具體實現(xiàn) 文獻 1 6 對基于c o p e 的無線網(wǎng)絡(luò)進行了更深入的理論分 析 并給出了相應(yīng)的性能改進 其他涉及節(jié)能和跨層設(shè)計的研究可參閱文獻 7 5 1 0 7 文獻 1 0 2 針對無線傳感器網(wǎng)絡(luò)提出了一種結(jié)合分布式源編碼和網(wǎng)絡(luò)編碼的優(yōu)化算法 目的是用來提高傳感器網(wǎng)絡(luò)的容錯性和可靠性 同時對分布式源編碼的壓縮效率和網(wǎng)絡(luò)魯 棒性進行了折衷考慮 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ò)編碼的研究熱點之一 它在節(jié)省帶寬資源 提高系統(tǒng)的抗毀性和可擴展性等方面都比無編碼協(xié)議優(yōu)勢明顯 但也面臨著解碼計算復(fù) 雜 延時過大導(dǎo)致系統(tǒng)性能下降的新問題 文獻 8 2 指出 在p 2 p 系統(tǒng)中采用隨機線性碼 僅在編碼塊數(shù)目較少且塊大小合適的情形下 其性能才可接受 m a 等人 8 4 實現(xiàn)了一個 基于稀疏線性編碼策略的p 2 p 內(nèi)容分發(fā)系統(tǒng) 通過鄰居選取 環(huán)路檢測和編碼區(qū)間劃分3 種 策略 降低了各編碼塊間的線性相關(guān)性 提升了系統(tǒng)的整體性能 文獻 1 0 9 提出了一種基 于網(wǎng)絡(luò)編碼的p 2 p 流媒體直播方案 仿真實驗表明 采用網(wǎng)絡(luò)編碼后 節(jié)點的播放質(zhì)量得 到了普遍增強 l a v a 1 1 0 是首個集成網(wǎng)絡(luò)編碼技術(shù)的p 2 p 流媒體協(xié)議實際系統(tǒng) 通過與 己實現(xiàn)的標準流媒體協(xié)議v a n i l l a 比較 網(wǎng)絡(luò)編碼協(xié)議在可用上傳帶寬略大于流媒體所需帶 寬時優(yōu)勢較明顯 a c e d a n s k i 等人 1 2 研究了在多個存儲資源受限的節(jié)點間進行分布式文件存儲的問題 比較了無編碼存儲 基于糾刪碼存儲和采用隨機線性碼存儲3 種策略 仿真結(jié)果表明 基 于隨機線性碼的分布式存儲策略在無需全局文件服務(wù)器的參與時 其性能接近集中式全局 調(diào)度算法 文獻 9 3 關(guān)注基于糾刪碼的文件存儲在保持冗余度不變時 如何最小化網(wǎng)絡(luò)帶 寬的問題 網(wǎng)絡(luò)編碼在通信網(wǎng)絡(luò)安全性方面的應(yīng)用是網(wǎng)絡(luò)編碼研究中逐漸興起的一個領(lǐng)域 也是 本文的研究重點 2 0 0 2 年 y e u n g 和c a i 就網(wǎng)絡(luò)竊聽問題首先進行了研究 1 8 設(shè)計了一種 安全的網(wǎng)絡(luò)編碼 在通信鏈路已經(jīng)被竊聽的情況下 在信源處將原始數(shù)據(jù)和隨機信息結(jié)合 起來進行網(wǎng)絡(luò)編碼設(shè)計 該文獻從理論上證明了此方案使得只有接收方才能正確解碼 竊 聽者得到的信息包和原始數(shù)據(jù)包之間沒有任何相關(guān)性 互信息為零 就信息論而言 是安 全的 f e l d m a n 等人則在 1 8 的基礎(chǔ)上 改進了構(gòu)造方法 并將其提出的定理細化 將組 4 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 播容量和構(gòu)造線性碼所需的字母表大小進行了折衷 1 9 k b h a t t a d 等人 2 3 針對無環(huán)網(wǎng)絡(luò)的組播問題 提出了竊聽者不能得到任何有意義信息 的弱安全網(wǎng)絡(luò)編碼模型 他們通過理論證明 在該模型下 對于計算能力有限的竊聽者來 說 只要它們竊取的獨立信源信息數(shù)小于組播容量 就可以用安全網(wǎng)絡(luò)編碼來進行保密通 信 并且不會降低傳輸速率 同樣是針對竊聽攻擊 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 等 人在文獻 1 0 4 中討論了多源網(wǎng)絡(luò)的安全通信問題 他們在一定竊聽范圍的限制下 利用隨 機網(wǎng)絡(luò)編碼的方法 給出了多源安全網(wǎng)絡(luò)編碼容量的內(nèi)界 外界和線性規(guī)劃界 這些界是 y e u n g 得到的界的推廣 中繼節(jié)點對編碼數(shù)據(jù)的惡意修改可能會導(dǎo)致網(wǎng)絡(luò)編碼使用受限 甚至不可用 因此消 除拜占庭攻擊的影響一直是網(wǎng)絡(luò)編碼安全應(yīng)用研究中各受關(guān)注的問題 文獻 4 提出了一種 用散列函數(shù)檢測拜占庭敵手的方法 首先對原始數(shù)據(jù)進行簡單多項式函數(shù)哈希變換 然后 把得到的結(jié)果添加到每一個原始數(shù)據(jù)包內(nèi) 接收節(jié)點經(jīng)過比較解碼后的數(shù)據(jù)和哈希值就可 以判斷數(shù)據(jù)包是否被修改過 可以防止拜占庭攻擊 j a g g i 等人 3 3 1 0 8 進一步給出了一種 多項式復(fù)雜度的分布式算法 在糾正敵手錯誤的前提下 同時達到最優(yōu)組播速率 該方法 無需對編碼節(jié)點添加新的功能 對無線和有線網(wǎng)絡(luò)均適用 k r o h n 等人 3 6 提出了一種基于 同態(tài)散列函數(shù)的方法 用于檢測被修改的編碼分組 但該方法需要將計算好的散列值預(yù)先 通過其他通道分發(fā)給所有節(jié)點 因此該方法具有一定的局限性 文獻 3 5 乖t j 用橢圓曲線算 法給出了一種適用于網(wǎng)絡(luò)編碼的簽名方案 除了可檢測被修改的分組 還加入了對數(shù)據(jù)的 身份認證功能 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ò)的安全問題 他 們集中研究了如何抵抗針對系統(tǒng)熵或試圖完全阻塞系統(tǒng)的安全攻擊 提出了一種能夠提高 驗證效率的方案 他們還提出一種基于安全隨機校驗和的 能夠防止偽造警報造成的d o s 攻擊的有效機制 o l i v e i r a 等人 4 3 通過研究證明 利用網(wǎng)絡(luò)編碼的優(yōu)勢 可以為傳感器網(wǎng) 絡(luò)設(shè)計出一種密鑰分配方案 它只需要用到少量預(yù)先存儲的密鑰 但仍然可以確保以概率 l 建立共享密鑰連接 并且移動節(jié)點并不知道所分配的密鑰 總而言之 現(xiàn)在關(guān)于網(wǎng)絡(luò)編碼的研究是百家爭鳴 各種方法和應(yīng)用層出不窮 但是 沒有一個統(tǒng)一的標準 而且多數(shù)是基于理論分析 試驗仿真很少 到目前為止 網(wǎng)絡(luò)編碼 應(yīng)用到實際網(wǎng)絡(luò)中去還比較少 所以關(guān)于網(wǎng)絡(luò)編碼的研究還有很多東西去做 5 南京郵電大學(xué)碩士研究生學(xué)位論文第一章緒論 1 3 論文主要工作及章節(jié)安排 本文在對網(wǎng)絡(luò)編碼的基本理論進行深入學(xué)習(xí)和研究的基礎(chǔ)上 著重討論其在無線網(wǎng)絡(luò) 和網(wǎng)絡(luò)安全中應(yīng)用時的性能增益 首先 重點研究一種基于稀疏網(wǎng)絡(luò)編碼的p 2 p 內(nèi)容分發(fā) 算法 并對其進行詳細研究和仿真驗證 仿真實驗表明 與一般網(wǎng)絡(luò)編碼相比 稀疏網(wǎng)絡(luò) 編碼能夠減小分發(fā)系統(tǒng)中編碼分塊的線性相關(guān)性 降低編碼計算復(fù)雜度 并且解碼成功率 較高 與無編碼的分發(fā)系統(tǒng)相比 基于稀疏網(wǎng)絡(luò)編碼的分發(fā)系統(tǒng)在吞吐量 平均下載時間 和總分發(fā)時間等方面的性能都要優(yōu)于前者 此外 本文還將對網(wǎng)絡(luò)編碼的安全性進行重點 研究 討論抵御不同安全攻擊的網(wǎng)絡(luò)編碼方案 同時針對網(wǎng)絡(luò)的外部竊聽攻擊提出一種改 進的安全網(wǎng)絡(luò)編碼方案 從理論上證明其安全性和可達性 且具有較低的計算復(fù)雜度 本文共分六章 其余幾章安排如下 第二章對網(wǎng)絡(luò)編碼的基本理論進行討論 先對網(wǎng)絡(luò)編碼的數(shù)學(xué)模型和原理進行研究 然后依次介紹線性網(wǎng)絡(luò)編碼 隨機網(wǎng)絡(luò)編碼和實際網(wǎng)絡(luò)編碼的概念 最后總結(jié)網(wǎng)絡(luò)編碼的 性能優(yōu)點 第三章首先介紹網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的一些典型應(yīng)用 接著就p 2 p 內(nèi)容分發(fā)問題 著重研究一種基于稀疏網(wǎng)絡(luò)編碼的內(nèi)容分發(fā)系統(tǒng) 并通過性能仿真 驗證稀疏網(wǎng)絡(luò)編碼的 優(yōu)越性 最后 通過從安全性角度將網(wǎng)絡(luò)編碼方案分類以及將各種安全攻擊歸類 引出網(wǎng) 絡(luò)編碼在安全性方面的研究 第四章研究如何利用網(wǎng)絡(luò)編碼的特性來抵抗各種不同的安全攻擊 其中重點研究抵抗 竊聽攻擊的網(wǎng)絡(luò)編碼方案 并對方案性能進行了詳細分析 第五章針對竊聽問題 在前人工作的基礎(chǔ)上 提出一種改進的網(wǎng)絡(luò)編碼方案 并對其 性能進行驗證 第六章總結(jié)全文的工作 并指出今后有待進一步深入研究的一些問題 6 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 本章首先從通信網(wǎng)絡(luò)的角度出發(fā) 介紹了圖論的相關(guān)知識 在此基礎(chǔ)上引出了網(wǎng)絡(luò)編 碼的基本原理及數(shù)學(xué)模型 并從信息論角度出發(fā)證明了其可以實現(xiàn)網(wǎng)絡(luò)中的最大流 而這 是傳統(tǒng)路由方式無法達到的 接著 本章重點描述了網(wǎng)絡(luò)編碼最主要的實現(xiàn)方式一線性網(wǎng) 絡(luò)編碼的原理以及兩種從不同角度出發(fā)的構(gòu)造方法 同時分析了線性網(wǎng)絡(luò)編碼的局限性 之后 本章研究了線性網(wǎng)絡(luò)編碼中最重要 也是最為實用的兩種方案一隨機網(wǎng)絡(luò)編碼和實 際網(wǎng)絡(luò)編碼 最后 本章從增加網(wǎng)絡(luò)容量以及節(jié)省網(wǎng)絡(luò)帶寬兩個角度分析了網(wǎng)絡(luò)編碼技術(shù) 的優(yōu)點 2 1 網(wǎng)絡(luò)編碼的數(shù)學(xué)模型 2 1 1 網(wǎng)絡(luò)編碼的預(yù)備知識一圖論和網(wǎng)絡(luò)流圖 2 1 1 1 圖論基礎(chǔ) 一個圖是由一些節(jié)點和連接兩個節(jié)點之間的連線所組成 至于連線的長度及節(jié)點的位 置是無關(guān)緊要的 定義2 1 一個圖是一個三元組 y g e g 哆 其中y g 是一個非空的節(jié)點集合 e g 是邊集合 唾是從邊集合e g 到節(jié)點無序偶 有序偶 集合上的函數(shù) 若把圖中的邊e l 看作總是與兩個節(jié)點關(guān)聯(lián) 那么一個圖亦可簡記為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 上的 i j e 矗一g 口一碼對于 所有的邊 f e 均滿足 刀一l 0 9 2r f r g 2 1 2 這里理 l o g 7 是編碼后鏈路 f 力上的平均比特速率 定義2 8 兄 g 豆 天 h g 是口一可達的 定義2 9 有向圖g v e 中 信源為s 信宿f 1 t l 邊 f 力上的容量為r 則 硝 g 天 s 至l j t 1 1 乙 的最大流 塒 定理2 3 1 r 加 尺三g 文獻 1 給出了上述定理的詳細證明 此處從略 通過有關(guān)熵的理論 該定理證明了通 過網(wǎng)絡(luò)編碼 可以使網(wǎng)絡(luò)的傳輸容量達到最大流最小割給出的理論限 2 2 線性網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)編碼方案可分為線性和非線性兩種 所謂線性網(wǎng)絡(luò)編碼 4 6 也就是在實現(xiàn)網(wǎng)絡(luò)編 碼過程中所用到的編碼函數(shù)和譯碼函數(shù)均采用線性函數(shù)來實現(xiàn) 線性網(wǎng)絡(luò)編碼是中間節(jié)點 將接收數(shù)據(jù)在某有限域內(nèi)進行線性組合 節(jié)點接收足夠數(shù)量的獨立數(shù)據(jù)包就可以通過正確 譯碼解得全部信息內(nèi)容 能充分利用網(wǎng)絡(luò)帶寬 假設(shè)每個信息數(shù)據(jù)包為l 比特 當它與要 l s 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 組合的數(shù)據(jù)包長度不同時 較短的信息附加額外一串 0 將包中的j 個連續(xù)比特組成域 上的一個符號 則一個包中包含三 j 個符號 在線性編碼下 運用乘法和加法運算 使從 節(jié)點發(fā)送出去的數(shù)據(jù)為 該節(jié)點接收到信息的線性組合 5 6 文獻 1 3 4 6 4 8 5 3 5 4 5 5 等都討論了線性網(wǎng)絡(luò)編碼 的原理及實現(xiàn)問題 2 2 1 線性網(wǎng)絡(luò)編碼的基本原理 下面介紹線性網(wǎng)絡(luò)編碼的基本原理 即如何進行編碼和解碼操作 2 2 1 1 編碼過程 假設(shè)一個源或多個源產(chǎn)生的原始數(shù)據(jù)包信息為m 則在線性網(wǎng)絡(luò)編碼中傳輸?shù)?數(shù)據(jù)可表示為 x g 鳩 2 1 3 i 1 其中蜀 g n 表示相應(yīng)的編碼系數(shù) 對每個符號有 彳七 膨 2 1 1 其中 彬和x 分別表示必和x 的第k 個符號 傳輸?shù)臄?shù)據(jù)包中既包括編碼向量 又包括信息向量 編碼向量用于接收端的 解碼 編碼過程采用迭代的方法 若一個節(jié)點己經(jīng)接收和存儲的包信息集合為 五 g 厶 則該節(jié)點可以通過選定編碼系數(shù)曩 和運用算式 2 1 5 得到新 的信息包刀 x 么t 2 1 5 l 編碼向量g 可以通過 直接的代數(shù)計算得到 該過程可以在若干個節(jié)點中重復(fù)操作 g 乃g 2 1 6 l 2 2 1 2 解碼過程 假設(shè)節(jié)點接收集合為 g l 墨 以 為了恢復(fù)原始信息 需要求解 2 2 0 中的 1 6 南京郵電大學(xué)碩士研究生學(xué)位論文第二章網(wǎng)絡(luò)編碼基礎(chǔ) m 個等式中的甩個未知數(shù)必 因此恢復(fù)所有數(shù)據(jù)要求腳 刀 也就是說接收包的個數(shù)至少 要為原信息的個數(shù) 而有些線性組合可能是線性相關(guān)的 所以歷 r l 并不是充分條件 但 卻是網(wǎng)絡(luò)編碼的重要條件 g j m 2 1 7 j l 解碼需要求解一組線性方程 實際中 可以應(yīng)用高斯消去的方法 節(jié)點存儲編碼向量 以及編碼之后的結(jié)果 以行向量的形式 存儲在所謂解碼矩陣中 最初解碼矩陣中只包含 未經(jīng)該節(jié)點編碼的包以及與之相對應(yīng)的編碼向量 如果有的話 否則為空 當接收到一個 已編碼包后 會從中抽取它的編碼向量以及編碼結(jié)果 放入到解碼矩陣中 解碼矩陣會經(jīng) 過等價變換變成行階梯型 最終變成行最簡型 如果所收到的某一個包可以增加矩陣的秩 則稱之為更新包 如果所收到的包是非更新的 它可以通過等價變換變?yōu)槿?從而可以 忽略 當解碼矩陣變換成最簡型后 方程組得解 這種情況發(fā)生在當接收到以個線性獨立 的編碼向量之后 2 2 2 線性網(wǎng)絡(luò)編碼的實現(xiàn)方案 編碼向量的選取可以采用確定性編碼策略和隨機編碼策略 確定性的方案是根據(jù)網(wǎng)絡(luò)拓撲為節(jié)點選取確定的編碼向量 y e u n g 等人 4 6 提出了線 性網(wǎng)絡(luò)編碼的向量實現(xiàn)方法 通過分析網(wǎng)絡(luò)結(jié)構(gòu) 根據(jù)節(jié)點的輸入輸出個數(shù)設(shè)計相應(yīng)的局 部編碼向量 用迭代的方式得到全局編碼向量 從而實現(xiàn)網(wǎng)絡(luò)編碼 k o e t t e r 等人 4 7 則提 出了較為完備的線性網(wǎng)絡(luò)編碼的代數(shù)實現(xiàn)方法 但他們的方法運算量太高 于是j a g g i 等 人 1 3 5 7 又提出了一種確定的多項式時間編碼設(shè)計算法 可以為特定的廣播網(wǎng)絡(luò)找到可行 的網(wǎng)絡(luò)編碼 目前已有對此算法的各種改進 確定性的編碼方案由于每個節(jié)點應(yīng)用的都是固定的編碼向量 因此網(wǎng)絡(luò)中傳 遞的數(shù)據(jù)中只需要包含信息向量 節(jié)省帶寬 并且所需的符號域比較小 但確定 性的網(wǎng)絡(luò)編碼需要了解全網(wǎng)的情況 拓撲結(jié)構(gòu)等 復(fù)雜度比較高 難于分布式地實現(xiàn) 一旦網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生了變化 就必須對整個編碼方案進行修改 對無線環(huán)境變化的魯棒 性比較差 由于確定性網(wǎng)絡(luò)編碼的以上缺點 h o 和m e d a r d 等人 2 1 1 5 8 1 提出了隨機網(wǎng)絡(luò)編碼的概 念 隨機網(wǎng)絡(luò)編碼是讓網(wǎng)絡(luò)中的節(jié)點以完全獨立的分布式方式 隨機選取編碼系數(shù) 對輸 入信息編碼 并把這組隨機向量作為報頭的一部分發(fā)送給收點 以便于解碼 已經(jīng)證明 1 7 南京郵屯大學(xué)碩士研究生學(xué)位論文第二章網(wǎng)絡(luò)編碼基礎(chǔ) 隨機方式選取的編碼向量成功的概率為1 1 i f l 其中f 為編碼的符號域 當符號域為無 窮大時 采用隨機編碼 系統(tǒng)傳輸矩陣滿秩的概率為 1 隨機編碼可以分布式地實現(xiàn) 并可增加保密性 文獻 4 7 提出的代數(shù)實現(xiàn)框架指出 線性網(wǎng)絡(luò)編碼可以通過隨機編碼有效地構(gòu)建 c h o u 6 應(yīng)用隨機編碼 提出了第一個實用的 網(wǎng)絡(luò)編碼方案 為了保證隨機編碼成功概率 編碼向量的符 號域必須足夠大 這可能會增加數(shù)據(jù)包頭部的負擔(dān) 因此符號域的大小必須仔細 選擇 確定性編碼和隨機編碼分別用于不同的網(wǎng)絡(luò)應(yīng)用與構(gòu)架上 這些方案主要是基于理論 上的分析和實現(xiàn) 因此在實際網(wǎng)絡(luò)上需要針對不同的應(yīng)用設(shè)計相應(yīng)的編碼方式 如對于結(jié) 構(gòu)較小的網(wǎng)絡(luò) 可以選擇比較簡單的確定性算法 編碼過程中甚至可以通過轉(zhuǎn)換為對數(shù) 將乘法運算轉(zhuǎn)換成加法運算 降低總的編碼復(fù)雜度 而對于無線網(wǎng)絡(luò) 則應(yīng)用隨機編碼機 制是主要的研究趨勢 即令中間節(jié)點隨機生成編碼系數(shù) 對節(jié)點所有的可用信息應(yīng)用線性 編碼 并隨時更新編碼系數(shù) 還有一種半隨機的編碼方案 整個網(wǎng)絡(luò)被化分成若干區(qū)域 各區(qū)域都采用隨機編碼 但為了保證傳輸矩陣滿秩 區(qū)域間要相互傳遞信息 以使每個區(qū) 域在選擇編碼向量時盡量不選可能導(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ò)編碼實現(xiàn)以后 4 6 首先給出了網(wǎng)絡(luò) 編碼的具體實現(xiàn)方法 之后 1 3 5 7 又從信息流的角度對以上方法進行了簡化 把算法的 時間復(fù)雜度從指數(shù)級降到了多項式時間級 設(shè)d 表示信源s 和任一非信源節(jié)點丁的最大流m a x f l o w t 的最大值 q 表示一足夠大 基域f 上的d 維向量空間 這里采用的信息速率單位為每單位時間信道上可以傳輸一個基 域上的符號 定義2 1 0 1 4 6 通信網(wǎng)絡(luò) g s 上的一個線性碼組播 l i n e a r c o d em u l t i c a s t l c m v 是 對每一節(jié)點x 分配一個向量空間v x 每一信道 x n e 分配一個全局編碼向量 v x 功 使得它們滿足以下條件 1 1 s q 2 對每一信道 腭有 v x n v x 3 對于網(wǎng)絡(luò)中的任何非信源節(jié)點集合 有 1 8 南京郵電大學(xué)碩士研究生學(xué)位論文 第二章網(wǎng)絡(luò)編碼基礎(chǔ) 1 r r 艫 v 盯 x 茌矽 y 矽 2 1 8 4 給節(jié)點t 的輸出邊分配的編碼向量是其輸入邊所分配的編碼向量的線性組合 符號 表示線性張成 l c my 刻畫了一種信息數(shù)據(jù)在網(wǎng)絡(luò)中傳播的結(jié)構(gòu) 開始將源 節(jié)點s 中要傳輸?shù)男畔⒎殖蒬 維的向量組 稱作信息向量 在傳輸過程中 每條信道上承 載的數(shù)據(jù)符號是信息向量和該信道所分配的編碼向量的向量積 圖2 4 b 就是一個線性編碼組播的例子 在該例中 網(wǎng)絡(luò)編碼的的基域為五 每一條 鏈路分配的編碼列向量為 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ù)男畔⒎枮樾畔⑾蛄?a b 和該鏈路 編碼列向量的向量積 對于一個線性網(wǎng)絡(luò)編碼組播 如果所有接收節(jié)點能夠恢復(fù)出信源發(fā) 送的信息向量 則稱其為有效的線性編碼組播 當網(wǎng)絡(luò)中的任何m 1 m d 條鏈路 x z x e l 匕對應(yīng)的編碼向量線性無關(guān)時 就可以保證任何接收點能夠恢復(fù)出信源的 信息向量 當編碼符號域足夠大時 就可以保證這一點成立 可以驗證 上述線性碼組播可以實現(xiàn)圖2 4 b 中網(wǎng)絡(luò)的通信 但是對于任意復(fù)雜的通 信網(wǎng)絡(luò) 如何找到其所有的全局編碼向量呢 p s a n d e r s 等人 1 3 5 7 1 針對組播網(wǎng)絡(luò)給出了 一種多項式時間算法 現(xiàn)把其主要思想介紹如下 這種多項式時間算法是對從向量空間角度構(gòu)造線性網(wǎng)絡(luò)編碼的方法進行的簡化 4 6 首先 對于任意給定的通信網(wǎng)絡(luò) 我們利用最小割最大流算法確定網(wǎng)絡(luò)中所能傳輸?shù)淖畲?信息量h 如果這個通信網(wǎng)絡(luò)是可解的 那么對每一個目的節(jié)點 我們都可以找到h 條邊 不相互重合的路徑 這h 條路徑組成了此目的節(jié)點的一個流 此網(wǎng)絡(luò)的最大信息傳輸量是 h 個符號 所以我們沿著每個目的節(jié)點的流上的h 條路徑 在每條路徑上分別傳輸一個符 號 則可實現(xiàn)所要的通信 也就是說 對每個目的節(jié)點的h 條路徑 它們傳輸了目的節(jié)點 所要的全部信息 所以這h 條路徑上的全局編碼向量必須張成整個信息空間 這種確定全 局編碼向量的方法可以在多項式時間內(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 從另一個角度出發(fā) 提出了用抽象代數(shù)理論描述網(wǎng)絡(luò) 編碼的方法 該算法需要知道整個網(wǎng)絡(luò)的拓撲信息情況 通過構(gòu)造符合要求的系統(tǒng)轉(zhuǎn)移矩 陣來實現(xiàn)網(wǎng)絡(luò)編碼 該算法雖然是一種指數(shù)時間算法 但為網(wǎng)絡(luò)編碼的實際實施提供了方 向 一 數(shù)學(xué)模型 定義2 1 1 g v 占 是無延遲的通信網(wǎng)絡(luò) 如果對于網(wǎng)絡(luò)中的每一條邊p v 群 e 上的隨 機過程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é)點 處有 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 是信源輸入符號 向量的線性組合 用一個向量v e e 來表示組合的系數(shù)向量 稱其為全局編碼向量 則有 p v e e 2 2 2 可以看出 全局編碼向量和局部編碼向量之間的關(guān)系是 r e e 2 刪 仆刪 尾 v e e 7 2 2 3 在一個組播通信網(wǎng)絡(luò)中實現(xiàn)網(wǎng)絡(luò)編碼 可以通過對網(wǎng)絡(luò)中的各個節(jié)點上的全局編碼向 量和局部編碼向量進行必要的操作 所以如果一個通信網(wǎng)絡(luò)是可解的 那么網(wǎng)絡(luò)編碼的求 解可以通過兩個途徑實現(xiàn) 確定全局編碼向量或者確定局部編碼向量 它們具有同等的作 用 從向量角度出發(fā)實現(xiàn)網(wǎng)絡(luò)編碼 是求解全局編碼向量 求解