無線網(wǎng)絡(luò)技術(shù)5.2.ppt

1、,無線網(wǎng)絡(luò)技術(shù),計算機(jī)與通信工程學(xué)院 李娜娜 ,第5章 ZigBee 網(wǎng)絡(luò)層原理,5.1 網(wǎng)絡(luò)層 5.2 設(shè)備類型 5.3 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 5.4 地址及其分配方法 5.5 路由協(xié)議 5.6 功能描述網(wǎng)絡(luò)和設(shè)備維護(hù) 5.7 網(wǎng)絡(luò)層常量與參數(shù),5.5 路由協(xié)議,路由算法設(shè)計目標(biāo),路由算法設(shè)計目標(biāo),1)簡單、高效、控制開銷?。?2)無環(huán)路、快速收斂； 3)健壯、穩(wěn)定、靈活；,設(shè)計目標(biāo)1簡單、高效、控制開銷小,設(shè)計目標(biāo)2無環(huán)路、快速收斂,設(shè)計目標(biāo)3健壯、穩(wěn)定、靈活,ZigBee路由協(xié)議,5.5.1 ZigBee路由方式,ZigBee網(wǎng)絡(luò)中，路由方式有以下三種：,網(wǎng)絡(luò)拓?fù)渑c路由方式關(guān)系,每種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2、的路由方式都不相同。 星型和樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)通常采用靜態(tài)路由協(xié)議，如樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)采用Cluster-Tree協(xié)議。 對于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，多采用動態(tài)路由協(xié)議，如ZigBee Ad-Hoc On-demand Distance Vector Routing(ZAODV),ZAODV與自組網(wǎng)中的經(jīng)典AODV協(xié)議不完全一樣，準(zhǔn)備的說是一種簡化版本的AODV junior(AODVjr)。,5.5.2 Cluster-Tree路由算法 P137,ZigBee網(wǎng)絡(luò)的樹型拓?fù)浣Y(jié)構(gòu)中，每一個新入網(wǎng)的節(jié)點(diǎn)，都會與一個父節(jié)點(diǎn)相互對應(yīng)，每一個父節(jié)點(diǎn)可以同時有多個子節(jié)點(diǎn)，但是一個子節(jié)點(diǎn)卻只能有一個父節(jié)點(diǎn)，按照這種方

3、式形成了一顆樹，在路由的時候就按照樹的父子節(jié)點(diǎn)來查找，這種方式稱之為C luster-Tree算法。,5.5.2 Cluster-Tree算法流程,在Cluster-Tree過程中，節(jié)點(diǎn)不需要通過路由發(fā)現(xiàn)過程來進(jìn)行路由，節(jié)點(diǎn)直接通過數(shù)據(jù)包中的目的節(jié)點(diǎn)地址來計算下一跳的地址。 通常的做法是將其簡化為上行路由或者下行路由。,5.5.2 Cluster-Tree算法流程,1. 如果某一個FFD節(jié)點(diǎn)的當(dāng)前地址是A，目的節(jié)點(diǎn)的地址是D，節(jié)點(diǎn)A要向目的節(jié)點(diǎn)D傳輸數(shù)據(jù)，A路由器節(jié)點(diǎn)的深度分別為d，則 2.否則如果節(jié)點(diǎn)A為RFD,要向目的節(jié)點(diǎn)D傳輸數(shù)據(jù)，則只需交由父節(jié)點(diǎn)處理。,5.5.2 Cluster-Tr

4、ee算法流程,1）.如果節(jié)點(diǎn)收到的數(shù)據(jù)是要傳遞給自己的(即目的節(jié)點(diǎn)的地址為本身地址)，那么節(jié)點(diǎn)就不用再轉(zhuǎn)發(fā)數(shù)據(jù)，而是直接上傳到上層處理，否則轉(zhuǎn)2； 2）如果節(jié)點(diǎn)收到的數(shù)據(jù)的目的地址是鄰居節(jié)點(diǎn)，那么可以將數(shù)據(jù)信息直接發(fā)送到鄰居節(jié)點(diǎn)，否則轉(zhuǎn)3； 3）接收到的數(shù)據(jù)包轉(zhuǎn)發(fā)給子節(jié)點(diǎn)或者父節(jié)點(diǎn)。該路由器節(jié)點(diǎn)會依據(jù)下述表達(dá)式判斷目的節(jié)點(diǎn)是否是其后裔節(jié)點(diǎn)：,5.5.2 Cluster-Tree算法流程,如果滿足當(dāng)前條件:ADA+ Cskip(d-1)，則說明目的節(jié)點(diǎn)D是節(jié)點(diǎn)A的子節(jié)點(diǎn)，那么節(jié)點(diǎn)A就可以直接將數(shù)據(jù)發(fā)送給D，下一跳地址A根據(jù)下式計算,否則，若不滿足上述條件，則A將信息上交自己的上一級。,Clust

5、er-Tree路由,Cluster-Tree路由算法維護(hù)過程,5.5.2 Cluster-Tree算法優(yōu)缺點(diǎn),Cluster-Tree算法在一些方面存在著優(yōu)點(diǎn)，比如網(wǎng)絡(luò)結(jié)構(gòu)覆蓋范圍大，節(jié)點(diǎn)不需要維護(hù)路由表，也不需要進(jìn)行路由發(fā)現(xiàn)，減少了網(wǎng)絡(luò)中路由和數(shù)據(jù)處理的開銷，并且算法簡單查找節(jié)點(diǎn)速度較快，可以方便采用數(shù)據(jù)融合技術(shù)減少信息冗余度。 但是同時它也存在著很多的缺點(diǎn)。Cluster-Tree算法這種樹狀結(jié)構(gòu)的網(wǎng)絡(luò)選擇路徑的時候是依靠父子節(jié)點(diǎn)關(guān)系來判斷的，當(dāng)節(jié)點(diǎn)收到了一個數(shù)據(jù)包的分組，如果節(jié)點(diǎn)查找目的地址發(fā)現(xiàn)數(shù)據(jù)包不是發(fā)送給自己的，那么就只能交給子節(jié)點(diǎn)或者父節(jié)點(diǎn)來處理了，不進(jìn)行路由發(fā)現(xiàn)的過程。由于Cl

6、uster-Tree算法這種直接由子節(jié)點(diǎn)或者父節(jié)點(diǎn)來發(fā)送，因此節(jié)點(diǎn)不能夠走最優(yōu)的路徑，相對來說，所走的路徑都會比較偏長，也會給分組的傳輸帶來很高的延時，而且深度較低的節(jié)點(diǎn)對于數(shù)據(jù)量的轉(zhuǎn)發(fā)會比較大，給節(jié)點(diǎn)帶來很大的負(fù)載，很容易造成節(jié)點(diǎn)的流量分配不均衡。,5.5.3 動態(tài)路由協(xié)議AODVjr,5.5.3 動態(tài)路由協(xié)議AODVjr,ZigBee路由器，包括協(xié)調(diào)器均可以執(zhí)行AODVjr路由算法，進(jìn)行路由發(fā)現(xiàn)和選擇、路由維護(hù)等操作。,動態(tài)路由協(xié)議AODVjr,1. AODV 2.AODVjr與AODV比較 3.AODVjr算法流程,5.5.3 動態(tài)路由協(xié)議AODVjr,什么是AODV?,1.AODV,無

7、線自組網(wǎng)按需平面距離矢量路由協(xié)議（Ad hoc On-Demand Distance Vector Routing，AODV），是應(yīng)用于無線網(wǎng)狀網(wǎng)絡(luò)（也稱作無線mesh網(wǎng)絡(luò)）中進(jìn)行路由選擇的路由協(xié)議，它能夠?qū)崿F(xiàn)單播和多播路由。 該協(xié)議是Ad Hoc網(wǎng)絡(luò)中按需生成路由方式的典型協(xié)議。,AODV與因特網(wǎng)路由協(xié)議本質(zhì)區(qū)別,它是反應(yīng)式路由協(xié)議，也就是說當(dāng)向目的節(jié)點(diǎn)發(fā)送包時，源節(jié)點(diǎn)才在網(wǎng)絡(luò)中發(fā)起路由查找過程，找到相應(yīng)的路由。 相反的，因特網(wǎng)路由協(xié)議是先驗式的，也就是說它們查找路由是不依賴于路徑上的節(jié)點(diǎn)是否要發(fā)包，而是每個節(jié)點(diǎn)維護(hù)一張包含到達(dá)其它節(jié)點(diǎn)的路由信息的路由表。節(jié)點(diǎn)間通過周期性的交換路由信息來不斷

8、更新自身的路由表，以便能夠及時的反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和變化，以維護(hù)一致的、及時的、準(zhǔn)確的路由信息。,AODV算法RREQ的處理和反向路徑建立,AODV算法RREP的處理和正向（前向）路徑建立,AODV算法是基于最少跳數(shù)的最短路徑算法,AODV算法路由維護(hù)過程,2.AODVjr與AODV比較,AODVjr與AODV比較1路由選擇的標(biāo)準(zhǔn)不同,路由成本為路由發(fā)現(xiàn)和維護(hù)管理提供了一種度量的方法，是用來比較路由好壞的基礎(chǔ)。 AODV算法采用基于最少跳數(shù)的最短路徑算法作為路由選擇的依據(jù)（傳統(tǒng)的距離矢量路由機(jī)制），而ZigBee網(wǎng)絡(luò)則采用基于信道質(zhì)量的最優(yōu)路徑算法作為路由選擇的依據(jù)。,ZigBee路由成本 P1

9、33,ZigBee路由成本,Round(A):對A進(jìn)行四舍五入取整數(shù)。,AODVjr與AODV比較2路由發(fā)現(xiàn)過程簡化,路由發(fā)現(xiàn)過程的簡化,AODVjr路徑發(fā)現(xiàn)的基本思想： 通過傳播路由包請求包RREQ(Route Request Message)與路由回復(fù)包RREP(Route Reply Message)實(shí)現(xiàn)路由查找和記錄。 當(dāng)RREQ和RREP包在兩點(diǎn)之間傳遞時，這兩點(diǎn)之間的損耗最小的路徑會被記錄下來并保存在路由表中。 節(jié)點(diǎn)收到數(shù)據(jù)包后查詢路由表，如果有到目的節(jié)點(diǎn)的最小損耗路由，則按照該路由傳送數(shù)據(jù)，如沒有則啟動AODVjr查找路由，發(fā)送RREQ包查找路由。若收到了目的節(jié)點(diǎn)的RREP包，則

10、證明有最優(yōu)路由存在，則可以按照此路由傳數(shù)據(jù)包。,AODVjr與AODV比較3路由維護(hù)過程簡化,AODVjr相對于AODV，采用了終端對終端機(jī)制，目標(biāo)節(jié)點(diǎn)需要定時發(fā)送給源節(jié)點(diǎn)KEEP-ALIVE包（以維護(hù)路由表），如果在數(shù)據(jù)傳輸過程中發(fā)生鏈路中斷，那么源節(jié)點(diǎn)將不能接收到從目的節(jié)點(diǎn)發(fā)來的信息。當(dāng)節(jié)點(diǎn)離開路徑一段時間后，源節(jié)點(diǎn)將偵聽到路徑鏈路中斷，如果還需要路由的話，將進(jìn)行路由修復(fù)（具有網(wǎng)絡(luò)自愈功能）。 相比較于AODV算法而言，AODVjr 則不需要HELLO、RERR包的發(fā)送，大大節(jié)省了控制開銷。,AODVjr與AODV路由維護(hù)比較,AODVjr與AODV路由維護(hù)比較,路由表 P134,AODV

11、jr與AODV比較4路由表的簡化,路由表的簡化,AODVjr與AODV比較5路由環(huán)路的避免,AODVjr中則不使用節(jié)點(diǎn)序列號，僅規(guī)定目的節(jié)點(diǎn)回復(fù)RREP，并且采用了終端對終端機(jī)制，目標(biāo)節(jié)點(diǎn)需要定時發(fā)送給源節(jié)點(diǎn)KEEP-ALIVE包（以維護(hù)路由表），這樣同樣能避免路由環(huán)路，同時可以進(jìn)一步減少開銷。,什么是路由環(huán)路？,在維護(hù)路由表信息的時候，如果在拓?fù)浒l(fā)生改變后，網(wǎng)絡(luò)收斂緩慢產(chǎn)生了不協(xié)調(diào)或者矛盾的路由選擇條目，就會發(fā)生路由環(huán)路的問題，這種條件下，路由器對無法到達(dá)的網(wǎng)絡(luò)路由不予理睬，導(dǎo)致用戶的數(shù)據(jù)包不停在網(wǎng)絡(luò)上循環(huán)發(fā)送，最終造成網(wǎng)絡(luò)資源的嚴(yán)重浪費(fèi)。為此，解決路由環(huán)路的問題的方法就出現(xiàn)了。,3.AODVjr算法流程,5.5.4 ZBR路由算法,ZBR算法設(shè)計思想,5.6 功能描述網(wǎng)絡(luò)和設(shè)備維護(hù) P125,例如： 建立一個新網(wǎng)