太爽ㄌ....
花了兩天兩夜掰ㄌ一人生第一篇唬爛用的論文....
現在只想問老師....
我可以畢業了嗎????
以Cluster-Tree拓樸特性建構之高效能ZigBee網路新架構
花了兩天兩夜掰ㄌ一人生第一篇唬爛用的論文....
現在只想問老師....
我可以畢業了嗎????
以Cluster-Tree拓樸特性建構之高效能ZigBee網路新架構
林宗宏 劉宏偉 李文耀 陳瑞茂
國立勤益科技大學 國立勤益科技大學 廈門華廈職業學院 國立勤益科技大學
資訊工程系 電子工程系 技術與市場開發中心 資訊工程系
l 摘要
在本論文中，我們將提出新的一套具效率網路拓樸協定，用來建構於ZigBee通訊協定標準IEEE802.15.4之上。在傳統的IEEE 802.15.4網路標準當中，提出了一些基本的拓樸方式來建構符合Zigbee在無線感測網路(Wireless sensor network,WSN)中所必需使用的網路組織方式，後來又有許多先進在這方面基於效能的考量提出更為複雜的網路組織協定，期盼改善IEEE 802.15.4網路協定效能問題。
在許多衍生的網路基礎協定中，最常被使用的是Cluster-Tree(CT)拓樸協定，但由於IEEE 802.15.4對其網路建置之後的樹狀結構並沒有定義是否需要一些符合效能考量的限制[1]，且在CT樹又存在著Child header(CH)資訊蒐集負荷過重問題，因此CT建構的網路效能通常不具最佳效能與穩定性!因此CT效能改進便吸引許多專家學者的目光定針對其特性找出效能最佳化方法，如Yuh-Shyan Chen 與 Tsung-Hung Lin共同發表的”A Qos Routing Protocol using Cluster-Mesh-Tree for IEEE 802.15.4 Low-Rate WPANs”一文中便提出一種以CT為基礎進行改善之後的拓樸協定Cluster-Mesh_tree。[2]
在本論文中，我們也將提出以Cluster-Mesh=tree(CMT)為基礎，並加入Cluster-Tree的拓樸特性考量元素產生一套新的Best of Cluster-Mesh-Tree(BOCMT)拓樸協定，並證明其效能在考量CT拓樸限制性之因素後，確實效能比原CMT還要好。
關鍵詞: ZigBee , IEEE 802.15.4 , Cluster-Tree , Cluster-Mesh-Tree , WSN
l 前言
2.1 IEEE 802.15.4 簡介
無線個人區域網路(Wireless personal area networks, WPANs)是短距離行動裝置間用來互相交換資訊的網路組織方案[4,5]，由於其架構並不像傳統網路組織需要複雜佈線與基礎資訊建設支援，所以非常適用於行動裝置間組織成區域網路的實現，因為其符合行動裝置需要的自由組織網路特色，且其佈建成本低廉，故發展出許多相關的技術標準支援無線個人區網的建置!
其中比較重要的一項標準便是IEEE 802.15.4協定，這是一套用以組織低功耗、低資料速率與低成本的低功率無線個人區域網路協定(Low-rate Wireless personal area networks, LR-WPAN)[2,4,5]，這套協定應用相當廣泛，尤以應用於無線感測網路的生活智慧控制最為主要，ZigBee無線感測網路便是以IEEE 802.15.4為基礎所發展出來的無線感測技術，舉凡家庭自動化、遠端監控、玩具生產、健康照護…等等都是其相關應用主題[2,4]，這在講求EMU(E化、行動化、優化)品質生活的今天可說是一項重要的技術規格。
2.2 IEEE 802.15.4 拓樸方式
在IEEE 802.15.4中，由於其主要應用於低功率行動裝置或節點的網路組織上，因此特別注重其使用效率，最重要的兩點在於其必需是低功耗以及傳輸穩定的，因為行動裝置多半低功率，所以並不能允許大量功耗情形發生在IEEE 802.15.4網路組織上，會造成網路節點容易斷線或故障，另一方面由於無線環境在傳輸距離上相對受到比較大的限制，因此如何使兩端傳遞資料的節點間能順利在彼此間收發訊息，而能盡量擺脫所有實體環境中可能出現的干擾，所以在發展IEEE 802.15.4拓樸時特別著重如何做到低功耗以及高效能傳輸還有網路生命週期的延長，期使網路能穩定運作。
而IEEE 802.15.4主要的網路組織方式主要有兩種，一種為星狀拓樸(Star Topology)，另一則為點對點網路(Peer to Peer Topology)![1,2,3,4,5]兩種拓樸形式如圖1(a)與1(b)所示，而星狀拓樸屬於主從式(Master-Slave)拓樸架構，即網路上所有節點只有一個主節點，負責連結管理網路上所有其它的節點，而其他節點則必需與主節點相連，彼此間通訊則需透過主節點才能達成;至於點對點拓樸則是所有節點地位平等，彼此間可以透過連結程序互相發現並且傳遞溝通訊息。
(a)
(b)
(c)
圖1.三種常見IEEE802.15.4拓樸型態(a) star (b)peer to peer (c)cluster-tree[3]
此後，點對點拓樸又衍生出更先進的網路架構，稱為Cluster-Tree(CT) topology[1,2]，是由一個根節點PAN coordinator與其他以Child header(CH)節點為根的樹狀結構所組成，如圖1(c)所示，其中每一個Child header都是PAN coordinator的子節點，所以根節點理所當然是整個CT的管理者，存有所有子節點的資訊，而每一個CH則主管其下所有子節點資訊，在傳遞資訊時，所有子節點必需將資訊透過其父節點轉送，不同的CH要交換資訊則透過PAN coordinator 負責，如此將所有Child header網路叢集起來且以祖孫關係為基礎的樹狀拓樸結構稱作Cluster-Tree topology。
至於Cluster-Mesh-Tree(CMT) topology[1]則是由一些教授根據CT缺陷改提出改善修正而來的，其相較於傳統拓樸最大的不同是提出了所謂Mesh-link概念，即CT中只存在一種鏈結稱為Tree-link，CMT作者在其提出的方式中利用新增的Mesh-link鏈結來補償傳統CT效能上的缺陷，至於CMT詳細介紹，將在後面研究方法章節中詳細說明。
2.3 CMT的修正
雖然CMT方法是根據CT方法所提出的修正方案，但是依然是根據IEEE 802.15.4標準所建構的規格，對於節點的建構最終形態並沒有任何限制[1,4]，只要是在訊號涵蓋範圍內就能透過連結程序組織起整個網路，卻忽略了根本上CT拓樸可能產生的問題。
因為CMT也是建構於CT基礎之上，所以CMT其實也是一棵CT樹，其本身自然擁有所有CT擁有的樹狀特性，而F. Cuomo等人在”Topology formation in IEEE 802.15.4:
cluster-tree characterization”一文中便探討到一個重要的概念:”拓樸的結構特性將會造成CT拓樸上效能的損失”[1]，基於此論點，我們注意到CMT的效能必然也碰到與CT一樣效能受到結構特性影響的問題，所以我們修正CMT方法，對其組織的最終網路結構加入考慮CT拓樸特性的因子，以限制不良樹狀結構所造成的效能不佳問題，藉此增進CMT效能，並稱此方法為Best of Cluster-Mesh-Tree(BOCMT)，最後證明此方法確實達到最佳化CMT效能的目的，也就能用來當作ZigBee的新網路架構
在接下來的部份，我們將先探討我們在研究時所用到的理論模型，並且提出BOCMT改正CMT效能的探討，接著再以BOCMT與CMT比較效能，在確定結果BOCMT確實優於CMT之後，我們在最後為文章做一個總結。
l 研究方法
3.1理論基礎
3.1.1 Cluster-Tree特徵描述
在前言當中，我們對於Cluster-Tree架構已有初步的一個了解，而在這邊我們將直接進入關於Cluster-Tree一些特徵現象的討論，並以其在建構與分析IEEE 802.15.4拓樸上的應用為主軸，探討Cluster-Tree的特性
在F.Cuomo 等人所提出的論文:”Topology formation in IEEE 802.15.4: Cluster-tree characterization”中，主要對傳統Cluster-tree架構提出一些效能改進上所必需考慮的關鍵問題，他們提出在IEEE 802.15.4 的標準中，對於節點組織的形式並沒有任何限制(無限制性)，僅依其簡單的協定溝通程序來連結無線區域網路，卻忽略了在大量節點數的網路中，若建構在以Cluster-tree為基礎的拓樸策略上所可能面臨的一些無形頻寬與功耗或記憶空間的浪費造成效能嚴重下降的問題!
因此，F.Cuomo等人認為必需對IEEE 802.15.4網路的Cluster-tree拓樸策略訂出一個合理限制，也就是限制節點的組織成長方式(限制性)，他們利用三個可能會影響拓樸建成後效能的參數如下:
η_mean: the mean number of children per parent, computed for each tree level, and averaged on all the formed M*S trees;[1]
C_max: the maximum number of children per parent, computed for each tree level and measured over all the formed M*S trees.[1]
T: the tree height, computed as the maximum
tree depth for all M*S trees.[1]
用ns-2軟體模擬在不同節點數下，每一個節點數均執行數回，因在模擬過程中，即使同樣節點數的情況下，由於網路上節點每次模擬的分佈位置都不相同，故建構出來的樹狀結構也會有所不同(如圖2a)，故同一種節點數必需模擬數回，再取各種節點數下多次模擬的結果平均值來比較其C_Max、T、η_mean特性，以了解其對拓樸效能的影響方為客觀。
結果發現以下特點:
1.無論節點數為多少，低階度節點的C_Max都高於後面高階度的節點;而η_mean的分佈曲線也是呈現與C_Max相同的走向，隨著階度愈高愈遞減(如圖2b與2c)
2.呈上所述，作者發現在建構樹的過程中必需對樹的每個節點所能擁有的最大節點數作一限制，我們稱此樹為Cm，但是Cm值若太高將造成後面高階度的節點由於兒子比較少所以會造成位址空間浪費，太低則低階度所需子節點數又將不夠，故必需小心選擇
3.作者也發現，當建成的樹的高度太高，由於節點間溝通會消耗功率，所以如果兩溝通的節點之間因樹的高度結構因素而必需經手多個中介路由傳送資料的話將嚴重耗費功率；但若給予樹的高度一個太低的限制，我們稱此限制樹高度的值為T_Max，如果太低，則網路上一些離PAN coordinator或Child header太遠的節點將被遺失掉，如此又造成網路連結品質下降，故也要對T_Max訂定一合理限制方能最佳化網路傳輸效能。
綜上所述，我們得知兩個很重要的Cluster-tree特徵參數:T_Max與Cm，我們知道在有限制情況下一般都有比較好的效能，除非是比較特舒的情況下，所以我們可以用這兩個特徵參數(T_Max與Cm)來分析驗証Cluster-Mesh-Tree是否效能較佳的原因與此二特徵值相關。
(a)由於每一次模擬的節點分佈結果不同，故建出來的CT樹高度也不同
(b)隨著CT的節點階度增加，每一節點的平均兒子數也不斷減少
(c)隨著CT的節點階度增加，每一階節點的最大兒子數也不斷減少
圖2. 一些CT拓樸特性模擬結果[1]
3.1.2 Cluster-Mesh-Tree 拓樸
Cluster-Mesh-Tree(CMT)方法是經由Cluster-Tree方法修正而來的，在這個方法中提出了Qos(Quality of service)備份路徑[2]的機制來改進Cluster-Tree的效能。
在IEEE 802.15.4當中對於Cluster-Tree結構並沒有提供多路徑選擇的概念，也就是路由路徑在網路中只有一條，若在資訊傳遞過程中發生節點故障或因管理路由資訊的FFD(full-functions devices,可以當它是CH或PAN coordinator)[1,2,4]忙碌中無法處理要轉送的新資訊，這時就會造成效能下降以及網路不穩的情況，因為路徑被阻所以資料在路徑被修復前無法傳遞，造成延遲現象。
因此CMT提出了備份路徑的概念，它在拓樸機制中加入新的鏈結結構，Mesh-link[1]，再加上原本樹就有的Tree-link，CMT拓樸主要由這兩種鏈結組織而成!而Tree-link提供了父子關係連結路徑；Mesh-link則提供同一Cluster範圍內兄弟節點連結的路徑，而Mesh-link正是備份路徑得以產生的關鍵!
對比於CT的單一路徑，很明顯CMT將有較高的效能與網路生命週期!首先，由於備份路徑的存在，使得即使原來利用Tree-link連結的資料路徑即使因為認何原因而無法使用，CMT可透過與其父節點或CH溝通，向其租貸訊息溝通權，而直接與另一兄弟節點分享資料，不再透過CH或父節點，因此資料延遲現象會獲得改善，因為資料並非像CT一樣只有一條路徑走，更可以在不透過資料轉送管理者的情況下從新路徑前進目的地，所以沒有排隊等待，效能自然比較好。
其次，關於生命週期則是指網路而言，在CT中FFD設備掌握了所有子節點資訊的管理權，因此負擔相當沉重，也因此功耗就比較明顯，生命週期也隨之減短，一旦故障將造成整個網路的不穩定，所以網路生命週期較短；相較於CMT方法，由於子節點可以向父節點要求合理的資訊管理權，這種現象降低了父節點工作負荷量，自然而然裝置生命週期就長，再加上替代路徑策略使網路運作在效能提高情況下還能順暢工作，網路自然也就可以延長生命週期，而且提高了通訊的穩定性!
以上是對於CMT工作原理作一簡單介紹，接下來我們將以簡單圖例( 圖3)說明CMT架構與運作方式，然後進入我們實驗設計主題探討效能的分析方法，讀者若想更進一步了解CMT運作細節，請參閱由 Yuh-Shyan Chen 與 Tsung-Hung Lin共同發表的”A Qos Routing Protocol using Cluster-Mesh-Tree for IEEE 802.15.4 Low-Rate WPANs”一文:
圖3.上列是一CMT拓樸範例，其中構成三角形的虛線即Mesh-link，S則是要傳送資料給D的發射端，D為資料接收端，圖上圓滑曲線則是傳統CT單一路徑，需透過FFD裝置傳遞資訊，此例資料可透過CMT新路徑傳遞資料
3.2 Best of Cluster-Mesh-Tree Topology, BOCMT
在討論過CT與CMT兩種拓樸方式之後，雖然我們了解CMT所提供的備份路徑策略可以減輕CH負荷並有效使用頻寬，但卻無法解決一旦網路組織龐大，樹狀結構不平衡所造成結構性效能浪費問題，因此我們針對大型無線網路組織的拓樸對CMT效能提出新的改進方式，當網路節點樹較為龐大時，我們可以透過調整CMT樹為一最佳結構的方式來加強CMT的網路溝通效能。
我們透過F.Cuomo等人對CT拓樸特性的文章中得到一個最佳論點:”當我們對CT或CMT樹的高度與子節點樹提出適當限制時，將可避免因樹狀結構不平衡所造成的效能減損問題，而樹的高度與子節點數是CT拓樸中影響效能的最關鍵因素，因此只要找到最佳樹的高度限制值T_Max與每一父節點最大子節點數限制值Cm，便能將樹調整至最佳效能狀態。”[1]
基於此論點，我們在本篇文章將對CT樹的T_Max與Cm值提出一合理理論值，用來限制CMT樹的樹狀結構，我們可以透過重新選擇最佳CH與PAN的方式來建立符合我們限制架構的新拓樸結構，而在設定T_Max與Cm值的時候可以不必為Cm值可能影響到樹的高度而困擾，因為在F.Cuomo等人提出的CT拓樸特性描述一文當中已證明對Cm的限制將不會影響樹的高度，而在經過限制後的CMT樹，必然比原來未受任何限制所建構的CMT樹更加有效能，我們稱此受限制的CMT結構為BOCMT，並將在最後證明BOCMT樹擁有比CMT樹為佳的效能，在網路節點分佈造成組織極不均勻的情況下。
3.3實驗模擬
3.3.1 T_Max與Cm最佳效能值
由於CMT樹的結構是行成於節點間的互相傳遞溝通之上，而節點間的互相傳遞溝通又受到訊號涵蓋範圍影響，因此節點間的連結會受到距離的影響與受限，所以樹的連結就必需透過高度的增加以取得離根較遠節點的連結，因此若訂下對樹的高度的限制，我們將無法掌握分佈較為偏遠的節點而失去連結，因此我們是假設在允許少數節點失連的情況下提出T_Max，當然這允許比率必需愈小愈好，可實際上我們認為應該根據實際應用時需求而定會比較好，在拓樸特性分析中提到當T_Max=8時可確保70%以上的網路節點被連結，並且由於一般CT樹的高度都有超過90%在7以下，因此我們假設T_Max=8為最佳限制，因為通常已足夠建構任何樹，而且連結漏失率也較T=7為低，因為樹高度愈高愈能連結偏遠節點。
至於Cm值，由於接近CT樹根階度的節點通常擁有較多子節點，尤其是位在階度為一的節點，所擁有的最高子節點數(C_Max)通常最大，且因為CT必需為每一節點保留夠用的子節點空間，因此每一節點最大子節點數的限制理應受到擁有最高C_Max的節點所左右，我們發現在一階時有超過90%的樹其擁有C_Max=15，因此我們假設Cm=15時有最佳效能，因為Cm訂太高會造成不必要的空間浪費，效率自然又下降一些。所以Cm設定是以子節點數夠用為原則。
在後面我的分析模擬中，我們今以BOCMT_P(T,C)與CMT_P(T,C)分別代表BOCMT樹與CMT樹的高度與每一父節點可納子節點數。而下表1則是我們用ns-2模擬的還境參數:
表1.實驗模擬參數
|
Number of nodes N = 100 – 2000
|
|
|
Side of the square area, L
|
1500 m *1500 m
|
|
Radio transmission range , R
|
150 m
|
|
Cycle time
|
16 time slots
|
|
Package length
|
1 time slots
|
|
Mobility
|
No
|
|
Qos request length
|
5-20 packages
|
|
Qos bandwidth
|
2-4 time slots
|
|
Qos request frequency
|
2 requests/cycle
|
3.3.2 模擬模型
在我們的實驗過程中，我們是以ns-2網路環境模擬器來作為實驗平台，而在我們的實驗做法上，我們則是設定在不同節點的情況下，比較以BOCMT與CMT兩種不同方法所構成的網路組織效能，在評估效能時我們則是以下列參數為效能指標(Performance metrics):
Success rate: the ratio of successful requests/packages to the total requests/packages.(SR_Req & SR_Pack) [2]
Throughput: the value of all data bytes received by all devices from the starting to the designated cycle time.[2]
Bandwidth utilization: the ratio of all used time slots of successful QoS requests[2]
其中我們是假設在節點數為100-2000個的情況下，每增加100個節點為一run來觀察BOCMT與CMT的效能，並依實驗結果說明BOCMT確實增強了CMT樹的效能。
3.4實驗結果分析
在圖4(a)(b)(c)(d)中，我們可以看到分別比較Success rate request/package 以及 Throughput ， Bandwidth utilization的結果，其中我們可以發現不論是在資料傳遞或者是生產量、頻寬使用率，在BOCMT中都擁有高於CMT的效能，於是我們再觀察不同節點數下BOCMT的BOCMT_P(T,C)與CMT的CMT_P(T,C)值，以了解二者所建構的樹高度與子節點數限制之異同(參閱表1.)，在表一中我們發現BOCMT_P(T,C)=(8,15)，是唯一值，這是因為我們已對每一節點數產生的CMT數作過調整，調整為我們想要的BOCMT樹，CMT_P(T,C)部份則因為每一次執行的節點分佈不同所以造成結構上產生差異，然而參看表1與圖4的模擬結果之後，我們證明了架構受限制的BOCMT樹確實擁有比CMT樹有較高的網路效能與穩定性，在節點遺失率允許為30%以下的情況下。
(4a)比較BOCMT與CMT的request傳遞成功率
(4a)比較BOCMT與CMT的package傳遞成功率
(4a)比較BOCMT與CMT的生產效能Throughput
(4a)比較BOCMT與CMT的Bandwidth utilization
圖4.模擬分析效能的結果比較
表2. BOCMT與CMT樹狀架構特徵值
|
|
BOCMT_P(T,C)
|
CMT_P(T,C)
|
|
100
|
`
|
6 , 11
|
|
200
|
6 , 15
|
|
|
300
|
7 , 12
|
|
|
400
|
7 , 9
|
|
|
500
|
8 , 8
|
|
|
600
|
7 , 11
|
|
|
|
7 , 12
|
|
|
800
|
7 , 9
|
|
|
900
|
7 , 15
|
|
|
1000
|
7 , 10
|
|
|
1100
|
8 , 9
|
|
|
1200
|
7 , 17
|
|
|
1300
|
7 , 10
|
|
|
1400
|
7 , 12
|
|
|
1500
|
7 , 16
|
|
|
1600
|
7 , 19
|
|
|
1700
|
8 , 10
|
|
|
1800
|
6 , 14
|
|
|
1900
|
7 , 8
|
|
|
2000
|
8 , 10
|
l 結論
IEEE802.15.4是一個無線個人區域網路組織的重要標準，它提供了低功耗、低速率、低成本的LR-WPAN組織方式，以應用於智慧感測生活技術的改善與服務!
然而，由於IEEE 802.15.4標準所提供的基本拓樸以及其所衍生的樹狀拓樸方法並未作任何效能上的限制，導致低功耗目標尚有許多困難尚待克服與解決，這也成了今日仍有許多人研究如何改進IEEE 802.15.4效能以期建立更佳拓樸協定的原因。
在我們這次所提出的方法中，我們在CMT拓樸方法上加入限制樹狀高度(T_Max)與子節點最大數(Cm)的特性，並且在模擬過程中，確定這項新做法增加了CMT樹的效能，至於T_Max與Cm的最佳範圍則是直覺採用CT結構基本所需要的範圍值來作為最佳特徵限制參數，雖然已在我們實驗中證實採用T_Max=8與Cm=15可以產生不錯的效能，但是否已達最佳化或許仍不一定。
所以我們可以發現在我們提出的拓樸方法中，已為ZigBee網路架構提出新的一項限制性架構的做法，也證實可以透過限制樹狀結構的方式來加強效能，所以我們提出此方法為ZigBee提供更為有效率的網路組織架構，讓當網路節點分佈不均的時候仍然可以透過對CT架構的限制來組織有效率的ZigBee網路。
l 參考文獻
[1]F. Cuomoa , and S. Della Lunaa , and E. Cipollonea , and P. Todorovab , and T. Suihkoc , Topology formation in IEEE 802.15.4: cluster-tree characterization , Sixth Annual IEEE International Conference on Perva
全站熱搜
留言列表
