畢業(yè)設計]基于負載平衡的無線傳感器網(wǎng)絡中的多跳分群算法.doc

基于負載平衡的無線傳感器網(wǎng)絡中的多跳分群算法摘要：本文提出了一種新的基于路由算法的分群，它利用傳感器網(wǎng)絡的冗余特性，為了解決在無線傳感器網(wǎng)絡中負載平衡和能源效率的傳統(tǒng)問題。該算法充分利用在某一傳感器網(wǎng)絡中的節(jié)點，該傳感器網(wǎng)絡的區(qū)域覆蓋范圍被相鄰的節(jié)點所覆蓋以及像臨時聚集頭一樣標記。然后，該算法形成兩個多跳通信層。涉及內部集群通信的底層和涉及集群通信之間的頂層都涉及臨時聚集頭。性能研究表明，該算法有效地解決負載平衡的問題，以及更能有效地形成從過濾器和增強版過濾器中的能源消耗。關鍵詞：集群路由，高效集群間路由，能源效率路由，基于路由的覆蓋面。1.介紹由于在微電氣機械系統(tǒng)無線電通信領域的最新研究進展已經(jīng)使計算和通信在比較短的距離里形成微小的節(jié)點能力的感知成為可能。如果監(jiān)測傳感器都不能給出精確的結果，這些節(jié)點可以完成傳感協(xié)作。它們能夠形成一個無人管理的自主智能網(wǎng)絡。麻省理工學院的科技評論和全球化未來指明傳感技術是十大新興技術之一，它能夠改變世界。一個無線傳感器網(wǎng)絡根據(jù)拓撲學和與外面世界通信的渠道劃分是由傳感節(jié)點、計算節(jié)點和通信能力連接節(jié)點組成。該網(wǎng)絡能監(jiān)測活動和現(xiàn)象，這些活動和現(xiàn)象是不能被人類容易地監(jiān)測，例如網(wǎng)站的核事故，某些化學領域的監(jiān)測和長時間段的環(huán)境監(jiān)測。這些網(wǎng)絡的總體特征是拓撲結構不斷變化，由于網(wǎng)絡中的節(jié)點安排在不同的狀態(tài)，例如在網(wǎng)絡中睡眠或是醒著的狀態(tài)以及失去活力的節(jié)點，網(wǎng)絡的密集部署，自主智能網(wǎng)絡管理，多集通信，有限的節(jié)點能量和有限的帶寬。由于無線電通信的短距離和能量消耗與距離的平方成正比的事實使多集通信代替直接通信將能夠節(jié)省能源。在無線傳感器網(wǎng)絡中，每一個節(jié)點都試圖對本地數(shù)據(jù)執(zhí)行計算，因此數(shù)據(jù)需要被轉凝聚。因為在無線傳感器網(wǎng)絡中計算比數(shù)據(jù)傳輸更便宜。例如，計算節(jié)點數(shù)據(jù)樣本的中位數(shù)比傳送數(shù)據(jù)樣本和計算水槽的中位數(shù)更有效率。無線傳感器網(wǎng)絡是數(shù)據(jù)中心網(wǎng)絡，并且由于節(jié)點的數(shù)據(jù)多，因此不能有效地給予唯一的ID給傳感器節(jié)點。這些節(jié)點通常被稱作類型或數(shù)據(jù)，它們正在處理的范圍。這些網(wǎng)絡具有很高的應用特性，因此協(xié)議操作種類的結構從應用到應用程序各不相同。一個路由算法可能很擅長定期監(jiān)測，但是也可能執(zhí)行的不好，可能將會產(chǎn)生持續(xù)的數(shù)據(jù)傳感。本文的其余部分組織如下。第二部分簡要介紹了無線傳感器網(wǎng)絡在各個領域的應用。第三部分給出了各種聚類算法的簡要概述。第四部分包括對相關研究工作的詳細調查。該算法是針對第五部分和第六部分討論的仿真和第七部分它的最終結果。2.應用本節(jié)介紹了無線傳感器網(wǎng)絡可以有效地運用的少數(shù)地區(qū)，無線傳感器網(wǎng)絡能夠監(jiān)測的應用的系統(tǒng)包括溫度、濕度、壓力、閃電條件、土壤組成、物質的存在、機械壓力、速度、方向和物體的大小。典型的應用包括監(jiān)測和軍事，農(nóng)業(yè)和環(huán)境的戰(zhàn)場空間監(jiān)測，例如，伯克利大學的研究人員和在緬因州上的大鴨島上部署傳感器。這些網(wǎng)絡監(jiān)測微氣候里面和周圍的被用作海燕的筑巢的洞穴。這樣做的目的是為了形成一個生態(tài)環(huán)境監(jiān)測組件，它能夠使來自全世界的研究者從事于非入侵性的和非破壞性的敏感的野生動物和棲息地的監(jiān)測。工程應用包括維修的大型工業(yè)廠房或是民用建筑的監(jiān)測，現(xiàn)代化建筑的規(guī)定都是依據(jù)溫度，濕度等等。其他的應用包括林火探測，洪水監(jiān)測等等。3.無線傳感器網(wǎng)絡分群的挑戰(zhàn)和問題盡管該算法具有巨大的潛力和優(yōu)勢，換句話說，就是分布式局部計算，通信中一個網(wǎng)絡的某一部分發(fā)生故障，不影響其他部分的網(wǎng)絡，更長距離的覆蓋范圍，極端環(huán)境監(jiān)控，無線傳感器網(wǎng)絡的構成都對研究團體形成了挑戰(zhàn)。本節(jié)簡要的概述無線傳感器網(wǎng)絡監(jiān)測所面臨的一些重大挑戰(zhàn)。3.1網(wǎng)絡部署在無線傳感器網(wǎng)絡中的節(jié)點部署即是固定的也是隨機的，它依據(jù)其應用。網(wǎng)絡的固定部署是部署在固定的位置，在網(wǎng)絡的隨機部署中，產(chǎn)生的分布可以是統(tǒng)一的或是不統(tǒng)一的。在這種情況下，網(wǎng)絡的認真管理是必須的，為了通過網(wǎng)絡確保覆蓋全部的范圍和確保能源消耗的統(tǒng)一。3.2異構網(wǎng)絡該無線傳感器網(wǎng)絡并不是一直統(tǒng)一的，在很多情況下，一個網(wǎng)絡是異構的，它包括節(jié)點的不同能量層次。一些節(jié)點比其他節(jié)點少些能量約束。通常能量約束小的節(jié)點的一小部分都是很小的。在這種類型的網(wǎng)絡能量越少約束的節(jié)點都是被選作聚集頭和能量約束的節(jié)點都是集群的工作節(jié)點。這種網(wǎng)絡的問題出現(xiàn)在當網(wǎng)絡被隨機部署時和所有的聚集頭都被集中于某些特定的網(wǎng)絡部分，并導致不平衡的聚集形成和使某些網(wǎng)絡的部分變得不可能實現(xiàn)。此外，如果集群產(chǎn)生的分配頭是均勻的，并且如果我們使用多跳通信，靠近聚集頭的節(jié)點都會承受一個巨大的負載，就好像所有的通信量都是通過聚集頭的相鄰節(jié)點從網(wǎng)絡的不同區(qū)域到聚集頭路由來的，這將導致在聚集頭的鄰近部分的節(jié)點快速死亡，并導致聚集頭之間的差距，減小網(wǎng)絡的大小和增加網(wǎng)絡的能量消耗。異構傳感器網(wǎng)絡需要群組仔細的管理，為了避免不平衡聚集頭分布導致的問題和確保通過網(wǎng)絡的能量消耗是均勻的。3.3網(wǎng)絡擴展當一個無線傳感器網(wǎng)絡被部署時，有的時候新的節(jié)點需要被附加到該網(wǎng)絡中，為了覆蓋更多的區(qū)域和延長即時網(wǎng)絡的生命。在這兩種情況下，聚類方案應該能夠適應網(wǎng)絡拓撲的改變。其關鍵點是設計，這樣的管理解決方案應該能夠適用該算法是本地的并且是動態(tài)的，它將更容易適應拓撲的改變3.4統(tǒng)一的能量消耗在無線傳感器網(wǎng)絡中的傳輸相對于傳感器而言是需要更多的能量消耗，因此，執(zhí)行數(shù)據(jù)傳輸?shù)交嘏_的功能的聚集頭相對于其他空閑的節(jié)點需要更多的能量。為了平衡網(wǎng)絡的能量消耗，聚類方案應該確保通過網(wǎng)絡的能量損耗平衡和該聚集頭應該能夠旋轉。3.5多跳或單跳通信這種通信形式對于無線傳感器網(wǎng)絡的使用者即是單跳的也是多跳的。因為在無線系統(tǒng)中的能量消耗是與距離的平方成正比的。因為依據(jù)能源消耗，跳通信是昂貴的。大多數(shù)的路由算法都是使用多跳通信形式，因為根據(jù)能量消耗，它更加的有能源效率，它的多跳通信更靠近聚集頭的節(jié)點都承受很大的負載，并且當它們的能量終止時它能夠創(chuàng)造空白在附近的聚集頭。3.6基于定址的屬性由于節(jié)點的數(shù)目太多，因此，在無線傳感器網(wǎng)絡中它是不能給每個節(jié)點分配ID的。數(shù)據(jù)進入節(jié)點是通過屬性而不是通過ID。這樣使得它侵入系統(tǒng)更加的簡單，并且實施安全機制更加的簡單。3.7群集動力學群集動力學的意思就是群集的不同的參數(shù)都是如何被決定的，例如，在某一特定的網(wǎng)絡群集的數(shù)量。在某些情況下，這些數(shù)量是被預先指定的，在某些情況下，它是動態(tài)的。這些聚集頭執(zhí)行壓縮的功能和數(shù)據(jù)傳輸一樣。聚集頭之間的距離是一個重大的問題，它可能是動態(tài)的，也可能被設定成一致和一些最小價值。假設是動態(tài)的，有可能形成不平衡的集群。然而限制它的一些情況，有最小距離可能是有效地在某些情況下，但是這是一個開放的研究問題，聚集頭部分可能是中心的或是非中心的，它有優(yōu)點也有缺點。集群的數(shù)量可能是固定的，也可能是動態(tài)的。集群的固定數(shù)量導致少量的超支，在這樣的網(wǎng)絡中將不能夠重復的通過集群的設置階段的形成。依據(jù)其可擴展行它是貧窮的。4.相關研究首先，在無線傳感器網(wǎng)絡中的路由是一個具有挑戰(zhàn)性的任務，因為總尋址方案的缺乏。其次，來自多跳路徑的數(shù)據(jù)資源是單一的資源。最后，由于數(shù)據(jù)冗余和能量，以及網(wǎng)絡能量約束。當應用到無線傳感器網(wǎng)絡中時，常規(guī)的路由選擇算法不是有效的。對于無線傳感器網(wǎng)絡，現(xiàn)有的路由選擇算法的性能從應用到應用程序是多種多樣的，由于不同應用需求的多樣性。路由技術發(fā)展的強烈需要，能夠在更廣泛的應用中發(fā)揮作用?；诰W(wǎng)絡結構和第二基于協(xié)議操作，大致路由協(xié)議可以分為兩個類型。網(wǎng)絡結構可進一步分為平坦網(wǎng)絡路由，分層網(wǎng)絡路由和基于位置的路由。協(xié)議操作能夠被分作談判的基礎，多路徑的基礎，查詢的基礎，基礎服務和一致的基礎路由。剩下的部分簡要的描述了基于網(wǎng)絡結構的路由協(xié)議和更具體的分層路由算法。在無線傳感器網(wǎng)絡中的集群基礎路由收到分層路由種類的影響。分層路由涉及集群信息，在這里節(jié)點分配的傳感的任務，它有低能量和傳輸任務的節(jié)點有更高的能量。這樣做的目的是為了執(zhí)行能量效率路由。該集群頭可能是一個擁有更高能量的特殊節(jié)點或者是依賴算法和應用的普通節(jié)點。還聚集頭也執(zhí)行計算功能，例如為了減少基于基站節(jié)約能量的傳輸數(shù)量的數(shù)據(jù)收集和數(shù)據(jù)壓縮。它的一個基本的優(yōu)勢是集群的延遲將會減少相對于基于基站缺失能量來到達的平坦路由。在無線傳感器網(wǎng)絡中，基于聚類的算法被認為是最有效的路由算法。其效率的基本原則是運作時根據(jù)分離和侵占的規(guī)律。在能源消耗方面的聚類是通過減少碰撞來提高的。在無線傳感器網(wǎng)絡中目前的工作是能源效率，它將決定聚集頭的選擇，聚集頭之間的距離，集群的類型和集群間和內部集群通信，它們部署的環(huán)境類型，網(wǎng)絡組織的建立和穩(wěn)定性都是考慮制定一套基于路由算法的高效的集群主要的因素。在接下來的章節(jié)里，我們在共同的聚類算法方面做一個簡單的介紹。傳感器網(wǎng)絡的第一層路由方法之一就是過濾。大部分的聚類算法都來自于這種算法。該協(xié)議僅僅使用了兩個通信層。一個是集群間的通信，另外一個是集群頭之間的通信。在這里聚集頭的選擇是隨機的，并且聚集頭角色的轉變是為了平衡整個網(wǎng)絡的能源消耗。集群的形成取決于每個節(jié)點接受該廣告信息的信號強度。節(jié)點將會去信號最強的那個集群，并且它也為網(wǎng)絡計算集群頭總數(shù)。根據(jù)過濾工作是整個網(wǎng)絡的5%，并且其仿真結果表明過濾形成超過了7耗能單位為基礎的路由，如直接擴散。Leach協(xié)議最主要的問題在于聚集頭的隨機選擇。聚集頭的隨機選擇存在一個聚集頭形成的不平衡，并且可能制作某些網(wǎng)站無法訪問的可能性。Leach協(xié)議的擴展使用集中聚集形成算法。該算法的執(zhí)行是從第一次接收所有關于每個節(jié)點它們位置和能級的信息的基站開始，然后它運行該算法，用于形成集群頭和集群。在這里集群的數(shù)量是有限的，并且集群頭的選擇也是隨機的，但是基站確保一個節(jié)點能量較小，就不會成為聚集頭。LeachC的難題在于在更大的網(wǎng)絡中，它是不可行的，因為節(jié)點遠離基站將會導致節(jié)點發(fā)送它們的位置到基站變得困難，并且由于聚集頭角色開始轉變，遠距離節(jié)點將可能無法及時到達基站。這將會導致通信延遲的增加，并且延遲也將放大。Leach的路由算法基于兩個階段，建立階段和穩(wěn)定階段。在建立階段聚集頭是隨機選擇的，穩(wěn)定階段既是數(shù)據(jù)傳輸階段。Leachf采用的想法是如果集群保持不變，并且僅僅只是在集群中轉變聚集頭的角色，這將節(jié)約大量的能源和提高系統(tǒng)吞吐量，然而缺點就是缺乏可擴展性的網(wǎng)絡，這就意味著不能增加新的節(jié)點。Teen原則上是給時間的關鍵應用及時的對感應數(shù)據(jù)突然的變化做出響應。這里的節(jié)點感應數(shù)據(jù)是不斷的與數(shù)據(jù)傳輸進行比較的，這是唯一在數(shù)據(jù)的興趣范圍的用戶。這里的聚集頭使用兩種價值閥值，一個是硬閥值和其它軟閥值。硬閥值是屬性的最小價值，觸發(fā)的傳輸是從一個節(jié)點的聚集頭開始的，它是在這個意義上價值屬性的微小變化。當屬性變化的數(shù)額等于或大于軟閥值時該節(jié)點將會發(fā)送。軟閥值減少進一步的傳輸，如果屬性值沒有顯著意義的變化。這個方案的最大優(yōu)點就是它適合于關鍵應用的時間，大大減少了傳輸次數(shù)，并且為用戶提供了屬性值準確性的控制權，當用戶正在通過改變軟閥值來收集時。Apteen協(xié)議是Teen的擴展，它是一個既定期收集數(shù)據(jù)的混合協(xié)議，也是一個對關鍵數(shù)據(jù)進行實時采集的協(xié)議。這里的聚集頭廣播了四種類型的信息給節(jié)點。閥值，屬性值和一個節(jié)點的調度方案的TDMA允許每一個節(jié)點進行傳輸仿真，它的仿真結果表明Teen和Apteen執(zhí)行的更好，然而Leach在能源消耗方面是最節(jié)約的。比較Leach、Teen和Apteen，Teen表現(xiàn)優(yōu)于其他兩個。它的缺點是由于在Teen和Apteen間存在多層次聚類，將會導致多層次聚類更加復雜和產(chǎn)生間接費用。這個協(xié)議提出了一個多網(wǎng)關架構來保障大區(qū)域的利益，而不會降低系統(tǒng)的大面積的利益服務。該算法平衡在不同集群之間的負載的密度的均勻。該網(wǎng)絡采用兩種類型的節(jié)點：能源約束的傳感節(jié)點和能量約束更少的網(wǎng)關節(jié)點。網(wǎng)關保持傳感器收集數(shù)據(jù)的狀態(tài)和設置多跳路由的狀態(tài)。基于MAC的節(jié)點TDMA被用作聚集頭之間的通信。它的缺點就是由于聚集頭是靜態(tài)的，其節(jié)點能量約束又低于其余的節(jié)點，它們在網(wǎng)絡中是終身固定的，因此節(jié)點接近集群頭將會比其它的節(jié)點更早的失去作用，從而導致與附近聚集頭之間的差距，減少了網(wǎng)絡連接。此外，如果網(wǎng)絡的部署是隨機的，將很可能導致聚集頭之間的不平衡分配。集中式協(xié)議提出通過復雜的計算能力是基站的重要組成部分。基站使用的所有高能量消費的決定，像聚集頭的選擇，路線計算等等。這種算法主要有兩個主要的階段，第一個階段是安裝階段，第二個階段是數(shù)據(jù)通信。在安裝集群的形成階段，選擇聚集頭和為每個集群做安排。此外基站接收來自所有節(jié)點的能量并計算產(chǎn)生能量的平均值，然后當節(jié)點的能量水平高于節(jié)點能量的平均水平值時，聚集頭將會選擇該種設置。第二步是使保留的節(jié)點在聚集頭中結群，然后通過反復的過程，直至達到形成集群所需要的集群數(shù)量，這個過程也保證了選擇集群頭是均勻分布的，數(shù)據(jù)通信階段包括以下活動：數(shù)據(jù)采集數(shù)據(jù)融合數(shù)據(jù)路由仿真結果表明，BCDCP其性能優(yōu)于Leach，LeachC和PEGASIS還形成于CH到CH的路徑，其計劃是轉移數(shù)據(jù)融合到基站。該協(xié)議的缺點是它需要在網(wǎng)絡中的所有節(jié)點的信息在聚集頭選擇之前，如果不是這樣將會導致無法正常工作，因為它使用了集群集中管理的方式。由漢森，諾蘭和約克曼的文獻可以看出通過分離聚集頭可以降低多少能量消耗在傳感器網(wǎng)絡中。該集群的形成在同一個LeachC。為了盡量減少能集群節(jié)點的量消耗，當傳輸數(shù)據(jù)到達集群頭時，該算法隨機選擇一個節(jié)點適應聚集頭的選擇，與此同時還可以確保節(jié)點與其他集群的最小間隔在同一時間上。這個節(jié)點應該有能量級，包括網(wǎng)絡中的平均能量級。當聚集頭得選擇過程結束后，集群也完成了形成在同一時間內同一個Leach上。仿真結果表明，最小間隔距離提高了能量效率，通過基站接受郵件的數(shù)量來衡量，這也表明它比不使用最小間隔距離要好1.5倍。在IsrarandAwan,2006中，我們提出的多跳路由集群間通信的算法，該算法是一個多層次多跳路由算法，它的工作原則是分離、戰(zhàn)勝和為了在下載和能源效率方面形成平衡。該算法的目的是利用該傳感器網(wǎng)絡的冗余特性，它會選擇網(wǎng)絡節(jié)點很小的一部分，并標記它們作為臨時集群頭，并使用這些節(jié)點，使集群間多跳。該算法的問題是它選擇臨時聚集頭是隨機的，這樣將會影響網(wǎng)絡。這種算法修改后的版本作為臨時聚集頭的附加保證，作為臨時集群頭選擇的節(jié)點的覆蓋面積只有這些節(jié)點。此外，該算法形成兩個層次的通信，底層是檢測數(shù)據(jù)的節(jié)點，并參與內部集群的通信，第二層包括聚集頭和臨時聚集頭，無論層之間的通信是多跳的，我們都可以使接下來關于網(wǎng)絡模型的消耗所取的做如下假設：網(wǎng)絡由100個傳感節(jié)點組成；所有的節(jié)點都具有相同的電池電量和結構；該網(wǎng)絡在500平方米的區(qū)域內是隨機部署的；我們假設該網(wǎng)絡是嘈雜的和沒有錯誤的；能量消耗的假設都低于50nj/bit，在運行的同時發(fā)送和接受100Pj/bit的傳輸電路；我們并沒用對網(wǎng)絡同步，無線傳輸范圍和有關控制信息做任何假設；每個節(jié)點它通過一些GPS系統(tǒng)或使用一些定位算法，知道每個節(jié)點的位置信息和鄰節(jié)點信息；每個節(jié)點都有相關的覆蓋范圍。5.MCLB（多跳聚類的負載平衡算法）該MCLB包括兩個不同的階段，安裝階段和穩(wěn)定階段。在安裝階段聚集頭和臨時聚集頭之間相互選擇跟隨穩(wěn)定階段，在穩(wěn)定階段就是數(shù)據(jù)傳輸?shù)碾A段。在安裝階段，該算法首先將過濾器中的所有節(jié)點涵蓋在一定的網(wǎng)絡覆蓋范圍內，相鄰的覆蓋范圍是通過該算法決定的，如果我們結合起來，通過接觸兩個不同的區(qū)域和節(jié)點本身，將會產(chǎn)生更大的傳感節(jié)點范圍。有的時候，傳感范圍也包括不同的感測范圍，因為它們擁有不同的電源能量，但是在該算法中，我們并不考慮它的區(qū)域類型。圖2描述了臨時聚集頭形成的整體運作，在這里節(jié)點5的傳感范圍