現(xiàn)代通信技術(shù)課程10

1、4、 網(wǎng)絡(luò)路由協(xié)議原理 4.1 有線路由協(xié)議 4.2 無線路由協(xié)議 4.3 機(jī)會(huì)路由協(xié)議現(xiàn)代通信技術(shù)課程現(xiàn)代通信技術(shù)課程主講：宋梁，主講：宋梁，LSONGIEEE.ORGLSONGIEEE.ORGQQQQ群：群：3149458742012015 5-201-2016 6章節(jié)概覽4.3.1 機(jī)會(huì)路由簡(jiǎn)介4.3.2 機(jī)會(huì)路由的協(xié)作機(jī)制4.3.3 候選節(jié)點(diǎn)的選擇4.3.4 已有的機(jī)會(huì)路由協(xié)議4.3.5 機(jī)會(huì)路由所面臨的挑戰(zhàn)4.3.6 總結(jié)2無線傳感網(wǎng)的應(yīng)用戶外監(jiān)測(cè)3無線傳感網(wǎng)的應(yīng)用室內(nèi)監(jiān)測(cè)4機(jī)會(huì)路由簡(jiǎn)介近年來，無線網(wǎng)絡(luò)在生活中的應(yīng)用場(chǎng)景越來越豐富，并且不斷有新的應(yīng)用被挖掘出來，但是無線網(wǎng)絡(luò)的潛能并沒

2、有被充分的挖掘出來。大多數(shù)網(wǎng)絡(luò)路由協(xié)議都是基于傳統(tǒng)有線網(wǎng)絡(luò)改進(jìn)而來，從而忽略了無線網(wǎng)絡(luò)的廣播特性，錯(cuò)失了許多無線網(wǎng)絡(luò)可能帶來的許多優(yōu)點(diǎn)。5機(jī)會(huì)路由的提出 對(duì)于傳統(tǒng)的路由協(xié)議而言，由于發(fā)展自有線網(wǎng)絡(luò)，所以在數(shù)據(jù)發(fā)送之前，數(shù)據(jù)的傳輸路徑就已經(jīng)確定。由于無線鏈路的不穩(wěn)定性，這種方式對(duì)于無線網(wǎng)絡(luò)來說這無疑是不可靠的。2005年，MIT的CSAIL實(shí)驗(yàn)室提出了機(jī)會(huì)路由的概念。6機(jī)會(huì)路由的基本思想充分利用了無線網(wǎng)絡(luò)的廣播特性 7機(jī)會(huì)路由的基本思想RTS 8機(jī)會(huì)路由的基本思想 CTS9機(jī)會(huì)路由的基本思想確定候選節(jié)點(diǎn)集以及避免重復(fù)傳輸 10機(jī)會(huì)路由的基本思想 從源節(jié)點(diǎn)傳輸數(shù)據(jù)到目的節(jié)點(diǎn)，對(duì)于傳統(tǒng)的路由協(xié)議，可

3、能會(huì)將路徑設(shè)置為 src-B-D-dst，但是由于無線傳輸?shù)膹V播特性和鏈路的不確定性，B節(jié)點(diǎn)并沒有收到源節(jié)點(diǎn)發(fā)來的信息，C節(jié)點(diǎn)卻收到了。那么這次傳輸對(duì)于傳統(tǒng)路由來說就失敗了。11機(jī)會(huì)路由的基本思想 但是，機(jī)會(huì)路由則將其視為一次幸運(yùn)的傳輸，C明顯比B距離目的節(jié)點(diǎn)要近一些。在機(jī)會(huì)路由中，C節(jié)點(diǎn)將會(huì)承擔(dān)下一步的傳輸任務(wù)，接著將數(shù)據(jù)傳輸下去。也就是說機(jī)會(huì)路由的下一條地址在數(shù)據(jù)傳輸之前是不確定的，數(shù)據(jù)傳輸后，所有收到數(shù)據(jù)的優(yōu)先級(jí)最高的節(jié)點(diǎn)才會(huì)成為路徑的下一跳。12章節(jié)概覽4.3.1 機(jī)會(huì)路由簡(jiǎn)介4.3.2 機(jī)會(huì)路由的合作策略4.3.3 候選節(jié)點(diǎn)的選擇4.3.4 已有的機(jī)會(huì)路由協(xié)議4.3.5 機(jī)會(huì)路由所面

4、臨的挑戰(zhàn)4.3.6 總結(jié)13機(jī)會(huì)路由的兩個(gè)基本組成要素合作策略和候選節(jié)點(diǎn)集的選擇是設(shè)計(jì)機(jī)會(huì)路由的兩個(gè)必要組成部分。14機(jī)會(huì)路由的合作策略從發(fā)送者的角度來說，合作策略用于挑選出最佳的候選節(jié)點(diǎn)。對(duì)于候選節(jié)點(diǎn)來說，合作策略用來決定節(jié)點(diǎn)的當(dāng)前狀態(tài)和是否傳輸收聽到的數(shù)據(jù)包以及何時(shí)傳輸數(shù)據(jù)包。15機(jī)會(huì)路由的合作策略已有的合作策略根據(jù)運(yùn)行機(jī)制的不同可以分為三類：定時(shí)器（Timer），令牌（Token），網(wǎng)絡(luò)編碼（Network coding）16基于定時(shí)器的路由策略發(fā)送數(shù)據(jù)包前，源節(jié)點(diǎn)會(huì)根據(jù)一個(gè)測(cè)量方法確定一個(gè)候選節(jié)點(diǎn)集，并且給候選節(jié)點(diǎn)集中的節(jié)點(diǎn)做一個(gè)優(yōu)先級(jí)排序。節(jié)點(diǎn)在收到數(shù)據(jù)包后，會(huì)根據(jù)自己的優(yōu)先級(jí)排序設(shè)

5、置定時(shí)器以等待比自己優(yōu)先級(jí)高的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。待定時(shí)器設(shè)定的時(shí)間到達(dá)，則開始發(fā)送數(shù)據(jù)。即，第i個(gè)節(jié)點(diǎn)會(huì)在第i個(gè)時(shí)間間隙發(fā)送數(shù)據(jù)包。17基于定時(shí)器的路由策略 基于定時(shí)器策略的路由協(xié)議實(shí)施起來較為簡(jiǎn)單，也是第一次提出機(jī)會(huì)路由概念是所用的策略。最大缺點(diǎn)是重復(fù)傳輸，因?yàn)閭鬏敂?shù)據(jù)的節(jié)點(diǎn)不能保證所有的候選節(jié)點(diǎn)收到他的確認(rèn)信息，從而造成低優(yōu)先級(jí)的節(jié)點(diǎn)重復(fù)傳輸數(shù)據(jù)。 代表路由：ExOR（Extremely Opportunistic Routing）18基于令牌的路由策略在基于令牌策略的路由中，只有拿到令牌的節(jié)點(diǎn)才能傳輸數(shù)據(jù)，從而完全避免了數(shù)據(jù)的重復(fù)傳輸，但是這樣又增加了控制包的開銷。代表算法：Economy1

6、9基于網(wǎng)絡(luò)編碼的路由策略在這種策略中，原始數(shù)據(jù)被分割成數(shù)據(jù)段，然后進(jìn)行線性編碼。當(dāng)目的節(jié)點(diǎn)收到足夠多的數(shù)據(jù)段后即可解碼出原始數(shù)據(jù)。代表路由：MORE20基于網(wǎng)絡(luò)編碼的路由策略網(wǎng)絡(luò)編碼示意圖P1，P2為源節(jié)點(diǎn)進(jìn)行線性編碼后的數(shù)據(jù)包，P3為R1收到其中一個(gè)數(shù)據(jù)包后再一次線性編碼的數(shù)據(jù)包，P4為R2將收到的兩個(gè)數(shù)據(jù)包進(jìn)行在編碼后的包。目的節(jié)點(diǎn)在收到P3，P4后可解碼出原始數(shù)據(jù)21章節(jié)概覽4.3.1 機(jī)會(huì)路由簡(jiǎn)介4.3.2 機(jī)會(huì)路由的合作策略4.3.3 候選節(jié)點(diǎn)的選擇4.3.4 已有的機(jī)會(huì)路由協(xié)議4.3.5 機(jī)會(huì)路由所面臨的挑戰(zhàn)4.3.6 總結(jié)22候選節(jié)點(diǎn)集的選擇候選節(jié)點(diǎn)集的確定可以進(jìn)一步劃分為候選節(jié)

7、點(diǎn)集的篩選和候選節(jié)點(diǎn)的排序23候選節(jié)點(diǎn)的篩選候選節(jié)點(diǎn)越多，鏈路的傳輸性能會(huì)越好，但是同時(shí)也會(huì)增加通信成本，并且產(chǎn)生重復(fù)傳輸，所以候選節(jié)點(diǎn)的數(shù)量應(yīng)該控制在合適的范圍內(nèi)。24候選節(jié)點(diǎn)集的篩選如圖，假設(shè)每條鏈路的PDR值為80%，隨著候選節(jié)點(diǎn)的增加，虛擬鏈路的PDR也隨之增加，但是增加的幅度越來越小，再增加節(jié)點(diǎn)反而會(huì)降低網(wǎng)絡(luò)的性能，因?yàn)楣?jié)點(diǎn)間的協(xié)商通信花銷會(huì)增加很多。25候選節(jié)點(diǎn)的優(yōu)先級(jí)排序 候選節(jié)點(diǎn)的排序用于確定到達(dá)目的節(jié)點(diǎn)的最佳路徑 節(jié)點(diǎn)優(yōu)先級(jí)的排序有多種測(cè)量方法，如傳統(tǒng)路由中的距離向量法，或是簡(jiǎn)單的跳數(shù)都可以作為選定優(yōu)先級(jí)的測(cè)量方法。26候選節(jié)點(diǎn)的優(yōu)先級(jí)排序 另外，最新提出的更加適用于機(jī)會(huì)路由

8、的度量方法有 ETX（expected number of transmissions）和 ETT(expected transmission time)27利用ETX進(jìn)行節(jié)點(diǎn)的優(yōu)先級(jí)排序 ETX為期望傳輸次數(shù)，即一個(gè)節(jié)點(diǎn)要成功把一個(gè)報(bào)文發(fā)送到一個(gè)目標(biāo)節(jié)點(diǎn)所期望的轉(zhuǎn)發(fā)次數(shù)。ETX越小，說明該節(jié)點(diǎn)把報(bào)文傳輸給目標(biāo)節(jié)點(diǎn)所需要轉(zhuǎn)發(fā)的次數(shù)少，消耗小，成功概率高。28利用ETX進(jìn)行節(jié)點(diǎn)的優(yōu)先級(jí)排序ETX值與路徑的選擇有關(guān)。如圖所示，選擇路徑A-B-C-D，則A到D的ETX值為1/0.9+1/0.9+1/0.9=3.3次；而若選擇路徑A-C-D，則A到D的ETX值為1/0.4+1/0.9=3.6次。29利

9、用ETX進(jìn)行節(jié)點(diǎn)的優(yōu)先級(jí)排序上圖中，節(jié)點(diǎn)A到節(jié)點(diǎn)D最短路徑的ETX值為3.3，而節(jié)點(diǎn)B到節(jié)點(diǎn)D的最短路徑ETX值為2.2，所以節(jié)點(diǎn)B屬于節(jié)點(diǎn)A到節(jié)點(diǎn)D的候選節(jié)點(diǎn)集。途中節(jié)點(diǎn)的優(yōu)先級(jí)從高到低依次排序?yàn)椋篋CBA.即當(dāng)這些節(jié)點(diǎn)都收到數(shù)據(jù)包時(shí)，節(jié)點(diǎn)D的優(yōu)先級(jí)最高。30章節(jié)概覽4.3.1 機(jī)會(huì)路由簡(jiǎn)介4.3.2 機(jī)會(huì)路由的協(xié)作機(jī)制4.3.3 候選節(jié)點(diǎn)的選擇4.3.4 已有的機(jī)會(huì)路由協(xié)議4.3.5 機(jī)會(huì)路由所面臨的挑戰(zhàn)4.3.6 總結(jié)31已有的機(jī)會(huì)路由概覽2005年，ExOR作為首個(gè)機(jī)會(huì)路由被提出，在機(jī)會(huì)路由領(lǐng)域具有奠基者的作用，接著另一個(gè)基于定時(shí)器的OR協(xié)議SOAR被提出，SOAR的最大特點(diǎn)是它的候選

10、節(jié)點(diǎn)是由源節(jié)點(diǎn)和中繼節(jié)點(diǎn)共同決定的。32已有的機(jī)會(huì)路由概覽2007年，MORE作為第一個(gè)基于網(wǎng)絡(luò)編碼的機(jī)會(huì)路由被提出。MORE在PC終端上已經(jīng)被證明是可行的。雖然MORE不再需要額外的協(xié)商信息，但是在數(shù)據(jù)串長(zhǎng)度上還有限制，并且仍然存在冗余數(shù)據(jù)包。接著，CodeOR,SlideOR等在數(shù)據(jù)串長(zhǎng)度沒有限制的協(xié)議相繼被提出。33已有的機(jī)會(huì)路由概覽Economy是唯一應(yīng)用令牌機(jī)制的機(jī)會(huì)路由協(xié)議。它的主要優(yōu)點(diǎn)在于完全避免了重復(fù)數(shù)據(jù)包的傳輸。34章節(jié)概覽4.3.1 機(jī)會(huì)路由簡(jiǎn)介4.3.2 機(jī)會(huì)路由的協(xié)作機(jī)制4.3.3 候選節(jié)點(diǎn)的選擇4.3.4 已有的機(jī)會(huì)路由協(xié)議4.3.5 機(jī)會(huì)路由所面臨的挑戰(zhàn)4.3.6 總結(jié)35機(jī)會(huì)路由所面臨問題與挑戰(zhàn)基于令牌的機(jī)會(huì)路由增加了網(wǎng)絡(luò)中的控制信息，基于網(wǎng)絡(luò)編碼的機(jī)會(huì)路由冗余信息過多。通過比較，我們可以從中看出每種路由的潛力，并做進(jìn)一步的研究和改進(jìn)。36機(jī)會(huì)路由所面臨問題與挑戰(zhàn)對(duì)于大多數(shù)無線網(wǎng)絡(luò)來說，能耗問題是一個(gè)至關(guān)重要的問題，在設(shè)計(jì)路