第91章：圖論補(bǔ)充內(nèi)容

第91章：圖論補(bǔ)充內(nèi)容第一頁(yè)，共197頁(yè)。圖的連通性網(wǎng)絡(luò)流網(wǎng)絡(luò)編碼圖著色超圖第二頁(yè)，共197頁(yè)。圖的連通性之前介紹過(guò)割點(diǎn)、割邊、連通圖的概念；這里再補(bǔ)充一些概念和理論。在連通圖中，連通的程度也是有高有低；定義一種參數(shù)來(lái)度量連通圖連通程度的高低。第三頁(yè)，共197頁(yè)。割點(diǎn)定義：設(shè)，如果，則稱v為G的一個(gè)割點(diǎn)。w(G)表示圖G的連通分支數(shù)。uv去掉v后，連通分支增加了第四頁(yè)，共197頁(yè)。點(diǎn)割集（頂點(diǎn)割集）定義：對(duì)圖G，若V(G)的子集V’使得，則稱V’為圖G的一個(gè)點(diǎn)割集；含有k個(gè)頂點(diǎn)的點(diǎn)割集稱為k-點(diǎn)割集；若V’是圖G的一個(gè)點(diǎn)割集，而V’減少任意一個(gè)點(diǎn)都不再是G的點(diǎn)割集，則稱V’是G的一個(gè)極小點(diǎn)割集；G中含點(diǎn)數(shù)最少的點(diǎn)割集稱為G的最小點(diǎn)割集。說(shuō)明割點(diǎn)是1－頂點(diǎn)割集；完全圖沒(méi)有點(diǎn)割集。uv{u,v}是2-點(diǎn)割集第五頁(yè)，共197頁(yè)。連通度定義：連通度為是G的頂點(diǎn)割集}完全圖的連通度定義為，空?qǐng)D的連通度定義為0；使得的頂點(diǎn)割集V’就是G的最小點(diǎn)割集；若，則稱G為k連通的；若G不連通，則；若G是平凡圖，則；所有非平凡連通圖都是1-連通的。第六頁(yè)，共197頁(yè)。割邊定義：設(shè)，如果，則稱e為G的一條割邊。邊e是G的割邊當(dāng)且僅當(dāng)e不在G的任何回路中；一個(gè)連通圖是樹(shù)當(dāng)且僅當(dāng)它的每條邊都是割邊。uv第七頁(yè)，共197頁(yè)。邊割集定義：對(duì)圖G，若E(G)的子集E’使得，則稱E’為圖G的一個(gè)邊割集。含有k條邊的邊割集稱為k-邊割集。對(duì)非平凡圖G，若E’是一個(gè)邊割集，則不連通；一條割邊構(gòu)成一個(gè)1－邊割集；設(shè)，，，記號(hào)[S,S’]

表示一端在S中另一端在S’中的所有邊的集合。對(duì)圖G的每個(gè)邊割集，必存在非空的，使得是G的一個(gè)邊割集，其中。若E’是圖G的一個(gè)邊割集，而E’減少任意一條邊都不再是G的邊割集，則稱E’是G的一個(gè)極小邊割集；G中含邊數(shù)最少的邊割集稱為G的最小邊割集。第八頁(yè)，共197頁(yè)。邊連通度：定義：完全圖的邊連通度定義為；空?qǐng)D的邊連通度定義為0；對(duì)平凡圖或不連通圖G，；若圖G是含有割邊的連通圖，則；若，則稱G為k－邊連通的；所有非平凡連通圖都是1－邊連通的；使得的邊割集E’就是G的最小邊割集。定理：

圖G的結(jié)點(diǎn)中最小的度

點(diǎn)連通度

邊連通度第九頁(yè)，共197頁(yè)。可靠通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題描述：要設(shè)計(jì)一個(gè)有線通訊網(wǎng)，使得敵人炸壞幾通訊站后，其余的通訊站仍然可彼此通話；顯然，有兩個(gè)要求是必要的：一是不怕被敵人炸壞站的數(shù)目要多，一是整個(gè)造價(jià)要小?？煽烤W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題：給定賦權(quán)圖G和正整數(shù)m，求G的具有最小權(quán)的m連通生成子圖；當(dāng)m=1時(shí)，就是求最小生成樹(shù)問(wèn)題；當(dāng)m>1時(shí)，問(wèn)題尚未解決；當(dāng)G=Kn且每邊權(quán)皆為1時(shí)，問(wèn)題成為：求Kn中邊數(shù)最少的m-連通生成子圖。這一問(wèn)題于1962年由Harary解決。第十頁(yè)，共197頁(yè)。網(wǎng)絡(luò)流簡(jiǎn)介網(wǎng)絡(luò)流理論是圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類(lèi)最優(yōu)化問(wèn)題；1955年，T.E.哈里斯在研究鐵路最大通量時(shí)首先提出在一個(gè)給定的網(wǎng)絡(luò)上尋求兩點(diǎn)間最大運(yùn)輸量的問(wèn)題。1956年，L.R.福特和D.R.富爾克森等人給出了解決這類(lèi)問(wèn)題的算法，從而建立了網(wǎng)絡(luò)流理論；目前網(wǎng)絡(luò)流的理論和應(yīng)用在不斷發(fā)展，出現(xiàn)了具有增益的流、多終端流、多商品流以及網(wǎng)絡(luò)流的分解與合成等新課題；網(wǎng)絡(luò)流的應(yīng)用已遍及通訊、運(yùn)輸、電力、工程規(guī)劃、任務(wù)分派、設(shè)備更新以及計(jì)算機(jī)輔助設(shè)計(jì)等眾多領(lǐng)域。第十一頁(yè)，共197頁(yè)。引例：運(yùn)輸方案連接產(chǎn)品產(chǎn)地V1和銷(xiāo)地V6的交通網(wǎng)，每一條邊（Vi，Vj）表示從Vi到Vj的運(yùn)輸線，產(chǎn)品經(jīng)這條邊由Vi輸送到Vj，邊上的數(shù)字表示這條運(yùn)輸線的最大通行能力（簡(jiǎn)稱容量）；產(chǎn)品經(jīng)過(guò)交通網(wǎng)從V1輸送到V6，現(xiàn)要求制定一個(gè)輸送方案，使得從V1運(yùn)到V6的產(chǎn)品數(shù)量最多。1234544842產(chǎn)地6銷(xiāo)地1273第十二頁(yè)，共197頁(yè)。下面考慮可行的輸送方案，用邊上方框內(nèi)的數(shù)字表示該運(yùn)輸線的實(shí)際運(yùn)輸量（單位：噸）：運(yùn)輸方案：2噸產(chǎn)品沿有向路P1（V1，V2，V4，V6）運(yùn)到銷(xiāo)地；1噸產(chǎn)品沿有向路P2（V1，V2，V5，V6）運(yùn)到銷(xiāo)地；2噸產(chǎn)品沿有向路P3（V1，V3，V5，V6）運(yùn)到銷(xiāo)地。1234544842產(chǎn)地6銷(xiāo)地1273222122112注意：需要滿足實(shí)際的物理限制！第十三頁(yè)，共197頁(yè)。1234544842產(chǎn)地6銷(xiāo)地12732221221121234544842產(chǎn)地6銷(xiāo)地12733221223合并各個(gè)邊上的運(yùn)輸量，得到運(yùn)輸方案總共有5噸產(chǎn)品從V1運(yùn)到V6第十四頁(yè)，共197頁(yè)。1234544842產(chǎn)地6銷(xiāo)地12733221223可行的運(yùn)輸方案必須滿足以下三個(gè)條件：實(shí)際運(yùn)輸量不能是負(fù)的；每條邊的實(shí)際運(yùn)輸量不能大于該邊的容量；除了起點(diǎn)V1和終點(diǎn)V6，對(duì)其它結(jié)點(diǎn)（中間點(diǎn)）來(lái)說(shuō)，不能囤積物資，即運(yùn)到它那兒的物資是多少，從它那兒運(yùn)走的物資也應(yīng)該是多少。

思考：有沒(méi)有可能改進(jìn)運(yùn)輸方案？即根據(jù)這個(gè)運(yùn)輸網(wǎng)，是否可增大運(yùn)輸量？第十五頁(yè)，共197頁(yè)?？梢哉业揭粭l有向路：P4（V1,V2,V3,V4,V6）能再增加1噸運(yùn)輸量1234544842產(chǎn)地6銷(xiāo)地12734221123311234544842產(chǎn)地6銷(xiāo)地12733221223第十六頁(yè)，共197頁(yè)。P5（V1，V3，V4，V6）也可再增加1噸運(yùn)輸量1234544842產(chǎn)地6銷(xiāo)地1273432122431思考：還能再增加運(yùn)輸量嗎？1234544842產(chǎn)地6銷(xiāo)地1273422112331第十七頁(yè)，共197頁(yè)。觀察有向路P6（V1，V3，V2，V4，V6）正方向的邊（V1，V3）、（V2，V4）、（V4，V6）都可增加運(yùn)輸量；反方向的邊（V3，V2）的運(yùn)輸量為1；1234544842產(chǎn)地6銷(xiāo)地1273432122431第十八頁(yè)，共197頁(yè)。如果將反向邊（V3，V2）的運(yùn)量調(diào)到正向邊（V2，V4）上去完成，這樣有向路P6（V1，V3，V2，V4，V6）的運(yùn)量可增加1。1234544842產(chǎn)地6銷(xiāo)地1273432122431反向邊上流量含義：節(jié)點(diǎn)2需要發(fā)出1噸貨物，而節(jié)點(diǎn)3需要接收1噸貨物；可以讓該路徑上的節(jié)點(diǎn)3前一條邊增加流量，保持節(jié)點(diǎn)3的總進(jìn)入流量不變；同時(shí)讓該路徑上節(jié)點(diǎn)2之后的邊上也增加流量，保持節(jié)點(diǎn)2的出發(fā)流量不變。第十九頁(yè)，共197頁(yè)。這里要注意，節(jié)點(diǎn)4到節(jié)點(diǎn)6一定還應(yīng)該有剩余的運(yùn)輸能力。再找不到可“改進(jìn)”的有向路了，該交通網(wǎng)的最大運(yùn)輸量為8噸。1234544842產(chǎn)地6銷(xiāo)地12734431225301234544842產(chǎn)地6銷(xiāo)地1273432122431第二十頁(yè)，共197頁(yè)。通過(guò)上述實(shí)例分析，包含了流量因素的問(wèn)題，是一類(lèi)特殊的圖；引例給出的交通網(wǎng)，其實(shí)具體的物理模型是多種多樣的：網(wǎng)絡(luò)的有向邊可以表示為城市之間的公路、電信網(wǎng)之間的通訊線路、天然氣站之間的輸氣管道等；邊的容量則可以表示為允許通過(guò)的物資數(shù)量、汽車(chē)數(shù)量、速率或最大信號(hào)流量等。這一類(lèi)特殊的圖，稱為網(wǎng)絡(luò)流圖；網(wǎng)絡(luò)流圖中需要解決的基本問(wèn)題最大流問(wèn)題最大流最小割問(wèn)題最小費(fèi)用最大流問(wèn)題第二十一頁(yè)，共197頁(yè)。流網(wǎng)絡(luò)G=(V,E)是一個(gè)有向圖，其中每條邊(u,v)∈E均有一個(gè)非負(fù)容量c(u,v)>=0；如果(u,v)不屬于E，則假定c(u,v)=0；流網(wǎng)絡(luò)中有兩個(gè)特別的頂點(diǎn)：源點(diǎn)s和匯點(diǎn)t；12345432625411343st一個(gè)流網(wǎng)絡(luò)的實(shí)例（紅色數(shù)字表示邊的最大容量，藍(lán)色數(shù)字表示邊上的實(shí)際流量）第二十二頁(yè)，共197頁(yè)。定義：帶權(quán)的有向圖G=(V,E)，滿足以下條件，則稱為網(wǎng)絡(luò)流圖(flownetwork)：（1）僅有一個(gè)入度為0的頂點(diǎn)s，稱s為源點(diǎn)(source)或出發(fā)點(diǎn)；（2）僅有一個(gè)出度為0的頂點(diǎn)t，稱t為匯點(diǎn)(sink)或結(jié)束點(diǎn)；（3）每條邊(u,v)的權(quán)值都為非負(fù)數(shù)，稱為該邊的容量，記作c(u,v)；滿足上述的條件的圖稱為網(wǎng)絡(luò)流圖，也可以記作記為G=(V,E,c)第二十三頁(yè)，共197頁(yè)。例：一個(gè)網(wǎng)絡(luò)流圖：stabcd44332224132源點(diǎn)容量匯點(diǎn)中間點(diǎn)中間點(diǎn)第二十四頁(yè)，共197頁(yè)。對(duì)一個(gè)流網(wǎng)絡(luò)G=(V,E,c)，每條邊(u,v)上給定一個(gè)實(shí)數(shù)f(u,v)，滿足：0≤f(u,v)

≤c(u,v)，則f(u,v)稱為邊(u,v)上的流量。其中滿足f(u,v)=c(u,v)的邊稱為飽和邊。如果有一組流量滿足條件：源點(diǎn)s：流出量=整個(gè)網(wǎng)絡(luò)的流量匯點(diǎn)t：流入量=

整個(gè)網(wǎng)絡(luò)的流量中間點(diǎn)：總流入量=總流出量

那么整個(gè)網(wǎng)絡(luò)中的流量稱為一個(gè)可行流。

這個(gè)是真實(shí)的實(shí)體網(wǎng)絡(luò)中的情況，如果針對(duì)通信網(wǎng)絡(luò)來(lái)說(shuō)，不一定滿足這樣的條件：比如對(duì)于匯點(diǎn)來(lái)說(shuō)，流入量可能大于整個(gè)網(wǎng)絡(luò)的流量（當(dāng)然多的那些是重復(fù)的，但是它們還是占用了網(wǎng)絡(luò)資源）第二十五頁(yè)，共197頁(yè)。例：一個(gè)網(wǎng)絡(luò)流圖上的可行流：stabcd(4,3)(4,3)(3,2)(3,0)(2,1)(2,2)(2,2)(4,4)(1,1)(3,2)(2,2)容量容許流fat第二十六頁(yè)，共197頁(yè)。整個(gè)流網(wǎng)絡(luò)G的流量為：|f|=∑f(s,v)(v∈V)或|f|=∑f(u,t)(u∈V)

『三個(gè)重要性質(zhì)』容量約束：對(duì)所有的u,v∈V，要求f(u,v)<=c(u,v)；平衡約束（反對(duì)稱性）：對(duì)所有的u,v∈V，要求f(u,v)=-f(v,u)；流守恒性：對(duì)所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。流量平衡方程即從源出發(fā)的所有流的總和或到達(dá)匯的所有流的總和第二十七頁(yè)，共197頁(yè)。根據(jù)各點(diǎn)流量守恒的關(guān)系，可得下列各式：fsa+fsb+fsc=w(1)fat+fbt+fdt=w(2)fsa+fba＝fat+fab

(3)fsb+fcb+fab＝fba+fbt+fbd

(4)fsc＝fcb+fcd

(5)fbd+fcd＝fdt

(6)0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3，0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2，0≤fdt≤2，w≥0stabcd44332224132第二十八頁(yè)，共197頁(yè)。2.最大流對(duì)于一個(gè)流網(wǎng)絡(luò)G=(V,E,c)，在其可行流中，流量最大的一個(gè)流就是最大流；注意：最大流可能不止一個(gè)。一個(gè)可行流一個(gè)可行流（也是最大流）12345432625411343st12345432645431343st第二十九頁(yè)，共197頁(yè)。殘留網(wǎng)絡(luò)對(duì)于給定的一個(gè)流網(wǎng)絡(luò)G及其上的一個(gè)流flow，網(wǎng)絡(luò)G關(guān)于流flow的殘留網(wǎng)絡(luò)G*與G有相同的頂點(diǎn)集V，而網(wǎng)絡(luò)G中的每一條邊對(duì)應(yīng)于G*中的1條邊或2條邊。設(shè)(v,w)是G的一條邊：當(dāng)flow(v,w)>0時(shí)，(w,v)是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)；當(dāng)flow(v,w)<cap(v,w)時(shí)，(v,w)是G*中的一條邊，該邊的容量為cap*(v,w)=cap(v,w)-flow(v,w)。注意：兩個(gè)條件可能同時(shí)都成立，因此就對(duì)應(yīng)兩條邊。注意：反向邊注意：正向邊第三十頁(yè)，共197頁(yè)。

流網(wǎng)絡(luò)G 殘留網(wǎng)絡(luò)G*12345432615401343st12345431633112st當(dāng)flow(v,w)>0時(shí)，(w,v)是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)；當(dāng)flow(v,w)<cap(v,w)時(shí)，(v,w)是G*中的一條邊，該邊的容量為cap*(v,w)=cap(v,w)-flow(v,w)。第三十一頁(yè)，共197頁(yè)。按照殘留網(wǎng)絡(luò)的定義，當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條零流邊時(shí)，殘留網(wǎng)絡(luò)G*中有唯一的一條邊(v,w)與之對(duì)應(yīng)，且該邊的容量為cap(v,w)；當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條飽和邊時(shí)，殘留網(wǎng)絡(luò)G*中有唯一的一條邊(w,v)與之對(duì)應(yīng)，且該邊的容量為cap(v,w)；當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條弱流邊時(shí)，殘留網(wǎng)絡(luò)G*中有兩條邊(v,w)和(w,v)與之對(duì)應(yīng)，這兩條邊的容量分別為cap(v,w)-flow(v,w)和flow(v,w)。都是可以使用的，一種是可以直接被利用的，一種是可以調(diào)到其它邊上的。相同點(diǎn)：都可以（需要）減少。第三十二頁(yè)，共197頁(yè)。增廣路徑有向路P6（V1，V3，V2，V4，V6）正向邊（V1，V3）、（V2，V4）、（V4，V6）；反向邊（V3，V2）的運(yùn)輸量為1；增廣路徑在殘留網(wǎng)絡(luò)Gf中從s到t的一條簡(jiǎn)單路徑稱為增廣路徑；若邊(u,v)的方向與該路徑的方向一致，稱(u,v)為正向邊（正向?。蜻叺娜w記為P+；若邊(u,v)的方向與該路徑的方向相反，稱為逆向邊（反向?。?，逆向邊的全體記為P-。

思考：增廣路徑的實(shí)際意義？第三十三頁(yè)，共197頁(yè)。如果將反向邊（V3，V2）的運(yùn)量調(diào)到正向邊（V2，V4）上去完成，這樣有向路P6（V1，V3，V2，V4，V6）的運(yùn)量可增加1。增廣路徑上所有的邊滿足：對(duì)所有正向邊有：f(u,v)<c(u,v)即P+中的每一條邊都是非飽和邊；對(duì)所有逆向邊有：f(u,v)>0即P-中的每一條邊都是非零流邊。

逆向邊流量大于0，意味著逆向邊上有流量；正向邊流量小于容量，意味著逆向邊的流量可以調(diào)過(guò)來(lái)。第三十四頁(yè)，共197頁(yè)。增廣路徑將增廣路徑中最大容量為p的殘留網(wǎng)絡(luò)定義為：cf(p)=min{cf(u,v)|(u,v)在增廣路徑上}簡(jiǎn)單路徑：13245中，(1,3)、(2,4)、(4,5)是正向邊，(3,2)是逆向邊。12345432654st第三十五頁(yè)，共197頁(yè)。增廣路徑兩條路徑：1235、1245兩條增廣路徑：135、1324512345432625242222st第三十六頁(yè)，共197頁(yè)。割（CUT）流網(wǎng)絡(luò)中頂點(diǎn)的一個(gè)劃分；它把流網(wǎng)絡(luò)G(V,E)中的所有頂點(diǎn)劃分成兩個(gè)頂點(diǎn)集合S和T（T=V-S），其中源點(diǎn)s∈S，匯點(diǎn)t∈T，記為CUT(S,T)；如果一條邊（弧）的兩個(gè)頂點(diǎn)分別屬于頂點(diǎn)集S和T（即一個(gè)頂點(diǎn)在S中，另一個(gè)頂點(diǎn)在T中），那么這條邊稱為割CUT(S,T)的一條割邊；從S指向T的割邊是正向割邊；從T指向S的割邊是逆向割邊。割CUT(S,T)中所有正向割邊的容量之和為割CUT(S,T)的容量；注意：不同割的容量不同。割是一個(gè)割邊的集合第三十七頁(yè)，共197頁(yè)。s12345432625443113t頂點(diǎn)集合S={1，2，3}和T={4，5}構(gòu)成一個(gè)割；割的容量為：3+4=7。12345432625443113st源點(diǎn)：s=1；匯點(diǎn)：t=5框外是容量，框內(nèi)是流量第三十八頁(yè)，共197頁(yè)。12345432625443113st頂點(diǎn)集合S={1，3}和T={2，4，5}構(gòu)成一個(gè)割；正向割邊：12；35逆向割邊：23割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：1容量只考慮正向邊，流量要考慮兩個(gè)方向。第三十九頁(yè)，共197頁(yè)。12345432625443113st頂點(diǎn)集合S={1，3，5}和T={2，4}能否構(gòu)成一個(gè)割？第四十頁(yè)，共197頁(yè)。12345432625443113st頂點(diǎn)集合S={1，3，4}和T={2，5}能否構(gòu)成一個(gè)割？同構(gòu)變形12345432625443113st4第四十一頁(yè)，共197頁(yè)。最大流問(wèn)題『最大流定理』可行流f為最大流，當(dāng)且僅當(dāng)不存在關(guān)于f的增廣路徑。證明：若f是最大流，但圖中存在關(guān)于f的增廣路徑，則可以沿該增廣路徑增廣，得到的是一個(gè)更大的流，與f是最大流矛盾。所以，最大流不存在增廣路徑?！涸鰪V路定理』當(dāng)且僅當(dāng)由當(dāng)前的流f壓得的殘留網(wǎng)絡(luò)中不存在增廣路徑時(shí)，流f的流量|f|達(dá)到最大。第四十二頁(yè)，共197頁(yè)。最大流問(wèn)題『Ford-Fulkerson方法』根據(jù)增廣路定理，可以設(shè)計(jì)出最基本的求最大流的方法——Ford-Fulkerson方法；開(kāi)始將流網(wǎng)絡(luò)G=(V,E)中的流f置為零流，即對(duì)于(u,v)∈E時(shí)，f(u,v)=0；然后構(gòu)建殘留網(wǎng)絡(luò)，尋找增廣路徑增廣，再修改殘留網(wǎng)絡(luò)，重復(fù)此過(guò)程，直到無(wú)法找到增廣路徑。具體步驟如下：（1）如果存在增廣路徑，就找出一條增廣路徑；（2）然后沿該條增廣路徑進(jìn)行更新流量（增加流量）。其實(shí)就是不停往流網(wǎng)絡(luò)中加流量，直到加不進(jìn)去為止第四十三頁(yè)，共197頁(yè)。最大流問(wèn)題12345432654開(kāi)始流量為：sum=012345432654一條增廣路徑:1235d=min{4,2,4}=2增加流量：2sum=2stst第四十四頁(yè)，共197頁(yè)。最大流問(wèn)題一條增廣路徑:1245d=min{4-2,3,5}=2增加流量：2sum=2+2=412345432625242st12345432625242st222第四十五頁(yè)，共197頁(yè)。最大流問(wèn)題12345432625242-1=1st22212345432625242st222111一條增廣路徑:13245d=min{6,2,3-2,5-2}=1增加流量：1sum=4+1=523減少1，加到2423減的1由13補(bǔ)充1第四十六頁(yè)，共197頁(yè)。最大流問(wèn)題12345432625242-1=1st222111一條增廣路徑:135d=min{6-1,4-2}=2增加流量：2sum=5+2=712345432625242-1=1st22211122還能再增加嗎？為什么？第四十七頁(yè)，共197頁(yè)。最大流問(wèn)題基于DFS的Ford-Fulkerson方法找一條增廣路徑：1、先設(shè)d為為正無(wú)窮（d為可增加流）

若（u,v）是正向邊：d=min(d,c(u,v)-f(u,v))若（u,v）是逆向邊：d=min(d,f(u,v))2、對(duì)與該增廣路徑上的邊

若（u,v）是正向邊，f(u,v)=f(u,v)+d；若（u,v）是逆向邊，f(u,v)=f(u,v)-d；增廣后，總流量增加了d。第四十八頁(yè)，共197頁(yè)。最大流問(wèn)題基于BFS的Edmonds-Karp（EK）算法找一條增廣路徑：EK算法是基于Ford-Fulkerson方法，唯一的區(qū)別是用BFS（寬度優(yōu)先搜索）來(lái)實(shí)現(xiàn)對(duì)增廣路徑p的計(jì)算；對(duì)于EK算法，每次用一遍BFS尋找從源點(diǎn)s到匯點(diǎn)t的最短路作為增廣路徑，然后增廣流量f并修改殘量網(wǎng)絡(luò)，直到不存在新的增廣路徑；EK算法的理論時(shí)間復(fù)雜度為：O(nm2)，由于BFS要搜索全部小于最短距離的分支路徑之后才能找到終點(diǎn)，因此頻繁的BFS效率是比較低的；類(lèi)似用BFS實(shí)現(xiàn)的還有Dinic算法。第四十九頁(yè)，共197頁(yè)?；赟AP算法（最短增廣路算法）找一條增廣路徑：定義距離標(biāo)號(hào)為到匯點(diǎn)距離的下界；在初始距離標(biāo)號(hào)的基礎(chǔ)上，不斷沿可行弧找增廣路增廣，一般采用DFS深度優(yōu)先。可行弧定義為：{(i,j)|h[i]=h[j]+1}遍歷當(dāng)前節(jié)點(diǎn)完成后，為了使下次再來(lái)的時(shí)候有路可走，重標(biāo)號(hào)當(dāng)前節(jié)點(diǎn)為：min{h[j]|(i,j)}+1

（注意要滿足距離標(biāo)號(hào)的性質(zhì)：不超過(guò)真實(shí)距離）重標(biāo)號(hào)后當(dāng)前節(jié)點(diǎn)處理完畢。當(dāng)源點(diǎn)被重標(biāo)號(hào)后，檢查其距離標(biāo)號(hào)，當(dāng)大于頂點(diǎn)數(shù)時(shí)，圖中已不存在可增廣路，此時(shí)算法結(jié)束；否則再次從源點(diǎn)遍歷；理論時(shí)間復(fù)雜度為：O(n2m)。第五十頁(yè)，共197頁(yè)。最小割問(wèn)題『流與割的關(guān)系』網(wǎng)絡(luò)流量：5割的流量：割正逆161250350450s12345432625443113t1234可以看到什么規(guī)律？第五十一頁(yè)，共197頁(yè)。最小割問(wèn)題『定理一』如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT(S,T)是任意一個(gè)割，那么f的值等于正向割邊的流量與負(fù)向割邊的流量之差?！和普撘弧蝗绻鹒是流網(wǎng)絡(luò)中的一個(gè)流，CUT(S,T)是流網(wǎng)絡(luò)中一個(gè)割，那么f的值不超過(guò)割CUT(S,T)的容量?！和普摱涣骶W(wǎng)絡(luò)中的最大流不超過(guò)任何割的容量。第五十二頁(yè)，共197頁(yè)。最小割問(wèn)題『定理二』在任何網(wǎng)絡(luò)中，如果f是一個(gè)流，CUT(S,T)是一個(gè)割，且f的值等于割CUT(S,T)的容量，那么f是一個(gè)最大流，CUT(S,T)是一個(gè)最小割（容量最小的割）?！憾ɡ砣鹤畲罅髯钚「疃ɡ恚‵ord-Fulkerson定理）』在任何的網(wǎng)絡(luò)中，最大流的值等于最小割的容量。第五十三頁(yè)，共197頁(yè)。例：plan問(wèn)題某軟件公司有n個(gè)可選的軟件項(xiàng)目，其中第i個(gè)項(xiàng)目，需要項(xiàng)目資金ai元，開(kāi)發(fā)成功后可以獲取收益為bi元；但是這些項(xiàng)目之間不是相互獨(dú)立的：開(kāi)發(fā)第i個(gè)項(xiàng)目之前必須開(kāi)發(fā)完成一些其他項(xiàng)目；這些項(xiàng)目稱為項(xiàng)目i的前驅(qū)項(xiàng)目；目標(biāo)：在給出所有項(xiàng)目的前驅(qū)項(xiàng)目及每個(gè)項(xiàng)目的ai和bi后，幫助該公司選擇若干個(gè)項(xiàng)目開(kāi)發(fā)，使獲得的收益最大。思考：考慮凈收益（收益-成本）；目標(biāo)就是總的凈收益最大；總的凈收益最大化→最大流；如何建模？第五十四頁(yè)，共197頁(yè)。思路：令di=bi-ai為凈收益A={i|di≥0}：可以獲取利潤(rùn)的項(xiàng)目集合B={i|di<0}：虧損的項(xiàng)目集合構(gòu)成網(wǎng)絡(luò)圖G=（V,E,c）1.兩類(lèi)頂點(diǎn)：N+2個(gè)頂點(diǎn)，源點(diǎn)為S，匯點(diǎn)為T(mén)，第i個(gè)項(xiàng)目為vi2.三種?。喝绻鹖∈A，存在弧(i,t)，容量為di如果i∈B，存在弧(s,i)，容量為|di|如果i的前驅(qū)項(xiàng)目為j，存在弧(j,i)容量為+∞第五十五頁(yè)，共197頁(yè)。構(gòu)造割cut(S,T)，如果i∈T，則i的前驅(qū)j∈T每個(gè)割對(duì)應(yīng)一種方案；目標(biāo)：求最大流f（即最小割）最大收益為：一種是做了B中任務(wù)就虧損；一種是沒(méi)有做A中任務(wù)的期望虧損；收入虧損跟t相連的結(jié)點(diǎn)是需要完成的項(xiàng)目第五十六頁(yè)，共197頁(yè)。S-T割：割中沒(méi)有正向容量為∞的弧因?yàn)楦鶷相連的結(jié)點(diǎn)是需要完成的項(xiàng)目，如果有正向邊，意味著它的前驅(qū)項(xiàng)目在S集合中；S集合中的項(xiàng)目是不進(jìn)行的，則計(jì)劃不可行，而反向邊是無(wú)所謂的。說(shuō)明：和S連接的項(xiàng)目，做了就是虧損→做就是讓這些結(jié)點(diǎn)跟S斷開(kāi)；和T連接的項(xiàng)目，不做就是虧損→不做就是讓這些結(jié)點(diǎn)跟T斷開(kāi)；第五十七頁(yè)，共197頁(yè)。最小費(fèi)用最大流最小費(fèi)用流問(wèn)題最大流向問(wèn)題僅涉及流的值，沒(méi)有涉及費(fèi)用；實(shí)際生活中，不僅要求流量最大，而且還要費(fèi)用最??；1.交通運(yùn)輸往往要求在完成運(yùn)輸任務(wù)的前提下，要找出費(fèi)用最少的方案；2.在網(wǎng)絡(luò)中，信息從源傳送到目標(biāo)時(shí)，也可尋找最小費(fèi)用方案，即滿足流量要求，又實(shí)現(xiàn)費(fèi)用最節(jié)省以實(shí)現(xiàn)最佳的分配。求最小費(fèi)用流就是在流量最大的前提下，求出費(fèi)用最小的那一個(gè)最大流。第五十八頁(yè)，共197頁(yè)?；纠碚摼W(wǎng)流G的邊不僅有容量限制，還要考慮單位流量的費(fèi)用；目標(biāo)：求其最大流的同時(shí)，使其費(fèi)用最低，也稱最佳流，是最大流問(wèn)題的推廣；描述：在網(wǎng)絡(luò)抽象圖G(V,E,C,f,w)中，w(e)為邊e上單位流量的費(fèi)用，f(e)為邊e上分配的流量；則在給定的可行流fst的條件下，通過(guò)流量的分配使費(fèi)用最??；即minw(f)=min{∑w(e)f(e)}第五十九頁(yè)，共197頁(yè)。最小費(fèi)用增廣路算法殘量網(wǎng)絡(luò)中費(fèi)用的定義：對(duì)于原圖中的邊w(u,v)，殘量網(wǎng)絡(luò)中w’(u,v)=w(u,v),w’(v,u)=-w(u,v)在殘量網(wǎng)絡(luò)中求最小費(fèi)用路，即以w’為權(quán)值的從s到t的最短路（利用Bellman-Ford）；沿最小費(fèi)用路增廣，直到不能找到s-t路為止。最后得到的就是最小費(fèi)用流。第六十頁(yè)，共197頁(yè)。消圈算法殘留網(wǎng)絡(luò)中費(fèi)用的定義：對(duì)于原圖中的邊w(u,v)；殘留網(wǎng)絡(luò)中w’(u,v)=w(u,v)，w’(v,u)=-w(u,v)先在網(wǎng)絡(luò)中求出一個(gè)最大流，然后再在網(wǎng)絡(luò)中尋找可增流的負(fù)圈，找到了就增流，就可以使最大流的費(fèi)用減少。當(dāng)殘留網(wǎng)絡(luò)中不存在負(fù)費(fèi)用圈的時(shí)候，這個(gè)最大流就是最小費(fèi)用最大流。第六十一頁(yè)，共197頁(yè)。例題分析GoingHome(Poj2195)地圖N*M（可用N*M矩陣表示）在地圖上有K個(gè)人、K間房子，每個(gè)人每步只能走到相鄰的格子中，每走一步的花費(fèi)是1；那要這K個(gè)人分別走到地圖上的K個(gè)房間里的總花費(fèi)是多少？說(shuō)明：每一個(gè)房間可以容納一個(gè)人；一個(gè)人也可以站在房間所在的格子中而不進(jìn)入到房間里去。第六十二頁(yè)，共197頁(yè)。例題分析由K個(gè)人走到K個(gè)房間，可以考慮為可行流問(wèn)題，這題每個(gè)源點(diǎn)或是匯點(diǎn)的流量都為1，而且題目要求的是最小的花費(fèi)；地圖上每?jī)蓚€(gè)相鄰的點(diǎn)上連接上兩條邊，容量為K花費(fèi)為1；把人作為一個(gè)頂點(diǎn)集合U，房間作為另一個(gè)頂點(diǎn)集合V，把U中所有點(diǎn)到V中所有點(diǎn)連線，構(gòu)成一個(gè)多源多匯的二分圖。HHMM第六十三頁(yè)，共197頁(yè)。構(gòu)造一個(gè)超級(jí)源s和超級(jí)匯t：超級(jí)源s與U中所有點(diǎn)相連，費(fèi)用為0（這是顯然的），容量為1；V中所有點(diǎn)與超級(jí)匯t相連，費(fèi)用為0（這是顯然的），容量為1；至于其它不連通的點(diǎn)，費(fèi)用與容量均為0。容量為0的邊，可以理解為飽和邊，不再連通；而上述的所有邊之所以容量初始化為1，是因?yàn)槊块g房間只允許入住1個(gè)人；而與超級(jí)源（匯）相連的邊的費(fèi)用之所以為0，是為了現(xiàn)在所構(gòu)造的單源單匯網(wǎng)絡(luò)流最終所求的最小費(fèi)用等于原來(lái)的多源多匯網(wǎng)絡(luò)流的最小費(fèi)用。第六十四頁(yè)，共197頁(yè)。HHMMst第六十五頁(yè)，共197頁(yè)。對(duì)偶圖在最大流中的應(yīng)用狼抓兔子現(xiàn)在小朋友們最喜歡的“喜羊羊與灰太狼”，話說(shuō)灰太狼抓羊不到，但抓兔子還是比較在行的，而且現(xiàn)在的兔子還比較笨，它們只有兩個(gè)窩，現(xiàn)在你做為狼王，面對(duì)下面這樣一個(gè)網(wǎng)格的地形：兔子們要從左上角(1,1)的窩跑到右下角(N,M)的窩，狼王開(kāi)始伏擊這些兔子，為了保險(xiǎn)起見(jiàn)，如果一條道路上最多通過(guò)的兔子數(shù)為K，狼王需要安排同樣數(shù)量的K只狼，才能完全封鎖這條道路；問(wèn)題：設(shè)計(jì)一個(gè)伏擊方案，使得在將兔子一網(wǎng)打盡的前提下，參與的狼的數(shù)量要最小。左上角(1,1)和右下角(N,M)為兔子的兩個(gè)窩（圖中N=3,M=4)。有三種類(lèi)型道路：1:(x,y)<==>(x+1,y)2:(x,y)<==>(x,y+1)3:(x,y)<==>(x+1,y+1)道路上的權(quán)值表示這條路上最多能夠通過(guò)的兔子數(shù)，道路是無(wú)向的；

第六十六頁(yè)，共197頁(yè)。思路：第一眼看到這題，顯然是找最小割：根據(jù)最大流最小割定理，找最大流，也就是最小割；但問(wèn)題是：找最小割的復(fù)雜度是O(n2?m)；但是觀察到地形圖是一個(gè)平面圖，平面圖有很多好的性質(zhì)：對(duì)偶圖。第六十七頁(yè)，共197頁(yè)。如果網(wǎng)絡(luò)流中的圖G可以轉(zhuǎn)化為一個(gè)平面圖，那么其對(duì)偶圖G‘中的環(huán)對(duì)應(yīng)G中的割，利用最大流最小割定理轉(zhuǎn)化模型，根據(jù)平面圖G’與其對(duì)偶圖的關(guān)系，先求出最小割；首先連接s和t，如下圖藍(lán)色虛線，得到一個(gè)附加面，設(shè)附加面對(duì)應(yīng)的點(diǎn)為s‘，無(wú)界面對(duì)應(yīng)的點(diǎn)為t’，求該圖的紅色的對(duì)偶圖G‘，最后刪去s’和t‘之間的邊。一條從s'到t'的路徑，就對(duì)應(yīng)了一個(gè)s-t割，更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度。這樣時(shí)間復(fù)雜度大大降低了。使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)

spfa還能更快一些。第六十八頁(yè)，共197頁(yè)。利用最短路求最小割對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：連接s和t，得到一個(gè)附加面對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：求該圖的對(duì)偶圖G*，令附加面對(duì)應(yīng)的點(diǎn)為s*，外部面對(duì)應(yīng)的點(diǎn)為t*對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：刪去s*和t*之間的邊123456781*3*2*4*5*7*6*8*sts*t*第六十九頁(yè)，共197頁(yè)。利用最短路求最小割一條從s*到t*的路徑，就對(duì)應(yīng)了一個(gè)s-t割！更進(jìn)一步，如果令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！123456781*3*2*4*5*7*6*8*sts*t*時(shí)間復(fù)雜度：使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)；找最小割的復(fù)雜度是O(n2?m)。第七十頁(yè)，共197頁(yè)。利用最短路求最小割一條從s*到t*的路徑，就對(duì)應(yīng)了一個(gè)s-t割！更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！分析一下時(shí)間復(fù)雜度新圖中的點(diǎn)數(shù)和邊數(shù)都是O(n)的使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*第七十一頁(yè)，共197頁(yè)?？梢园旬?huà)的線看作一條連通這條邊兩側(cè)方塊（如果在網(wǎng)格圖中）的邊，而且你會(huì)發(fā)現(xiàn)，要使起點(diǎn)和終點(diǎn)不連通，我們就會(huì)畫(huà)出一串可以相連的線；所以解法應(yīng)該就是在平面圖上求最小割，即就是在這一串的割線上找最短路。構(gòu)建一個(gè)對(duì)偶圖：對(duì)于每一條邊，必定會(huì)有兩個(gè)面在其左右側(cè)。將左右側(cè)兩個(gè)面連一條邊，且其權(quán)值為原來(lái)那條邊的權(quán)值。即對(duì)于圖中的一條權(quán)值為5的邊，在對(duì)偶圖中對(duì)應(yīng)的就是一條由1連向2的權(quán)值為5的邊。第七十二頁(yè)，共197頁(yè)。這個(gè)時(shí)候就有個(gè)問(wèn)題了：旁邊的邊怎么辦？解決方法：可以將左下方部分設(shè)為一個(gè)超級(jí)源點(diǎn)，右上方部分設(shè)為一個(gè)超級(jí)匯點(diǎn)；這樣，對(duì)偶圖就很好理解了：從超級(jí)源點(diǎn)到超級(jí)匯點(diǎn)找最短路就行了。第七十三頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼傳統(tǒng)的通信網(wǎng)絡(luò)傳送數(shù)據(jù)的方式是存儲(chǔ)轉(zhuǎn)發(fā)，即除了數(shù)據(jù)的發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)以外的節(jié)點(diǎn)只負(fù)責(zé)路由，而不對(duì)數(shù)據(jù)內(nèi)容做任何處理；中間節(jié)點(diǎn)扮演著轉(zhuǎn)發(fā)器的角色；長(zhǎng)期以來(lái)，人們普遍認(rèn)為在中間節(jié)點(diǎn)上對(duì)傳輸?shù)臄?shù)據(jù)進(jìn)行加工不會(huì)產(chǎn)生任何收益。真是這樣嗎？第七十四頁(yè)，共197頁(yè)。實(shí)際上，從信息理論的觀點(diǎn)來(lái)說(shuō)，網(wǎng)絡(luò)結(jié)點(diǎn)可以不僅進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā)，還可以收到的信息進(jìn)行一定的線性或非線性操作（編碼），然后再發(fā)送出去，起著編碼器的作用；存儲(chǔ)+轉(zhuǎn)發(fā)→存儲(chǔ)+編碼+轉(zhuǎn)發(fā)網(wǎng)絡(luò)編碼正是根據(jù)這思想而產(chǎn)生的；在接收節(jié)點(diǎn)上，通過(guò)一定的運(yùn)算，譯出信源所發(fā)的信息。第七十五頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼的提出最大流最小割定理：網(wǎng)絡(luò)端對(duì)端的最大流量是由最小割決定的，并且最大流的值等于最小割的容量。2000年R.Ahlswede，Cai.N等人發(fā)表論文：NetworkInformationflows，IEEETransInfotheory提出網(wǎng)絡(luò)編碼（NetworkCoding）的概念，通過(guò)路由器對(duì)信息流進(jìn)行編碼，可以達(dá)到該上界。但是，目前傳統(tǒng)路由器的存儲(chǔ)轉(zhuǎn)發(fā)模式不可能達(dá)到上界，即不能達(dá)到最小割。第七十六頁(yè)，共197頁(yè)?；驹恚阂?信源2信宿、蝴蝶網(wǎng)絡(luò)為例，每條鏈路容量為1；由最大流最小割定理，該多播（multicast）的最大的理論傳輸流量為2；即理論上Y和Z應(yīng)該能同時(shí)收到S發(fā)出的2個(gè)單元的信息，即同時(shí)收到b1、b2?！径嘣炊鄥R的情況】加超級(jí)源和超級(jí)匯，超級(jí)源向每個(gè)源點(diǎn)連容量無(wú)限大的邊，每個(gè)匯點(diǎn)向超級(jí)匯連容量為無(wú)限大的邊。最小割第七十七頁(yè)，共197頁(yè)。傳統(tǒng)的轉(zhuǎn)發(fā)方式：鏈路WX、XY和XZ上傳輸?shù)男畔⒕鶠閎1；雖然z收到b1、b2，但Y只能收到b1；因此不能實(shí)現(xiàn)最大傳輸。原因：W結(jié)點(diǎn)只有1個(gè)出口，只能轉(zhuǎn)發(fā)b1或者b2第七十八頁(yè)，共197頁(yè)。采用網(wǎng)絡(luò)編碼的轉(zhuǎn)發(fā)方式：W對(duì)b1、b2進(jìn)行編碼，發(fā)出編碼b1+b2包給X；X把b1+b2轉(zhuǎn)發(fā)給Y和Z；然后Y、Z可解碼出原始的數(shù)據(jù)包b1、b2。編碼運(yùn)算“+”是抽象意義的運(yùn)算，實(shí)際中可以選擇多種運(yùn)算第七十九頁(yè)，共197頁(yè)。第八十頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼的提出網(wǎng)絡(luò)編碼帶來(lái)的好處：使組播傳輸速率達(dá)到網(wǎng)絡(luò)容量的上限；最小割最大流決定；節(jié)省網(wǎng)絡(luò)帶寬、資源消耗；節(jié)省無(wú)線網(wǎng)絡(luò)結(jié)點(diǎn)電量消耗傳輸次數(shù)減少：無(wú)線信號(hào)傳輸比編碼計(jì)算更加耗電均衡網(wǎng)絡(luò)負(fù)載；提高網(wǎng)絡(luò)魯棒性。缺點(diǎn)：消耗計(jì)算資源；中間結(jié)點(diǎn)可以對(duì)數(shù)據(jù)進(jìn)行處理，因此可能有安全問(wèn)題。有沒(méi)有缺點(diǎn)呢？第八十一頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼的發(fā)展過(guò)程2000年，Ahlswede等提出了網(wǎng)絡(luò)編碼的概念；2002年，Koetter等給出了網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造算法，是指數(shù)時(shí)間算法（集中式）；2002年，Cai等提出了基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)糾錯(cuò)碼概念；2002年，Cai等提出了采用網(wǎng)絡(luò)編碼時(shí)的信息完安全性問(wèn)題；2003年，Sander等給出了網(wǎng)絡(luò)編碼的多項(xiàng)式時(shí)間算法（集中式）；2003年，Chou等提出了分布式網(wǎng)絡(luò)編碼，通過(guò)仿真得到其性能；2003年，Ho等也提出了隨機(jī)網(wǎng)絡(luò)編碼（分布式）；2004年，Wu等將網(wǎng)絡(luò)編碼應(yīng)用于無(wú)線網(wǎng)絡(luò)以節(jié)省能量。第八十二頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼的數(shù)學(xué)描述信息傳輸網(wǎng)絡(luò)可用圖表示信源節(jié)點(diǎn)集：信宿節(jié)點(diǎn)集：邊的頭節(jié)點(diǎn)用表示邊的尾節(jié)點(diǎn)用表示假設(shè)每條邊容量為1比特/單位時(shí)間（可通過(guò)合適選取單位時(shí)間大小和將鏈路進(jìn)行拆分實(shí)現(xiàn)）第八十三頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼的數(shù)學(xué)描述網(wǎng)絡(luò)編碼的數(shù)學(xué)描述(適用于組播和非組播傳輸）對(duì)邊集E中的每條邊，存在一種映射：

這是對(duì)應(yīng)于每條邊的編碼函數(shù)；目的節(jié)點(diǎn)為了得到所需信息，存在映射：是對(duì)應(yīng)于目的節(jié)點(diǎn)

的第

個(gè)信源符號(hào)的譯碼函數(shù)。第八十四頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼基本方法異或編碼、線性編碼對(duì)于多播，線性編碼得到性能上界（maximumcapacitybounds），編碼和解碼能在多項(xiàng)式時(shí)間內(nèi)完成；Ho等人證明上述結(jié)論對(duì)于線性編碼在隨機(jī)系數(shù)的情況下也成立；第八十五頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼應(yīng)用網(wǎng)絡(luò)傳輸（有線、無(wú)線）內(nèi)容分發(fā)安全分布式存儲(chǔ)傳輸差錯(cuò)控制第八十六頁(yè)，共197頁(yè)。無(wú)線組播中的網(wǎng)絡(luò)編碼可以實(shí)現(xiàn)以網(wǎng)絡(luò)的最大流傳輸信息；這是網(wǎng)絡(luò)中容量的理論上限；可以降低無(wú)線網(wǎng)絡(luò)中的能量消耗；這對(duì)以電池為能源供給的無(wú)線網(wǎng)絡(luò)來(lái)說(shuō)，是至關(guān)重要的；系統(tǒng)轉(zhuǎn)移矩陣中的變量個(gè)數(shù)由指數(shù)級(jí)降為多項(xiàng)式級(jí)；從而大大降低了實(shí)現(xiàn)網(wǎng)絡(luò)編碼算法的復(fù)雜度；在降低網(wǎng)絡(luò)編碼實(shí)現(xiàn)算法復(fù)雜度的同時(shí)，并沒(méi)有增加網(wǎng)絡(luò)編碼字母表的大小。傳統(tǒng)方法基于網(wǎng)絡(luò)編碼的方法第八十七頁(yè)，共197頁(yè)。網(wǎng)絡(luò)編碼在無(wú)線多跳網(wǎng)絡(luò)中的應(yīng)用S.Katti,H.Rahul,W.Hu,D.Katabi,M.Medard,J.Crowcroft,“XORsintheAir:PracticalWirelessNetworkCoding,”

ACMSIGCOMMConference,(September2006).無(wú)線網(wǎng)絡(luò)特性：wifi、zigbee等1廣播；（不考慮定向天線）2不穩(wěn)定、丟包率高；3同信道干擾。第八十八頁(yè)，共197頁(yè)。無(wú)線多跳網(wǎng)絡(luò)（Wirelessmultihopnetworks）Ad-Hoc、WMN、WSN、MANETWirelessmeshnetworks（WMN）傳統(tǒng)的無(wú)線網(wǎng)絡(luò)的節(jié)點(diǎn)通過(guò)接入點(diǎn)（AP）才能進(jìn)行通信，即使兩個(gè)節(jié)點(diǎn)距離很近；（星型拓?fù)洌o(wú)線Mesh網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都可以與一個(gè)或者多個(gè)對(duì)等節(jié)點(diǎn)進(jìn)行直接通信；（網(wǎng)狀拓?fù)洌┨峁┍阋?、廣泛的互聯(lián)網(wǎng)接入；但是目前的連接質(zhì)量比較低；Roofnet中一半的operational鏈接的丟包率超過(guò)30%.第八十九頁(yè)，共197頁(yè)。WirelessSensorNetwork（WSN）由大量的靜止或移動(dòng)的傳感器以自組織和多跳的方式構(gòu)成的無(wú)線網(wǎng)絡(luò)，以協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對(duì)象的信息，并最終把這些信息發(fā)送給網(wǎng)絡(luò)所有者的；傳感器可探測(cè)包括地震、電磁、溫度、濕度、噪聲、光強(qiáng)度、壓力、土壤成分、移動(dòng)物體的大小、速度和方向等參數(shù)；應(yīng)用領(lǐng)域軍事、航空、防爆、救災(zāi)、環(huán)境、醫(yī)療、保健、家居、工業(yè)、商業(yè)等。第九十頁(yè)，共197頁(yè)。COPE協(xié)議Inter-flownetworkcoding（流間編碼）ConsidermultipleunicastflowsGeneralizeAlice-BobscenarioExploitsSharedNatureofWirelessMediumStoreOverheardPacketsforShortTimeThesepacketsareusedfordecodingperspectivepacketsOpportunisticCodingOverhearneighbors’transmissionsStorethesepacketsinabufferPacketPoolforashorttimeReportthepacketpoolinfo.toneighborsDeterminewhatpacketstocodebasedontheinfo.Sendencodedpackets第九十一頁(yè)，共197頁(yè)。COPE特點(diǎn)第一個(gè)將networkcoding用于無(wú)線網(wǎng)絡(luò)大大增加網(wǎng)絡(luò)性能（吞吐量）實(shí)現(xiàn)簡(jiǎn)單COPE適用范圍全向天線（Omni-directionalantenna）對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)性能要求：內(nèi)存、CPU、電源要求overhear成功率高（干擾、鏈路沖突）要求鏈路質(zhì)量高：出錯(cuò)后重傳代價(jià)大延遲可能會(huì)增加：要等另一個(gè)流的數(shù)據(jù)包雙方數(shù)據(jù)包大小不同的話，對(duì)性能有影響第九十二頁(yè)，共197頁(yè)。Allassumingperfectoverhearing第九十三頁(yè)，共197頁(yè)。左圖中的問(wèn)題是無(wú)線網(wǎng)線沖突、干擾，如果B、D不能overhear到a(或b)，則不能解碼，重傳則更浪費(fèi)；右圖的例子不用考慮overhear丟包的問(wèn)題，但是這種情況較少，如果只考慮這種情況，則減少了編碼機(jī)會(huì)。傳統(tǒng)：4次轉(zhuǎn)發(fā)，NC：3次轉(zhuǎn)發(fā)Codinggain:theratioofthenumberoftransmissionsrequiredbythecurrentnon-codingapproach,totheminimumnumberoftransmissionsusedbyCOPEtodeliverthesamesetofpackets.第九十四頁(yè)，共197頁(yè)。MORE協(xié)議TradingStructureforRandomnessinWirelessOpportunisticRouting,SzymonChachulskiMichaelJenningsSachinKattiDinaKatabi,MITCSAIL,SIGCOMM’07傳統(tǒng)路由在發(fā)送數(shù)據(jù)包之前選擇下一跳節(jié)點(diǎn)（不管是先驗(yàn)式還是反應(yīng)式）；當(dāng)鏈接質(zhì)量低的時(shí)候，下一跳節(jié)點(diǎn)接收到數(shù)據(jù)包的概率比較低（意味著要發(fā)送多次）；機(jī)會(huì)路由（Opportunisticrouting）允許距離目的節(jié)點(diǎn)比較近的、接收到數(shù)據(jù)的任何節(jié)點(diǎn)（無(wú)線通信中數(shù)據(jù)是廣播方式發(fā)出的）參與數(shù)據(jù)包的轉(zhuǎn)發(fā)；在鏈接丟包比較嚴(yán)重的情況下，提供比傳統(tǒng)路由更高的吞吐量。第九十五頁(yè)，共197頁(yè)。EXOR：S.Biswas,R.Morris,“ExOR:OpportunisticMulti-HopRoutingforWirelessNetworks,”

ACMSIGCOMMConference,(August2005).Biswas和Morris證明了：這種更加彈性的下一跳節(jié)點(diǎn)的選擇方法可以較大地提高吞吐量；問(wèn)題：需要節(jié)點(diǎn)間協(xié)同；多個(gè)節(jié)點(diǎn)可能接收并且轉(zhuǎn)發(fā)同樣的數(shù)據(jù)包，造成資源浪費(fèi)；第九十六頁(yè)，共197頁(yè)。N1N3N5N7N6N2N4N8SDTraditionalPathTraditionalroutingmustcompromisebetweenhopstochooseonesthatarelongenoughtomakegoodprogressbutshortenoughforlowlossrateWithExOReachtransmissionmayhavemoreindependentchancesofbeingreceivedandforwardedIttakesadvantageoftransmissionsthatreachunexpectedlyfar,orfallunexpectedlyshort第九十七頁(yè)，共197頁(yè)。Traditionalrouting:1/0.25+1=5transmissionsExOR:1/(1–(1–0.25)4)+1=2.5transmissionsAssumesindependentlossesN1srcdstN2N3N425%25%25%25%100%100%100%100%第九十八頁(yè)，共197頁(yè)。MORE簡(jiǎn)介MAC-independentOpportunisticRouting&Encoding；MORE在發(fā)送數(shù)據(jù)包之前將它們r(jià)andomly

mixes，這保證了同時(shí)接收到相同數(shù)據(jù)的節(jié)點(diǎn)不會(huì)轉(zhuǎn)發(fā)相同的數(shù)據(jù)包；數(shù)據(jù)包隨機(jī)編碼（randomlycodedpackets）后發(fā)生重復(fù)的概率已經(jīng)被證明exponentiallylow；效果：MORE不需要特別設(shè)定的調(diào)度機(jī)制，它直接運(yùn)行在802.11之上。思考：為什么要隨機(jī)編碼？第九十九頁(yè)，共197頁(yè)。隨機(jī)編碼在實(shí)際網(wǎng)絡(luò)中無(wú)控制中心，因此需要實(shí)現(xiàn)分布式網(wǎng)絡(luò)編碼：各個(gè)節(jié)點(diǎn)不需要中心分配編碼系數(shù)，而是在某個(gè)范圍內(nèi)隨機(jī)選擇一組元素作為編碼系數(shù)，隨機(jī)系數(shù)的線性相關(guān)概率比較低；隨機(jī)編碼系數(shù)的選擇范圍越大，隨機(jī)網(wǎng)絡(luò)編碼有效的概率就越高；為了方便處理，隨機(jī)編碼系數(shù)一般取自于Galois（伽羅瓦）域；域：對(duì)乘法運(yùn)算可換、有單位元、除零元外有逆元的環(huán)，如(R,+,x)；一個(gè)域的元素有限就是有限域，這種域又稱為伽羅瓦(Galois)域；定理：F為有限域，則存在素?cái)?shù)p，自然數(shù)m≥1，使|F|=pm；定義：一個(gè)具有pm個(gè)元素的有限域稱為pm階伽羅瓦域，記為GF(pm)，其中p為素?cái)?shù)，m1為自然數(shù)；網(wǎng)絡(luò)編碼中，隨機(jī)系數(shù)取值范圍GF(28)，則線性相關(guān)概率1/28。第一百頁(yè)，共197頁(yè)。MORE設(shè)計(jì)思想MORE的設(shè)計(jì)是基于網(wǎng)絡(luò)編碼理論（theoryofnetworkcoding）；通過(guò)兩個(gè)例子來(lái)說(shuō)明機(jī)會(huì)路由和網(wǎng)絡(luò)編碼之間的協(xié)同工作原理；TheUnicastCase；TheMulticastCaseP1orP2？第一百零一頁(yè)，共197頁(yè)。如圖1，傳統(tǒng)路由在傳輸數(shù)據(jù)之前先要確定傳輸路徑：src→R→dest，

因?yàn)樗凶罡叩霓D(zhuǎn)發(fā)概率；（最短路徑）由于無(wú)線通信是廣播方式，因此當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，一個(gè)距離目的節(jié)點(diǎn)比下一跳節(jié)點(diǎn)更近的節(jié)點(diǎn)也有可能接收到數(shù)據(jù)包；例如：假設(shè)源節(jié)點(diǎn)發(fā)出2個(gè)數(shù)據(jù)包p1、p2，下一跳節(jié)點(diǎn)R都接收到了，而目的節(jié)點(diǎn)也接收到了p1，這時(shí)如果R仍然轉(zhuǎn)發(fā)p1則是浪費(fèi)資源。這個(gè)就是設(shè)計(jì)ExOR的原因；第一百零二頁(yè)，共197頁(yè)。存在問(wèn)題ExOR需要節(jié)點(diǎn)之間的協(xié)同，這個(gè)在大型網(wǎng)絡(luò)中是很難做到的；轉(zhuǎn)發(fā)節(jié)點(diǎn)R只需要轉(zhuǎn)發(fā)p2，因?yàn)閜1已經(jīng)被目的節(jié)點(diǎn)接收到，但是在沒(méi)有和目的節(jié)點(diǎn)協(xié)商之前，R不知道他應(yīng)該轉(zhuǎn)發(fā)哪個(gè)數(shù)據(jù)包，這個(gè)問(wèn)題在大型網(wǎng)絡(luò)中是很難解決的；機(jī)會(huì)路由允許這些節(jié)點(diǎn)參與轉(zhuǎn)發(fā)他們聽(tīng)到（接收到）的數(shù)據(jù)包，但是如果沒(méi)有協(xié)同機(jī)制，多個(gè)節(jié)點(diǎn)可能會(huì)轉(zhuǎn)發(fā)同一個(gè)數(shù)據(jù)包；ExOR沒(méi)有用到網(wǎng)絡(luò)編碼第一百零三頁(yè)，共197頁(yè)。ExOR采用運(yùn)行在802.11上的特定的調(diào)度機(jī)制來(lái)解決這個(gè)問(wèn)題：

調(diào)度程序循環(huán)運(yùn)行，在任意時(shí)間為一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)保留無(wú)線介質(zhì)（也就是說(shuō)為一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)分配一個(gè)特定的時(shí)間段來(lái)訪問(wèn)無(wú)線介質(zhì)）；

其余的節(jié)點(diǎn)監(jiān)聽(tīng)數(shù)據(jù)包，由于這個(gè)嚴(yán)格的調(diào)度機(jī)制，距離目的節(jié)點(diǎn)很遠(yuǎn)的節(jié)點(diǎn)必須等到距離目的節(jié)點(diǎn)比較近的節(jié)點(diǎn)完成數(shù)據(jù)發(fā)送后才能發(fā)送數(shù)據(jù)，而如果采用了空間復(fù)用，則它們可以同時(shí)發(fā)送數(shù)據(jù)；因此，（全局）調(diào)度程序的副作用是阻礙了利用無(wú)線通信的空間復(fù)用性質(zhì)。問(wèn)題：全局調(diào)度很難實(shí)現(xiàn)！第一百零四頁(yè)，共197頁(yè)。Idea：采用網(wǎng)絡(luò)編碼在上個(gè)例子中，目的節(jié)點(diǎn)接收到了p1，但是R不知道，可以采用網(wǎng)絡(luò)編碼，R轉(zhuǎn)發(fā)接收到的數(shù)據(jù)包的線性組合；例如：R發(fā)送p1+p2，目的節(jié)點(diǎn)收到后，從p1+p2中減去p1就可以得到p2，然后發(fā)送接收到數(shù)據(jù)的ACK消息，R不需要知道目的節(jié)點(diǎn)到底接收到了哪個(gè)數(shù)據(jù)包；實(shí)際上，R需要發(fā)送的是兩個(gè)數(shù)據(jù)包的隨機(jī)線性組和：路由節(jié)點(diǎn)創(chuàng)建一個(gè)所有它接收到的數(shù)據(jù)包的線性組合，采用隨機(jī)系數(shù)；目的節(jié)點(diǎn)當(dāng)接收到整個(gè)數(shù)據(jù)后，沿著逆向路徑發(fā)送ACK消息；優(yōu)點(diǎn)：不需要節(jié)點(diǎn)的協(xié)同，并且保留了空間復(fù)用。

思考：為什么用隨機(jī)線性組合？第一百零五頁(yè)，共197頁(yè)。TheMulticastCase第一百零六頁(yè)，共197頁(yè)。第二個(gè)例子說(shuō)明網(wǎng)絡(luò)編碼和多播之間的協(xié)作；源節(jié)點(diǎn)多播4個(gè)數(shù)據(jù)包到3個(gè)目的節(jié)點(diǎn)研究發(fā)現(xiàn)：不同節(jié)點(diǎn)的無(wú)線信號(hào)接收是高度獨(dú)立的；假設(shè)每個(gè)目的節(jié)點(diǎn)的接收情況為：thefirstdestinationreceivesp1andp2,theseconddestinationreceivesp2andp3,thelastdestinationreceivesp3andp4.其中沒(méi)有一個(gè)數(shù)據(jù)包被所有節(jié)點(diǎn)接收到；第一百零七頁(yè)，共197頁(yè)。在這種情況下，如果沒(méi)有進(jìn)行編碼，則發(fā)送者必須重新發(fā)送所有丟失的數(shù)據(jù)包；如果進(jìn)行網(wǎng)絡(luò)編碼，只需要發(fā)送兩個(gè)隨機(jī)編碼后的數(shù)據(jù)包即可：

p1’=p1+p2+p3+p4P2’=p1+2p2+3p3+4p4不管哪個(gè)目的節(jié)點(diǎn)丟失了哪個(gè)數(shù)據(jù)包，它都能通過(guò)下面的公式計(jì)算出來(lái)它沒(méi)有接收到的數(shù)據(jù)包。重發(fā)次數(shù)由4減少到2，提高了吞吐量。其實(shí)應(yīng)該也考慮后來(lái)發(fā)送的編碼數(shù)據(jù)包也有丟失的情況第一百零八頁(yè)，共197頁(yè)。Each

routerforwardsrandomcombinationsofpacketssrcR1dstR2α

P1+

?

P2γ

P1+

δ

P2RandomnesspreventsduplicatesNoscheduler;NocoordinationSimpleandexploitsspatialreuseP1P2P1P2第一百零九頁(yè)，共197頁(yè)。RandomCodingBenefitsMulticastsrcdst1dst2dst3P1P2P3P4P1P2P2P3P3P4P3P4P1P4P1P2Withoutcodingsourceretransmitsall4packets第一百一十頁(yè)，共197頁(yè)。RandomCodingBenefitsMulticastsrcdst1dst2dst3P1P2P3P4P1P2P2P3P3P48

P1+5

P2+

P3+3

P47

P1+3P2+6P3+P4P3P4P1P4P1P2Withoutcodingsourceretransmitsall4packetsWithrandomcoding2packetsaresufficientRandomcombinationsRandomcodingismoreefficientthan

globalcoordination第一百一十一頁(yè)，共197頁(yè)。難點(diǎn)每個(gè)節(jié)點(diǎn)應(yīng)該轉(zhuǎn)發(fā)多少數(shù)據(jù)包？傳統(tǒng)的最優(yōu)路徑路由中，一個(gè)節(jié)點(diǎn)向下一跳節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，或者發(fā)送成功，或者一直發(fā)送直到超過(guò)重發(fā)次數(shù)；在機(jī)會(huì)路由中，沒(méi)有確定的下一跳節(jié)點(diǎn)，所有距離目的節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)近的節(jié)點(diǎn)都可以參與轉(zhuǎn)發(fā)；現(xiàn)在的問(wèn)題是：多少次的轉(zhuǎn)發(fā)能保證至少一個(gè)節(jié)點(diǎn)接收到這個(gè)數(shù)據(jù)包？多發(fā)了浪費(fèi)資源，少發(fā)了則不夠用第一百一十二頁(yè)，共197頁(yè)。一個(gè)節(jié)點(diǎn)在什么情況下停止發(fā)送，并清空數(shù)據(jù)？通過(guò)網(wǎng)絡(luò)編碼，路由器發(fā)送線性組合后的數(shù)據(jù)包，只要目的節(jié)點(diǎn)有數(shù)量足夠的編碼后的數(shù)據(jù)包，它就能解碼得到原始數(shù)據(jù)包。當(dāng)目的節(jié)點(diǎn)接受到數(shù)據(jù)后，我們需要盡快停止發(fā)送，并清空轉(zhuǎn)發(fā)節(jié)點(diǎn)中的相關(guān)數(shù)據(jù)；節(jié)點(diǎn)如何有效編碼？網(wǎng)絡(luò)編碼優(yōu)化的目的是更好地利用無(wú)線介質(zhì)，但是編碼需要節(jié)點(diǎn)進(jìn)行加法和乘法運(yùn)算，需要優(yōu)化算法來(lái)節(jié)省CPU的計(jì)算資源。第一百一十三頁(yè)，共197頁(yè)。MORE是針對(duì)靜態(tài)無(wú)線mesh網(wǎng)絡(luò)的協(xié)議，如Roofnet和communitywirelessnetworks；這些網(wǎng)絡(luò)中的節(jié)點(diǎn)是性能比較好的PCs；基本上不太考慮計(jì)算問(wèn)題；對(duì)于無(wú)線傳感器結(jié)點(diǎn)來(lái)說(shuō)，就不是太合適；MORE位于IP層之下，802.11MAC之上，提供可靠的文件傳輸服務(wù)，特別適合于傳輸中型和大型文件（8個(gè)或更多數(shù)據(jù)包）；對(duì)于小文件或者控制數(shù)據(jù)，采用標(biāo)準(zhǔn)的最優(yōu)路徑路由。第一百一十四頁(yè)，共197頁(yè)。相關(guān)術(shù)語(yǔ)原始數(shù)據(jù)包（NativePacket）沒(méi)有編碼的數(shù)據(jù)包；編碼數(shù)據(jù)包（CodedPacket）原始數(shù)據(jù)包的隨機(jī)線性組合；編碼向量（CodeVector）將原始數(shù)據(jù)包通過(guò)線性組合得到編碼數(shù)據(jù)包時(shí)用到的參數(shù)向量；創(chuàng)新數(shù)據(jù)包（

innovativepacket）和一個(gè)節(jié)點(diǎn)以前收到的數(shù)據(jù)包線性獨(dú)立的數(shù)據(jù)包；距離目的節(jié)點(diǎn)更近根據(jù)到目的節(jié)點(diǎn)的ETX來(lái)比較；新的信息第一百一十五頁(yè)，共197頁(yè)。源節(jié)點(diǎn)源節(jié)點(diǎn)把文件分割成K個(gè)原始數(shù)據(jù)包；就是一個(gè)batch，長(zhǎng)度固定當(dāng)802.11MAC做好發(fā)送準(zhǔn)備，源節(jié)點(diǎn)在當(dāng)前batch中創(chuàng)建一個(gè)由K個(gè)原始數(shù)據(jù)包隨機(jī)線性組合的數(shù)據(jù)包，然后將其發(fā)送出去；發(fā)送節(jié)點(diǎn)在每個(gè)數(shù)據(jù)包的頭部附加一個(gè)MORE包頭，其中包含本數(shù)據(jù)包的編碼向量、batchID、源和目的IP、參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)列表；第一百一十六頁(yè)，共197頁(yè)。計(jì)算轉(zhuǎn)發(fā)列表節(jié)點(diǎn)周期性地互相Ping，然后估計(jì)每個(gè)鏈接的發(fā)送概率，通過(guò)這個(gè)概率來(lái)計(jì)算到目的節(jié)點(diǎn)的ETX：ETX（expectedtransmissioncount）是將一個(gè)數(shù)據(jù)包發(fā)送到目的節(jié)點(diǎn)的期望傳輸次數(shù)；發(fā)送節(jié)點(diǎn)的轉(zhuǎn)發(fā)列表中包括那些比自己距離目的節(jié)點(diǎn)更近（在ETX指標(biāo)下）的那些節(jié)點(diǎn)，并且根據(jù)距離排序；發(fā)送節(jié)點(diǎn)持續(xù)發(fā)送當(dāng)前batch編碼后的數(shù)據(jù)包，直到整個(gè)batch被目的節(jié)點(diǎn)確認(rèn)接收到，然后發(fā)送者處理下一個(gè)batch。收到目的節(jié)點(diǎn)對(duì)該batch的ACK第一百一十七頁(yè)，共197頁(yè)。第一百一十八頁(yè)，共197頁(yè)。轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)節(jié)點(diǎn)監(jiān)聽(tīng)所有的數(shù)據(jù)傳輸，當(dāng)一個(gè)節(jié)點(diǎn)監(jiān)聽(tīng)到一個(gè)數(shù)據(jù)包，它檢查自己是否在這個(gè)數(shù)據(jù)包的轉(zhuǎn)發(fā)列表中；也就是該節(jié)點(diǎn)是不是被允許轉(zhuǎn)發(fā)這個(gè)數(shù)據(jù)包；如果是，然后檢查這個(gè)數(shù)據(jù)包中是不是一個(gè)創(chuàng)新數(shù)據(jù)包:包含新的信息，即：和以前接收到的數(shù)據(jù)包線性獨(dú)立；可采用簡(jiǎn)單的代數(shù)方法判斷（如GaussianElimination）；節(jié)點(diǎn)保存創(chuàng)新數(shù)據(jù)包，而忽略非創(chuàng)新數(shù)據(jù)包；第一百一十九頁(yè)，共197頁(yè)。轉(zhuǎn)發(fā)節(jié)點(diǎn)如果節(jié)點(diǎn)在轉(zhuǎn)發(fā)節(jié)點(diǎn)列表中，接收到的新數(shù)據(jù)包會(huì)觸發(fā)節(jié)點(diǎn)廣播一個(gè)編碼數(shù)據(jù)包這個(gè)編碼數(shù)據(jù)包是已經(jīng)接收到的同一個(gè)batch里面的所有數(shù)據(jù)包的一個(gè)隨機(jī)線性組合；注意：編碼數(shù)據(jù)包的線性組合也同樣是原始數(shù)據(jù)包的一個(gè)線性組合；第一百二十頁(yè)，共197頁(yè)。目的節(jié)點(diǎn)對(duì)接收到的每一個(gè)數(shù)據(jù)包，目的節(jié)點(diǎn)檢查它是否是一個(gè)創(chuàng)新數(shù)據(jù)包，丟棄非創(chuàng)新數(shù)據(jù)包；這個(gè)操作和轉(zhuǎn)發(fā)節(jié)點(diǎn)類(lèi)似；一旦目的節(jié)點(diǎn)接收到K個(gè)創(chuàng)新數(shù)據(jù)包，就可以通過(guò)如下方法得到原始數(shù)據(jù)包：?jiǎn)栴}：矩陣運(yùn)算的運(yùn)算量大！第一百二十一頁(yè)，共197頁(yè)。目的節(jié)點(diǎn)解碼出整個(gè)batch，它馬上發(fā)一個(gè)ACK到源節(jié)點(diǎn)，提示源節(jié)點(diǎn)可以開(kāi)始發(fā)送下一個(gè)batch；（一次數(shù)據(jù)傳輸分成多個(gè)batch，然后按順序傳輸）ACKs消息用最優(yōu)路徑路由來(lái)發(fā)送：因?yàn)镸ORE不適合于小數(shù)據(jù)量的數(shù)據(jù)傳輸，因此采用傳統(tǒng)的最優(yōu)路徑路由；最優(yōu)路徑路由在這里能工作的原因是MORE采用標(biāo)準(zhǔn)的802.11，并且能和最短路徑路由共存；ACKs消息比在每個(gè)節(jié)點(diǎn)上的數(shù)據(jù)包優(yōu)先級(jí)高；第一百二十二頁(yè)，共197頁(yè)。實(shí)際的挑戰(zhàn)一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)多少個(gè)數(shù)據(jù)包？傳統(tǒng)的最優(yōu)路徑路由中，一個(gè)節(jié)點(diǎn)向下一跳節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，或者發(fā)送成功，或者一直發(fā)送直到超過(guò)重發(fā)次數(shù)；在機(jī)會(huì)路由中，沒(méi)有確定的下一跳節(jié)點(diǎn)所有的距離目的節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)近的節(jié)點(diǎn)都可以參與轉(zhuǎn)發(fā)，現(xiàn)在的問(wèn)題是：多少次的轉(zhuǎn)發(fā)能保證至少一個(gè)節(jié)點(diǎn)接收到這個(gè)數(shù)據(jù)包？這是一個(gè)仍未解決的問(wèn)題，以前的工作只考慮一個(gè)簡(jiǎn)單并且理論化的問(wèn)題，該問(wèn)題假設(shè)流量是平滑的，并且無(wú)線網(wǎng)絡(luò)的帶寬是無(wú)限的；但是即使在這個(gè)假設(shè)之下，上述方法也需要解決前面提到的凸優(yōu)化問(wèn)題，這個(gè)優(yōu)化問(wèn)題的約束條件隨著聽(tīng)到廣播的節(jié)點(diǎn)數(shù)的指數(shù)方式增長(zhǎng)；第一百二十三頁(yè)，共197頁(yè)。在本節(jié)中，我們提出了該問(wèn)題的一個(gè)基于啟發(fā)式方法的實(shí)際解決方案，該解決方案有如下特點(diǎn)：低復(fù)雜度；分布式；自然地和802.11集成，并保留了空間復(fù)用性質(zhì)；實(shí)用性：只需要鏈接的平均丟失率；沒(méi)有假設(shè)無(wú)限的帶寬、平滑的流量。第一百二十四頁(yè)，共197頁(yè)。(a)Approach定義節(jié)點(diǎn)i到目的節(jié)點(diǎn)d的距離（i的ETX）節(jié)點(diǎn)i沿著最優(yōu)路徑發(fā)送一個(gè)數(shù)據(jù)包到目的節(jié)點(diǎn)d的期望發(fā)送次數(shù)；把一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)s路由到目的節(jié)點(diǎn)d的啟發(fā)式方法：（類(lèi)似于ExOR）當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包，在ETX指標(biāo)下距離目的節(jié)點(diǎn)最近的接收到數(shù)據(jù)包的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包；距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包，減少了期望傳輸次數(shù)，因此提高了總體的吞吐量。第一百二十五頁(yè)，共197頁(yè)。設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為N，對(duì)于任意兩個(gè)節(jié)點(diǎn)i和j，i<j表示i比j距離目的節(jié)點(diǎn)更近，即i的ETX值比j的??；設(shè)eij表示從i到j(luò)發(fā)送一個(gè)數(shù)據(jù)包的丟失概率；（這里考慮的是雙向的丟失率相同）設(shè)zi是在所有節(jié)點(diǎn)采用上述啟發(fā)式路由的情況下，轉(zhuǎn)發(fā)節(jié)點(diǎn)i把一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)s路由到目的節(jié)點(diǎn)d的期望傳輸次數(shù)（不管之前和之后，反正就是接收到一個(gè)數(shù)據(jù)包后，把它發(fā)出去的次數(shù)）；假設(shè)不同節(jié)點(diǎn)的無(wú)線數(shù)據(jù)接收是相互獨(dú)立的；這在

一些文獻(xiàn)中已經(jīng)通過(guò)實(shí)際測(cè)量驗(yàn)證了。第一百二十六頁(yè)，共197頁(yè)。我們注意從源節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包到目的節(jié)點(diǎn)；需要計(jì)算：在把一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)s發(fā)送到目的節(jié)點(diǎn)d的過(guò)程中，轉(zhuǎn)發(fā)節(jié)點(diǎn)j必須轉(zhuǎn)發(fā)的數(shù)據(jù)包的數(shù)量；如果轉(zhuǎn)發(fā)節(jié)點(diǎn)不轉(zhuǎn)發(fā)這個(gè)數(shù)據(jù)包呢？雖然在轉(zhuǎn)發(fā)列表中，但是ETX更小的節(jié)點(diǎn)已經(jīng)轉(zhuǎn)發(fā)了（這個(gè)問(wèn)題下一頁(yè)討論）；節(jié)點(diǎn)j從ETX值更高的節(jié)點(diǎn)得到的數(shù)據(jù)包的期望數(shù)量為：（不管經(jīng)歷了多少跳，最終都是從