无线感测网中无需地资讯之低成本坚韧由

無線感測網路中無需地理資訊之低成本堅韌路由Low-CostResilientRoutingwithoutGeographicInformationinWirelessSensorNetworks吳亦超段裘慶顏嘉鋒Y.-C.WuC.-C.TuanC.-F.Yen國立台北科技大學電腦與通訊研究所[e-mail]@[e-mail]摘要微型無線感測節點受限於供應電量、運算與儲存能力以及網路通信頻寛。感測節點常需以感測資料併同節點位置資訊做為相對處理。然而位置的取得雖可透過全球定位系統，但感測節點上若攜帶定位系統，其硬體成本的提升與電量的消耗，都不符合小體積與低成本的設定。本研究提出LCRR(低成本堅韌路由協定)。可透過虛擬座標系統的建置，於資料回傳時記錄各節點資訊，以達到事件定位之效果。訊息傳遞由外圍節點向內圍節點轉送，藉由多路徑選擇來分散負載，增加路徑的強健性。虛擬座標的路由維護因易於一般路由，可降低網路維護的成本。關鍵詞：無線感測網路、虛擬座標、堅韌路由、幹道、事件定位。一、簡介無線感測網路(WirelessSensorNetworks,WSN)是一種無基礎建設之網路架構，由部署在監測地區內的大量微型感測節點(SensorNode,SN)所組成，透過無線通訊的方式形成無線網路系統。常見應用於環境監控、醫療照護、居家保全、交通監視以及軍事偵測等方面上，而其應用的多樣性，近年來也受到廣泛的討論。微型的SN，在硬體上有許多限制：感測器電源由有限電池電能供給、通信受限於較低的傳送速率與距離、處理器的計算能力與儲存空間有限。有鑒於上述特性，如何有效利用有限的硬體資源尚能持久得使網路正常運作，為目前無線感測網路的研究目標之一。由於SN通常大量部署於廣大的監測地區，往往是高山險境惡劣氣候，非人力所及之處，須搭乘飛行載具，在感測區域上空灑下大量感測節點，隨機佈署於感測環境。由於節點需大量使用，對於感測節點的成本就得要求低廉。當狀況發生回傳訊息時，若無法得知所傳資料是由感測區內何處傳回時，則所得資訊變得沒有價值和意義。一般而言，若為人工佈署SN，則節點所在位置可於佈署時得知；反之，若為非人工部署，則SN的位置可透過全球定位系統(GlobalPositioningSystem,GPS)獲得。然而，不論是人為佈署或是透過GPS來得知地理資訊，都將花費大量的建置成本。若感測節點攜帶GPS情況下，學者提出GAF[8]與GHT[6]路由協定，以不同的路由架構來節能，使網路能延長運作的壽命。或是利用節點休眠機制令SN作最有效的發揮，但資料收集端周圍的轉送節點，還是得轉送其它遠處所傳的封包，往往不能藉由休眠來延長存活時間。因此如何降低因為地理資訊所付出的成本，將是WSN發展的要點之一。在WSN不需人工部署且不用具地理1資訊的SN，並使用有限的運算能力及儲存空間之條件下，本研究提出無需地理資訊之低成本堅韌路由機制(Low-CostResilientRouting,LCRR)。此路由協定包含網路拓樸的初始建立，封包訊息的傳送方法，路徑的維護，到套用事件定位的機制。透過本LCRR路由協定，除了減少能量的消耗外，更不需要使用GPS等高成本的硬體來獲取地理資訊。二、相關文獻探討地理位置路由GEM(GeographyEMbedding)[4]、GHT[6]與GAF[8]，皆提出透過虛擬極座標或是網格的地理路由法，但訊息最終還是得傳送至資料收集端。如此，資料收集端周圍的節點往往需轉送比其它節點更多的封包，而造成SN能量的快速消耗，以致於形成網洞[7]。假使資料收集端周圍節點失效，將使得感測訊息無法傳達至後端作處理，有效的解決方式可在資料收集端周圍部署較多的SN來分散周圍節點的轉傳負載。[1](Node-link-failureresilientrouting)提到資料收集端周圍的Criticalnodes若失效，可能迫使整個網路失去作用。如圖1所示，節點以網格方式作佈署，左下角為閘道節點或稱資料收集端，其周圍節點負載。而在傳輸資料方面，採用輪流傳送方式，網路中每一節點只能往下或往左轉傳，藉以分散網路負載於下游各節點。1,12,11,2n,1i,jn,k1,k：nodeati-throw,j-thcolumni,jGatewayInternet圖1網格中利用輪替轉送分散負載而GEM[4]與DV-Hop[5]根據節點至資料收集端的跳躍數(hop)來估算SN與Sink的距離。GEM[4]建立一虛擬極座標系統(VirtualPolarCoordinateSpace,VPCS)來建構網路拓撲，進而發展出與樹狀結構相似的虛擬極座標路由，以Sink為樹幹父節點擴散至網路各子節點，同時利用hop數與自定義的虛擬角度來作節點定位。訊息傳遞上，父節點擁有的角度包含子節點所有角度，而訊息由子節點傳送至該父節點。DV-Hop[5]建立網路拓撲是由資料收集端開始，向周圍廣播封包尋找路徑，凡節點距離資料收集端為一個hop數稱做第一層，距離資料收集端兩個hop數則為第二層，由此方法擴張至整個感測區域各個節點，則每一節點都可得知自己與資料收集端距離多少hop數，再利用三邊測量法(trilateration)來作網路節點的定位。在定位技術的路由法中(AdhocPositioningSystem,APS)[3]，指出GPS雖為目前應用最廣泛最成熟的定位系統，但對於低成本的WSN而言，卻顯得不適用。而利用少數具有仿似GPS定位系統的信標節點(beaconnode)，來節省成本，再套用定位演算法來達到SN定位。以上所述之GEM[4]、DV-Hop[5]與APS[3]皆為求SN成本考量，而不使用GPS模組。而本研究的目標與其相同，擬出一套定位機制，盡可能降低計算與儲存量，同時可節能，亦可成為一強健的路由。三、LCRR路由協定低成本堅韌路由LCRR適用於大量部署感測節點的無人廣大監測區域，或是人們難以到達的嚴酷惡劣環境，利用高空灑下大量感測節點，隨機佈署於感測環境。當有事件被偵測到時，感測訊息由外圍節點轉送至內圍節點，再到資料彙集端處理。資料在轉送時，則經由多路徑傳送。訊息回傳時，透過虛擬座標系統，記錄所經過的節點，由資料彙集端分析，即2可達到事件定位的效果。LCRR路由協定主要的相關環境設定如下：1.感測區域內節點部署為隨機且均勻的分佈。2.每個節點皆無GPS或其他定位系統以獲知本身的地理位置資訊。3.節點皆為靜止無移動性，感測半徑為傳輸半徑的一半。4.每一節點有各自的路由表，其記錄內圍節點，以供選擇下一傳遞點。5.節點間具雙向通訊鏈結，且傳輸半徑固定不變。6.資料彙集端沒有電量限制。7.感測節點具有下列欄位資訊，見表1。表1：感測節點記錄欄位3.1虛擬座標系統之建構在虛擬座標系統的建置上，LCRR路由協定的建構方法與DV-Hop[5]、GEM[4]相似，皆由資料彙集端向鄰居節點廣播路徑請求，進而擴張至整個感測區域，計算網路中各節點與資料彙集端的跳躍數，同時給予各節點虛擬座標值。3.1.1階層數之設定首先，由資料彙集端先設定自身hop數為0，再向周圍鄰居節點廣播路徑請求封包，距離資料彙集端為一個hop數的鄰居節點，在自己的Level欄位註記為1(Level1)。Level1節點在回傳路徑回覆的同時，Sink端也可藉此得知Level1的節點總數。Level1節點也以同樣方式向周圍廣播路徑請求，即可找到Level2節點。同樣地，尚未註記Level之節點在接收到路徑請求封包後，若經查封包內的Level數為i，則註記自己的Level為i+1，以此方式擴展至整個感測區域，則以跳躍為基礎的階層式網路拓撲形成。而當已設定Level數為i之節點，若接收到封包內Level數為j之重複路徑請求時，以下列三種狀態與方法處理：a.j+1i：捨棄該封包，不予理會。b.j+1=i：記錄於路由表，增加內圍節點的傳遞選擇。c.j+1i：修改自身Level數為j+1。3.1.2幹道與分支之建立在3.1.1中，Sink端得知Level1的總節點數，同時也為總幹道數。每一個Level1之節點皆為幹道節點，其欄位記錄為：Level=1；Trunk=k；Branch=0；CrossTrunk=X，簡寫成：1-k-0-X。記錄節點各欄位資訊與階層數設定是同時填入的。換言之，在尋找外圍節點的同時，階層數的設定、幹道、分支與相交幹道也同時完成。其它欄位則作以下設定：a.幹道節點(Branch=0)有能力選擇外圍節點為下一層幹道節點(設定下一層外圍節點的各欄位值)；而Branch≠0之節點只能給予Level值。b.為確保幹道延伸性，在選擇外圍的下一層幹道節點時，以最慢回傳路徑回覆者為幹道節點。在設定外圍節點各欄位時，需保留Branch(=0)欄位之設定。c.為能更準確定位出事件發生的所在地區，避免幹道相交的情形出現。被指定為幹道之節點，不可重複接受其它內圍幹道節點之請求；且身為幹道之節點，須令其鄰居節點不可為幹道節點。d.幹道節點有賦予外圍幹道節點的能力，所以需對外圍幹道節點週期性的維護；若外圍幹道節點失效，則從外圍節點再次選出，而對於內圍幹道節點則不3需去維護。欄位設定的步驟，如圖2所示：Step1.圖2(a)所示虛線為節點間存在通訊連結的情形。Step2.圖2(b)所示Level1已完成連結，各欄位也設定成功。Step3.圖2(c)所示Level2完成連結，粗黑線為幹道線。Trunk欄位為第一次接收到路徑請求封包的幹道；CrossTrunk為第二次所接到的封包。Step4.圖2(d)所示Level3可知LCRR路由協定的欄位設定規則。幹道節點其Branch欄位為“0”，且有設定下一層外圍節點各欄位的權力。在未與幹道節點相臨的節點(Level3最左邊兩個)，所能得知的資訊只有自己所在階層數，故表為3-X-X-X。圖2(a)WSN初始狀態圖2(b)Level1節點設定圖2(c)Level2節點設定SinkLevel1Level2Level3Level01-1-0-X1-2-0-X1-3-0-X2-1-0-X2-1-1-X2-2-0-12-3-1-X2-3-0-X2-3-2-23-1-1-X3-1-0-X3-1-2-23-2-0-X3-X-X-X3-3-1-X3-3-0-X圖2(d)Level3節點設定3.2訊息回傳方法訊息回傳原則為外圍節點朝內圍節點轉送(highLevel→lowLevel)。待傳送封包之節點，只須將資料封包傳送至Level數比自身還小的內圍節點即可，並無特定路徑，不需另交給幹道節點轉送，避免幹道額外耗費能量。內圍節點的選擇，則以隨機選擇或是輪流傳遞等轉送機制。若可得知節點之剩餘電量，則可依據內圍節點的電量多寡作傳遞的選擇；或若節點間距離可獲知，也可選擇較近的節點為傳送目標。當有事件發生時，來源節點將會傳送事件封包，同時也註記自身的欄位資料予事件封包內，封包傳遞時所經過的各節點欄位資料，皆記錄於回傳封包內，當封包成功傳送至資料彙集端時，即可作分析判4讀。3.3事件定位判讀藉由虛擬座標系統的建置與回傳事件封包所提供的訊息，將可解析事件發生的所在地區。資料彙集端可先由Level欄位判別此事件發生地點與資料彙集端相距的hop數，得知距離；再由其它欄位預估來源節點與資料彙集端的相對方向。事件定位判別時，以Level最高的欄位訊息為第一優先分析依據，再依Level由高至低作判別。也可統計所經幹道的次數，做為事件方位的預估。對於所回傳的Level1節點方向，資料彙集端可藉由多個超音波接收器或是天線陣列，找出Level1節點相對於Sink的方位。如圖3(a)所示當回傳封包成功傳送至資料彙集端，可得到的資訊如下：1.3-1-2-2：為Level3之訊息，距離資料彙集端為3個hop數，且位於在幹道1與2之間。2.2-2-0-1：經過Level2的幹道節點，此發生地區較接近幹道2，且所經此節點與幹道1的Level1節點只有一個hop數。3.1-1-0-X：綜合以上可