無線傳感網(wǎng)絡(luò)

–幾種典型拓撲控制策略

LeachTopdiscGAFASCENTMOTIVATIONFORTOPOLOGYCONTROLHighpowerHighinterferenceLowThroughputNetworkmaypartitionExampleofNoTopologyControlwithsmallertransmissionradiusMOTIVATIONFORTOPOLOGYCONTROLLowpowerLowinterferenceHighThroughputGlobalConnectivityBiggerPictureandRelatedWorkRoutingMAC/Power-controlledMACSelectiveNodeShutdownTopologyControlRelativeNeighborhoodGraphs,Gabrielgraphs,Sphere-of-Influencegraphs,-graphs,etc.[GAF][Span][Hu1993][Ramanathan&Rosales-Hain2000][Rodoplu&Meng1999][Wattenhoferetal.2001]ComputationalGeometry[MBH01][WTS00]拓撲控制的概念與意義概念 拓撲控制（topologycontrol）是一種協(xié)調(diào)節(jié)點間各自傳輸范圍的技術(shù)，用以構(gòu)建具有某些期望的全局特性（如，連通性）的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，同時減少節(jié)點的能耗或增加網(wǎng)絡(luò)的傳輸能力。意義 1、減少節(jié)點的通信負載，提高通信效率； 2、減少網(wǎng)絡(luò)耗能，延長網(wǎng)絡(luò)壽命； 3、輔助路由協(xié)議；拓撲控制的分類覆蓋控制拓撲控制的研究方向WSN中拓撲控制可以分為兩個研究方向：功率控制和層次拓撲結(jié)構(gòu)控制。功率控制機制調(diào)整網(wǎng)絡(luò)中每個節(jié)點的發(fā)射功率，保證網(wǎng)絡(luò)連通，在均衡節(jié)點中直接鄰居數(shù)目(單跳可達鄰居數(shù)目)的同時，降低節(jié)點之間的通信干擾。層次拓撲控制是利用分簇思想，使網(wǎng)絡(luò)中的部分節(jié)點處于激活狀態(tài)，成為簇頭節(jié)點。由這些簇頭節(jié)點構(gòu)建一個連通的網(wǎng)絡(luò)來處理和傳輸網(wǎng)絡(luò)中的數(shù)據(jù)，并定期或不定期地重新選擇簇頭節(jié)點，以均衡網(wǎng)絡(luò)中節(jié)點的能量消耗。拓撲控制與網(wǎng)絡(luò)體系的關(guān)系思考一個問題？拓撲控制是否一個單獨的技術(shù)？它與網(wǎng)絡(luò)層等有沒有聯(lián)系？網(wǎng)絡(luò)層：提供的兩個相鄰端點之間的數(shù)據(jù)幀的傳送功能上，進一步管理網(wǎng)絡(luò)中的數(shù)據(jù)通信，將數(shù)據(jù)設(shè)法從源端經(jīng)過若直干個中間節(jié)點傳送到目的端，從而向傳輸層提供最基本的端到端的數(shù)據(jù)傳送服務(wù)。具體功能包括尋址和路由選擇、連接的建立、保持和終止等。拓撲控制的評價指標(biāo)連通性在沒有拓撲算法前，兩個節(jié)點之間存在k條路徑，那么使用拓撲算法后，這兩個節(jié)點中也應(yīng)該有存在k條路徑。覆蓋性 覆蓋問題中，最重要的因素是網(wǎng)絡(luò)對物理世界的感知能力。吞吐量

化簡后的網(wǎng)絡(luò)拓撲結(jié)構(gòu)應(yīng)該能夠支持與原始網(wǎng)絡(luò)相似的通信量。擴展性（網(wǎng)絡(luò)容量）

減少數(shù)據(jù)傳輸節(jié)點所能影響的鄰居節(jié)點的數(shù)量,減少節(jié)點通信的傳輸范圍,可以有效減小網(wǎng)絡(luò)中的沖突域,從而降低通信沖突的概率。相反，網(wǎng)絡(luò)中的沖突就越多,節(jié)點通信也就更容易發(fā)生數(shù)據(jù)丟包或重傳現(xiàn)象。魯棒性

網(wǎng)絡(luò)發(fā)生變化時，一些節(jié)點可能會變化它們的拓撲信息，顯然，魯棒的拓撲結(jié)構(gòu)只需要進行少量的調(diào)整，這樣可以避免對本地節(jié)點的重新組織而造成整個網(wǎng)絡(luò)的波動。實現(xiàn)拓撲控制的手段1、在保證網(wǎng)絡(luò)的連通性與覆蓋性的情況下，控制節(jié)點的發(fā)射距離，減少發(fā)射功耗，同時減少分組沖突的可能性，減少協(xié)議不必要的開銷；2、盡可能讓多的節(jié)點進行休眠，降低功耗；3、數(shù)據(jù)融合，減少分組的冗余。單跳還是多跳耗能多？拓撲控制的表現(xiàn)1、網(wǎng)絡(luò)壽命：盡量降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存周期；2、減小節(jié)點通信負載，提高通信效率：傳感器節(jié)點分布密度一般比較大，通過拓撲控制技術(shù)中的功率控制技術(shù)可以通過選擇節(jié)點的發(fā)射功率合理調(diào)整節(jié)點的通信范圍，使得節(jié)點在連通性與覆蓋性得到一個平衡點。3、輔助路由協(xié)議：只有活動的節(jié)點才能進行數(shù)據(jù)轉(zhuǎn)發(fā)，而拓撲控制可以確定由哪些節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，同時確定節(jié)點之間的鄰居關(guān)系。4、數(shù)據(jù)融合策略的選擇；5、節(jié)點冗余：由于傳感器節(jié)點本身固有的脆弱性不能保證節(jié)點一直持續(xù)正常工作。拓撲控制的應(yīng)用效果拓撲控制的分類拓撲控制的分類1、概述與算法2、適用環(huán)境3、優(yōu)缺點4、實際應(yīng)用的問題5、協(xié)議改進突破口如何學(xué)習(xí)與理解一個協(xié)議？基于位置的拓撲控制算法-鄰近圖基本思想設(shè)所有節(jié)點都使用最大發(fā)射功率發(fā)射時形成的拓撲圖G，按照一定的鄰居判別條件q求出該圖的鄰近圖G'，最后G'中的每個節(jié)點以自己所鄰近的最遠通信節(jié)點來確定發(fā)射功率。經(jīng)典的鄰近圖算法RNG、GG、DG、YG、MST、DRNG、DLMST、DLSSDRNG與DLSS算法第一步:每個節(jié)點以最大的發(fā)射功率廣播HELLO信息，該信息至少包括：節(jié)點ID號、最大的發(fā)射功率、自身的位置。節(jié)點在收到HELLO信息后，確定了自己可以達到的鄰居集合。第二步：DRNG與DLSS以各自的鄰居算法確定鄰居集合，DRNG以與它節(jié)點最近的鄰居節(jié)點選擇優(yōu)先；而DLSS最小化了圖中所有邊的最大能量消耗,并取單跳距離的節(jié)點作為其鄰居節(jié)點。第三步確定鄰居節(jié)點后，將發(fā)射半徑調(diào)整到最遠鄰居節(jié)點的距離，進一步通過對拓撲圖的邊進行增刪，使網(wǎng)絡(luò)達到雙向連通。鄰近圖算法仿真結(jié)果對比基于鄰居的拓撲控制算法基于節(jié)點度數(shù)（鄰居）的算法LMA、LMN、LINT、LILTLMA(localmeanalgorithm)--本地平均算法

給定節(jié)點度的上限和下限,動態(tài)地調(diào)整節(jié)點發(fā)射功率,使節(jié)點的度數(shù)始終維持在度數(shù)的上限和下限之間.這種算法利用局部信息來調(diào)整相鄰節(jié)點的連通性,從而在保證網(wǎng)絡(luò)連通的同時使得節(jié)點間的鏈路具有一定的冗余性和擴展性。LMN(localmeanofneighborsalgorithm)--本地鄰居平均算法 與LMA不一樣的地方是，LMN的鄰居節(jié)點的數(shù)目依據(jù)于所有鄰居的鄰居節(jié)點數(shù)求平均值作為自己的鄰居節(jié)點數(shù)。仿真結(jié)果顯示,這種策略在保證網(wǎng)絡(luò)連通的同時,通過少量的局部信息使網(wǎng)絡(luò)性能達到了一定程度的優(yōu)化.但是,這兩種算法缺乏嚴(yán)格的理論推導(dǎo).層次型拓撲結(jié)構(gòu)控制層次型拓撲結(jié)構(gòu)產(chǎn)生背景傳感器節(jié)點在無線通信模塊在空閑狀態(tài)與收發(fā)狀態(tài)下的能耗相當(dāng)，因此只有關(guān)閉其節(jié)點的無線通信模塊才能真正有效的降低非工作能耗。層次分簇就是在這一背景下產(chǎn)生的。層次型拓撲控制的思想與關(guān)鍵技術(shù)關(guān)鍵技術(shù)層次分簇算法的核心是如何選擇簇頭集合，并把剩余的節(jié)點劃分到已經(jīng)產(chǎn)生簇頭集合中。分簇的基本思想通過簇首對簇內(nèi)節(jié)點間的相關(guān)信息融合及轉(zhuǎn)發(fā)機制減少數(shù)據(jù)的傳輸量和距離,進而降低通信能量,達到網(wǎng)絡(luò)節(jié)能的目的。WSN中不同拓撲下的數(shù)據(jù)傳輸方式LEACHLEACH不是一個單純的路由協(xié)議

，它提供了一個包括分群、路由、MAC和物理層的完整的無線傳感網(wǎng)絡(luò)的協(xié)議框架，也可以說是一個分層路由的體系結(jié)構(gòu)。

LEACH協(xié)議是眾多分層協(xié)議參考的模型，稱為經(jīng)典。LEACHLEACHLEACH概述

LEACH算法是一種分布式、自組織的分簇協(xié)議。運行LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)會隨機選擇一些節(jié)點成為簇頭，并令所有節(jié)點周期性地輪換成為簇頭，使整個網(wǎng)絡(luò)的能量負載達到均衡。

在LEACH協(xié)議中，簇頭節(jié)點將來自其成員節(jié)點的數(shù)據(jù)進行壓縮聚合，然后將聚合后的數(shù)據(jù)通過單跳的方式直接發(fā)送給基站節(jié)點，大大減小了整個網(wǎng)絡(luò)中的數(shù)據(jù)交換量，使得總體能耗有了大幅度的下降。LEACH算法的假設(shè)

基站是固定的而且遠離傳感器節(jié)點

網(wǎng)絡(luò)中的傳感器節(jié)點都是同型傳感器節(jié)點而且能量受限的

每個節(jié)點都有能力和基站通信

節(jié)點沒有位置信息

對稱二進制信道

簇首可以進行數(shù)據(jù)融合LEACH工作流程簇頭選擇算法1、確定最優(yōu)簇頭數(shù)目；2、計算每個節(jié)點成為簇頭的概率；

相關(guān)參數(shù)：全網(wǎng)的節(jié)點數(shù)、簇頭數(shù)目、能量評估（單節(jié)點與`全網(wǎng)）、當(dāng)前的循環(huán)數(shù)。目的：確保所有節(jié)點大致在相同時刻耗盡能量而停止工作，延長網(wǎng)絡(luò)的生命周期。1、簇頭進行數(shù)據(jù)融合，減少冗余數(shù)據(jù)量；2、在MAC層中使用了TDMA、CSMA、CDMA等機制來共同處理簇內(nèi)與簇間的沖突問題；3、采用選舉簇頭算法，保證WSN能量消耗平均負載到各節(jié)點上；4、采用層次路由，路由路徑選擇比較簡單，不需要存儲很大的路

由信息。LEACH優(yōu)點LEACH缺點1、簇頭選舉隨機性很強，可能會出現(xiàn)簇頭集中在某一個區(qū)域的現(xiàn)象，造成簇頭分布不均勻。LEACH缺點2、信息的融合和傳輸都是通過簇頭節(jié)點來進行，造成了簇頭節(jié)點能量消耗過快的問題；3、發(fā)射機和接收機必須嚴(yán)格遵守時隙的要求，避免在時間上互相重疊，然而，維持時間同步又增加了一些額外的信令通信量。節(jié)點的時間表可能會需要較大的存儲器。4、LEACH要求節(jié)點之間和節(jié)點與Sink點之間都能進行直接通信，網(wǎng)絡(luò)的擴展性差，對于大規(guī)模網(wǎng)絡(luò)而言，節(jié)點直接進行通信需要消耗大量的能量。并且采用單跳路由方式，增加了交換數(shù)據(jù)的能量。LEACH適用場合LEACH適用于周期性信息報告，對延時不敏感。網(wǎng)絡(luò)布設(shè)范圍小，所有節(jié)點到sink的距離可以認為相等。實際應(yīng)用：博物館的文物保護檢測Matlab資源TOPDISC算法TopDisc（topologydiscovery）算法來源于圖論中提出的思想，是基于最小支配集問題的經(jīng)典算法。利用顏色區(qū)分節(jié)點狀態(tài)，解決骨干網(wǎng)拓撲結(jié)構(gòu)的形成問題。TOPDISC算法TopDisc算法的過程由網(wǎng)絡(luò)中的一個節(jié)點啟動發(fā)送用于發(fā)現(xiàn)鄰居節(jié)點的查詢消息（拓撲發(fā)現(xiàn)探測數(shù)據(jù)包）。隨著查詢消息在網(wǎng)絡(luò)中傳播，算法依次為每個節(jié)點標(biāo)記顏色。最后，按節(jié)點顏色區(qū)分出簇頭節(jié)點，并通過反向?qū)ふ也樵兿⒌膫鞑ヂ窂皆诖仡^節(jié)點之間建立通信鏈路。發(fā)現(xiàn)

建立傳播TOPDISC算法在三色算法中，節(jié)點可以處于三種狀態(tài)，分別用白、黑和灰三種顏色表示：白色：尚未被發(fā)現(xiàn)的節(jié)點灰色：普通節(jié)點（簇內(nèi)節(jié)點），至少被一個標(biāo)記為黑色的節(jié)點覆蓋，即黑色節(jié)點的鄰居節(jié)點。黑色：骨干節(jié)點（簇頭節(jié)點），負責(zé)響應(yīng)拓撲發(fā)現(xiàn)請求；TOPDISC算法在初始階段，所有節(jié)點都標(biāo)記為白色。acbedTOPDISC算法（1）初始節(jié)點a將自己標(biāo)記為黑色，并廣播查詢消息。acbedTOPDISC算法（2）白色節(jié)點b、c收到黑色節(jié)點a的查詢消息時變?yōu)榛疑?等待一定時間再廣播查詢消息。acbedTOPDISC算法等待時間的長度與這個白色節(jié)點到向它發(fā)出查詢消息的灰色節(jié)點的距離成反比。acbedTOPDISC算法由于節(jié)點b比節(jié)點c距離節(jié)點a更遠，所以節(jié)點b先開始發(fā)送查詢信息。acbedTOPDISC算法（3）當(dāng)白色節(jié)點收到一個灰色節(jié)點的查詢消息時，先等待一段時間。acbedTOPDISC算法等待時間的長度與這個白色節(jié)點到向它發(fā)出查詢消息的灰色節(jié)點的距離成反比。如果節(jié)點在等待時間內(nèi)，又收到來自黑色節(jié)點的查詢消息，節(jié)點立即變成灰色節(jié)點，否則,節(jié)點變?yōu)楹谏?jié)點。TOPDISC算法由于節(jié)點d比節(jié)點e距離節(jié)點b更遠，所以節(jié)點d先超時，并將自己標(biāo)記為黑色。acbedTOPDISC算法d繼續(xù)向外發(fā)送查詢消息,這時節(jié)點e收到了來自節(jié)點d的消息，變?yōu)榛疑?。acbedTOPDISC算法（4）當(dāng)節(jié)點變?yōu)楹谏蛘呋疑?，它將忽略其他?jié)點的查詢消息。acbedTOPDISC算法（5）通過反向查找查詢消息的傳播路徑形成骨干網(wǎng)，黑色節(jié)點成為簇頭，灰色節(jié)點成為簇內(nèi)節(jié)點。acbedTOPDISC算法TopDisc算法缺點：這種算法構(gòu)建成的層次型網(wǎng)絡(luò)的靈活性不強，重復(fù)執(zhí)行算法的開銷過大，且該算法沒有考慮到節(jié)點的剩余能量問題。改進：如果把剩余能量控制信息加入到TopDisc算法中，讓節(jié)點輪流地去做簇頭節(jié)點，這樣能使得網(wǎng)絡(luò)中能量的消耗更均勻，從而直接提高了網(wǎng)絡(luò)的生存周期。作業(yè)：仿真一種TOPDISC算法或改進算法GAF算法介紹GAF算法介紹GAF算法介紹試探GAF算法介紹每個單元格內(nèi)部的簇頭競選和通信過程所示，每個節(jié)點都存在睡眠、發(fā)現(xiàn)、活動三種狀態(tài)，節(jié)點在三種狀態(tài)之間轉(zhuǎn)換的具體步驟如下：a）所有節(jié)點初始化為發(fā)現(xiàn)狀態(tài)，令其state=discovery，并獲得唯一的ID號NodeID。b)每個節(jié)點根據(jù)自身相對位置信息和無線通信半徑，采用公式(3-2)確定其單元格大小，從而決定其所在的單元格號GridID。c)每個節(jié)點都與鄰近節(jié)點交換數(shù)據(jù)信息，信息結(jié)構(gòu)如圖3-3所示：預(yù)估節(jié)點活動時間GAF算法介紹其中，NodeID為本節(jié)點號；GridID為所處的單元格號；State為狀態(tài)信息，當(dāng)前值為發(fā)現(xiàn)狀態(tài)。以上信息為廣播信息，當(dāng)節(jié)點收到鄰居節(jié)點的Message信息時，不進行信息的進一步轉(zhuǎn)發(fā)。若該Message的GridID號與本節(jié)點GridID號一致，則將該Message中的NodeID號記錄在本地的單元格鄰居節(jié)點列表Table_neighber中；若不一致則直接丟棄該Message。通過Message廣播過程，保證了每個節(jié)點都可以得知同一單元格內(nèi)所有其他節(jié)點的NodeID號。預(yù)估節(jié)點活動時間可通過剩余能量計算出時間GAF算法介紹d)所有節(jié)點共同進入簇頭選擇階段：在Td時間內(nèi)，未接收到任何更高級別的試探消息，則轉(zhuǎn)入活動狀態(tài)；如果有更高級別的，則立刻轉(zhuǎn)入休眠狀態(tài)（休眠Ts時間段，之后再重新競選簇頭）?！呒墑e取決于它的狀態(tài)和預(yù)期生存期，活動狀態(tài)下的節(jié)點比試探狀態(tài)下的節(jié)點級別高；另外，更高預(yù)期生存期的比同一狀態(tài)下的預(yù)期生存期低的節(jié)點級別更高，將被選擇為骨干節(jié)點（簇頭）GAF算法介紹e)處于睡眠狀態(tài)的睡眠節(jié)點關(guān)閉所有通信和檢測功能，不進行信號的發(fā)送、接收和偵聽，在Ts秒后將重新回到試探狀態(tài)。GAF算法介紹f)簇頭節(jié)點在活動狀態(tài)將維持Ta秒，在Ta秒內(nèi)每隔1秒簇頭節(jié)點將廣播一次Message信息，保證睡眠節(jié)點即使回到發(fā)現(xiàn)狀態(tài)后，仍來不及廣播其Message信息，而被迫重新轉(zhuǎn)到睡眠狀態(tài)。Ta秒結(jié)束后簇頭節(jié)點將重新回到發(fā)現(xiàn)狀態(tài)，返回步驟d)進行新一輪的簇頭選舉。GAF算法介紹參考文獻：GAF算法介紹Matlab資源ASCENT（自適應(yīng)自配置拓撲結(jié)構(gòu)）AdaptiveSelf-ConfiguringsEnsorNetworksTopologiesDoesnotdependontheroutingprotocolDecisionaboutjoiningthenetworkbasedonlocalmeasurementsEachnodemeasuresthenumberofneighborsandpacketlosslocally.（探測狀態(tài)）Eachnodethenmakesaninformeddecisiontojointhenetworktopologyortosleepbyturningitsradiooff.（睡眠狀態(tài)）A.Cerpa,D.Estrin,Ascent:AdaptiveSelf-ConfiguringSensorNetworkTopologies,Proc.IEEEINFOCOM2002.59ASCENTNodescanbeinactiveor

passivestateActivenodesarepartofthetopology(orstayawake)andforwarddatapackets（活動狀態(tài)）Nodesinpassivestatecanbesleepingorcollectingnetworkmeasurements.Theydonotforwardanypackets.（被動狀態(tài)）AnactivenodemaysendhelpmessagestosolicitpassiveneighborstobecomeactiveifitisexperiencingalowmessagelossA.Cerpa,D.Estrin,Ascent:AdaptiveSelf-ConfiguringSensorNetworkTopologies,Proc.IEEEINFOCOM2002.60ASCENTNodescanbeinactiveor

passivestateAnodethatjoinsthenetwork(teststate)sendsanannouncementmessage.Thisprocesscontinuesuntilthenumberofactivenodesissuchthattheexperiencedmessagelossisbelowapre-definedapplication-dependentthreshold.Theprocesswillre-startwhensomefuturenetworkevent(e.g.anodefailure)orachangeintheenvironmentalconditionscausesanincreaseinthemessageloss.A.Cerpa,D.Estrin,Ascent:AdaptiveSelf-ConfiguringSensorNetworkTopologies,Proc.IEEEINFOCOM2002.61ASCENTAcommunicationholeisdetectedTransitionfrompassivetoactivestateFinalStateNetworkSelf-Configuration-ExampleA.Cerpa,D.Estrin,Ascent:AdaptiveSelf-ConfiguringSensorNetworkTopologies,Proc.IEEEINFOCOM2002.62ASCENTAcommunicationholeisdetectedTra