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

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

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

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

點(diǎn)連通度

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

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

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

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

這個是真實(shí)的實(shí)體網(wǎng)絡(luò)中的情況，如果針對通信網(wǎng)絡(luò)來說，不一定滿足這樣的條件：比如對于匯點(diǎn)來說，流入量可能大于整個網(wǎng)絡(luò)的流量（當(dāng)然多的那些是重復(fù)的，但是它們還是占用了網(wǎng)絡(luò)資源）第二十五頁，共197頁。例：一個網(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第二十六頁，共197頁。整個流網(wǎng)絡(luò)G的流量為：|f|=∑f(s,v)(v∈V)或|f|=∑f(u,t)(u∈V)

『三個重要性質(zhì)』容量約束：對所有的u,v∈V，要求f(u,v)<=c(u,v)；平衡約束（反對稱性）：對所有的u,v∈V，要求f(u,v)=-f(v,u)；流守恒性：對所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。流量平衡方程即從源出發(fā)的所有流的總和或到達(dá)匯的所有流的總和第二十七頁，共197頁。根據(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第二十八頁，共197頁。2.最大流對于一個流網(wǎng)絡(luò)G=(V,E,c)，在其可行流中，流量最大的一個流就是最大流；注意：最大流可能不止一個。一個可行流一個可行流（也是最大流）12345432625411343st12345432645431343st第二十九頁，共197頁。殘留網(wǎng)絡(luò)對于給定的一個流網(wǎng)絡(luò)G及其上的一個流flow，網(wǎng)絡(luò)G關(guān)于流flow的殘留網(wǎng)絡(luò)G*與G有相同的頂點(diǎn)集V，而網(wǎng)絡(luò)G中的每一條邊對應(yīng)于G*中的1條邊或2條邊。設(shè)(v,w)是G的一條邊：當(dāng)flow(v,w)>0時，(w,v)是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)；當(dāng)flow(v,w)<cap(v,w)時，(v,w)是G*中的一條邊，該邊的容量為cap*(v,w)=cap(v,w)-flow(v,w)。注意：兩個條件可能同時都成立，因此就對應(yīng)兩條邊。注意：反向邊注意：正向邊第三十頁，共197頁。

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

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

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

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

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

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

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

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

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

的第

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

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

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

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

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

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

其余的節(jié)點(diǎn)監(jiān)聽數(shù)據(jù)包，由于這個嚴(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ù)用，則它們可以同時發(fā)送數(shù)據(jù)；因此，（全局）調(diào)度程序的副作用是阻礙了利用無線通信的空間復(fù)用性質(zhì)。問題：全局調(diào)度很難實(shí)現(xiàn)！第一百零四頁，共197頁。Idea：采用網(wǎng)絡(luò)編碼在上個例子中，目的節(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)到底接收到了哪個數(shù)據(jù)包；實(shí)際上，R需要發(fā)送的是兩個數(shù)據(jù)包的隨機(jī)線性組和：路由節(jié)點(diǎn)創(chuàng)建一個所有它接收到的數(shù)據(jù)包的線性組合，采用隨機(jī)系數(shù)；目的節(jié)點(diǎn)當(dāng)接收到整個數(shù)據(jù)后，沿著逆向路徑發(fā)送ACK消息；優(yōu)點(diǎn)：不需要節(jié)點(diǎn)的協(xié)同，并且保留了空間復(fù)用。

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

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

routerforwardsrandomcombinationsofpacketssrcR1dstR2α

P1+

?

P2γ

P1+

δ

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

P1+5

P2+

P3+3

P47

P1+3P2+6P3+P4P3P4P1P4P1P2Withoutcodingsourceretransmitsall4packetsWithrandomcoding2packetsaresufficientRandomcombinationsRandomcodingismoreefficientthan

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

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

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