無線傳感器網絡拓撲控制

無線傳感器網絡

拓撲控制拓撲控制技術概述什么是拓撲拓撲學(topology)是研究幾何圖形或空間在連續(xù)改變形狀后還能保持不變的一些性質的學科。它只考慮物體間的位置關系而不考慮它們的形狀和大小。WSN的拓撲控制WSN中的拓撲不僅考慮節(jié)點的位置，還包括了節(jié)點的狀態(tài)以及節(jié)點間的鏈路WSN拓撲控制(TopologyControl)

：節(jié)點活動狀態(tài)的管理和調度；節(jié)點發(fā)射功率和調度計劃的控制；節(jié)點通信覆蓋范圍和節(jié)點連通性的控制WSN拓撲控制的研究方向：功率控制；節(jié)點活動狀態(tài)調度拓撲控制技術概述通信半徑感知半徑節(jié)點密度覆蓋范圍連通度發(fā)射功率拓撲控制技術概述路由層拓撲管理/控制MAC層向上提供信息向上提供信息觸發(fā)算法運行觸發(fā)算法運行拓撲控制技術概述拓撲控制的最終目的高效利用網絡能量，減少節(jié)點間干擾，延長網絡壽命網絡部署減少能量消耗優(yōu)化網絡部署目標功率控制活動調度節(jié)點活動管理聚簇管理輔助路由協議目標目標目標網絡部署網絡部署使每個節(jié)點充分發(fā)揮作用，保證數據準確獲取和收集決定網絡的覆蓋范圍和連通性節(jié)點可靠性模型主要思想：節(jié)點的可靠性是節(jié)點在網絡中處于活動狀態(tài)的概率；對于給定的能耗預算，可以估計滿足系統可靠性的最小節(jié)點可靠性。連通性與覆蓋范圍無直接關系節(jié)點數量：節(jié)點增多，維持連通性和覆蓋范圍所花費的總能耗下降節(jié)點忙閑比和冗余度對部署也有影響：密度上升，忙閑比可下調。超過某一閾值后，增加節(jié)點冗余度對于降低忙閑比無效果功率控制功率控制對節(jié)點發(fā)射功率進行靜態(tài)設置或動態(tài)調整在保證網絡連通性基礎上，調整鄰居節(jié)點數，降低節(jié)點能耗，延長網絡壽命維持必要的連通性在此前提下降低節(jié)點傳輸功率目標盡可能短的路徑網絡中平均一跳的實際傳輸距離縮短目標支持分布式操作有好的擴展性以便支持大規(guī)模網絡目標基于節(jié)點度的方法功率控制什么是節(jié)點度節(jié)點度是指距離節(jié)點一跳范圍內的鄰居節(jié)點數目?；诠?jié)點度的功率控制方法旨在通過尋找節(jié)點的最佳發(fā)射功率，在不影響網絡連通性的前提下，減少能量消耗，延長網絡壽命?；诠?jié)點度的方法功率控制本地平均算法(LMA)初始狀態(tài)下，各節(jié)點發(fā)射功率相同，定期廣播自己的生命周期消息(LifeMsg)節(jié)點收到其他節(jié)點的LifeMsg后，發(fā)送確認消息LifeAckMsg進行應答；發(fā)送節(jié)點可以根據收到的LifeAckMsg數量判斷自己的鄰居節(jié)點數量nr

節(jié)點根據自己的鄰居節(jié)點數量判斷是否需要改變發(fā)射功率：若鄰居節(jié)點數nr

大于最大值nmax

，則降低發(fā)射功率；若鄰居節(jié)點數nr

小于最小值nmin

，則提高發(fā)射功率；若nr

介于nmin

和nmax

之間，則不調整發(fā)射功率基于節(jié)點度的方法功率控制本地鄰居平均算法(LMN)初始狀態(tài)下，各節(jié)點發(fā)射功率相同，定期廣播自己的生命周期消息(LifeMsg)節(jié)點將自己的實際鄰居數放在LifeAckMsg中發(fā)送出去，發(fā)送LifeMsg消息的節(jié)點收到所有鄰居的LifeAckMsg回復，計算出鄰居節(jié)點的平均值作為自己的平均鄰居節(jié)點數節(jié)點根據自己的鄰居節(jié)點數量判斷是否需要改變發(fā)射功率基于鄰近圖的方法功率控制鄰近圖方法思想基本思想：設所有節(jié)點都使用最大發(fā)射功率發(fā)射時形成的拓撲圖G(即UDG)，按照一定的鄰居判別條件q求出該圖的鄰近圖(即特殊生成子圖)G‘，最后G’中的每個節(jié)點以自己所鄰近的最遠通信節(jié)點來確定發(fā)射功率。主要算法包括RNG、MST、LMST等LMST算法：每個節(jié)點構建各自的局部最小生成樹，將這些局部最小生成樹合并為一張新圖。LMST優(yōu)勢：與UDG相比降低了能耗，包含的鏈路更少，降低了網絡中的干擾，提升了效能?；卩徑鼒D的方法功率控制其他方法功率控制CONREAP方法思想基本思想：采用了基于機會的方法并考慮了無線通信范圍內的“過渡區(qū)域”；處于過渡區(qū)域的節(jié)點既不是完全連通的也不是完全斷開的，這些節(jié)點可能成功接收一部分數據，下次發(fā)送的數據可能無法正確接收。算法引入網絡的可達性參數，當參數高于某一閾值時，網絡的能耗最小。過渡區(qū)域：某些區(qū)域內的節(jié)點雖在圓心節(jié)點的通信半徑內，但由于信號衰減等原因，造成通信質量不佳，此區(qū)域及過渡區(qū)域。目的：減少重復路由造成的節(jié)點能量快速衰減?；顒诱{度活動調度通過控制節(jié)點活動和睡眠狀態(tài)的切換來滿足節(jié)能等需求“狀態(tài)切換”指在維持連通度前提下，關閉冗余節(jié)點，留下部分可以滿足網絡需求的節(jié)點工作節(jié)點的關閉或休眠只針對節(jié)點的無線收發(fā)模塊，節(jié)點處于這兩種狀態(tài)時，其傳感器等其他部件還可以工作所處位置一般位于MAC層和網絡層之間，與路由協議關系密切地理自適應保真算法(GAF)

依據節(jié)點地理位置信息選擇骨干節(jié)點，節(jié)點必須知道自己的地理位置。GAF算法在每個網格內維持一個骨干節(jié)點，保證網絡連通性，讓其他節(jié)點進入睡眠狀態(tài)減少能耗發(fā)現狀態(tài)：節(jié)點與鄰居交換“鄰居發(fā)現消息”，包括節(jié)點ID、網格ID、預估節(jié)點活動時間和節(jié)點狀態(tài)活動狀態(tài)：節(jié)點參與路由活動，處理網格內通信活動，每一網格內只有一個節(jié)點處于活動狀態(tài)睡眠狀態(tài)：除活動節(jié)點外，其他節(jié)點均關閉無線傳輸模塊狀態(tài)切換：若收到更高級別“鄰居發(fā)現消息(預估活動時間)”，則節(jié)點進入睡眠狀態(tài)，工作任務轉移，活動調度基于連通度的方法活動調度基于連通度的方法GAF算法實際是一種基于地理位置信息的分簇算法，每個網格內的節(jié)點自動成簇，活動節(jié)點即為簇頭優(yōu)勢根據單元格的大小，可以最大限度使大部分節(jié)點睡眠，節(jié)省能耗劣勢成簇條件苛刻載荷分配不均衡，匯聚節(jié)點附近的單元格能耗消耗大自適應自配置傳感器網絡拓撲(ASCENT)

通過節(jié)點的本地“測量”來進行活動調度，保障網絡連通性。ASCENT算法使用分布式調度機制，保留骨干節(jié)點，其余節(jié)點睡眠探測狀態(tài)(Test)：節(jié)點與鄰居交換“控制信息”，計算周圍主動活動鄰居數主動活動狀態(tài)：可收發(fā)、路由數據被動活動狀態(tài)：不關閉無線通信，不參與通信，偵聽當前流量，搜集網絡狀態(tài)和鄰居數據丟失率睡眠切換：除活動節(jié)點外，其他節(jié)點均關閉無線傳輸模塊活動調度基于連通度的方法活動調度基于連通度的方法ASCENT節(jié)點狀態(tài)轉換方式：節(jié)點發(fā)現丟包嚴重，即向源節(jié)點方向發(fā)送求助消息節(jié)點探測到鄰居丟包嚴重或收到求助消息時，則進入主動活動狀態(tài)，參與網絡通信活動調度基于連通度的方法ASCENT算法基本思想是節(jié)點自適應決定自己的狀態(tài)，對節(jié)點的計算要求相對較高優(yōu)勢節(jié)點可以自適應地根據本地狀態(tài)改變自身狀態(tài)，從而動態(tài)改變網絡拓撲形態(tài)劣勢節(jié)點在自適應狀態(tài)轉換過程中計算、能耗開銷均高于GAF算法；節(jié)點偵測也有通信開銷活動調度基于網絡容量的方法SPAN算法也采用了分布式骨干節(jié)點選舉機制SPAN算法中節(jié)點與鄰居定期交換控制信息(即HELLO消息)HELLO消息內容：節(jié)點狀態(tài)(是否為骨干節(jié)點)、連接到的骨干節(jié)點列表、節(jié)點的鄰居每個節(jié)點通過HELLO消息都知道自己周圍的骨干節(jié)點，能在需要時決定自己是否成為骨干節(jié)點；消息內容也供路由協議使用，以便在骨干節(jié)點中選擇中繼節(jié)點活動調度基于網絡容量的方法SPAN算法中普通節(jié)點可以轉換為骨干節(jié)點，骨干節(jié)點也可以轉換為普通節(jié)點。成為骨干節(jié)點：如果節(jié)點發(fā)現有超過兩個鄰居節(jié)點不能通信，則有資格成為骨干節(jié)點；為防止過多節(jié)點成為骨干節(jié)點，SPAN算法有退避機制，由節(jié)點效用和剩余能量決定骨干節(jié)點停職：骨干節(jié)點檢查鄰居節(jié)點狀態(tài)，如每個鄰居都可通過其他的骨干節(jié)點進行通信，則該骨干節(jié)點停止當前職責，成為普通節(jié)點活動調度SPAN算法在保證了網絡連通性的同時也保證了一定的網絡容量優(yōu)勢延長了網絡壽命提高了網絡的健壯度，如鏈路故障，有其他鏈路替代劣勢增加了消息傳輸的跳數和時延增加了控制消息的交換以及通信開銷基于網絡容量的方法活動調度STEM協議稀疏拓撲與能量管理(STEM)協議屬于非層次型的節(jié)點喚醒調度算法。STEM協議中網絡無需始終維持連通性，通常情況下節(jié)點處于監(jiān)視狀態(tài)，在事件發(fā)生后，網絡產生突發(fā)流量，快速喚醒整個網絡，恢復連通性，傳輸數據。STEM協議采用雙無線收發(fā)機模式：一個收發(fā)機用于調度和信道偵聽；另一個用于實際數據通信。兩個收發(fā)機采用不同信道，彼此互不干擾活動調度STEM協議WSN網絡無實際數據通信節(jié)點關閉第二無線收發(fā)機以節(jié)省能量定期打開第一收發(fā)機偵聽網絡發(fā)生觸發(fā)事件節(jié)點第一收發(fā)機偵聽到網絡傳輸信號喚醒第二收發(fā)機，傳輸數據活動調度STEM協議STEM協議可以與GAF等算法相結合，利用各自優(yōu)勢，進一步調整網絡能量消耗優(yōu)勢節(jié)省能量，延長了網絡壽命適用于低速、基于事件的網絡應用場景劣勢節(jié)點花費大量時間進行偵聽不適用于監(jiān)控型網絡，節(jié)能效果不明顯聚簇管理使用分簇形式的優(yōu)勢擴展性好限制了一般節(jié)點到匯聚節(jié)點的傳輸跳數，支持大規(guī)模網絡高效能簇頭保持活動狀態(tài)，其他節(jié)點可睡眠；簇頭可動態(tài)選舉均衡能耗減少碰撞幾率節(jié)點簇內管理，數據簇內傳輸獲取更多局部信息通過和簇頭節(jié)點交換信息混合能效分布式(HEED)分簇算法在分簇時考慮了節(jié)點剩余能量與簇內通信成本，將節(jié)點劃分為多個一跳的簇。HEED產生背景：HEED是在LEACH算法簇頭分布不均勻這一問題基礎上而作出對LEACH協議分簇算法的改進，它以簇內平均可達能量(AMRP)作為衡量簇內通信成本的標準。HEED算法的實質：在LEACH算法基礎上，重點修改了選舉簇頭的算法。在全網時間同步的基礎上,將節(jié)點根據當前剩余能量占初始能量的比例p劃分為若干“等級”，等級較高的節(jié)點率先公布自己為簇頭，而等級較低的節(jié)點在收到簇頭廣播后加入這個簇。如果節(jié)點的剩余能量降為初始能量的1%就被除去競選簇頭的資格。聚簇管理HEED算法聚簇管理HEED算法主要改進在簇頭選擇中考慮了節(jié)點的剩余能量,并以主從關系引入多個約束條件。實結果