能量有效的三維無線傳感器網絡覆蓋算法
論文關鍵詞:無線傳感器網絡;覆蓋率;連通;網絡壽命
論文相關查閱：畢業論文范文、計算機畢業論文、畢業論文格式、行政管理論文、畢業論文
論文摘要:無線傳感器網絡通常都工作在三維空間中，因此需要三維空間中的覆蓋算法。結合三維空間的特點對二維空間內的覆蓋算法SGA進行改進，在此基礎上提出一種三維空間的覆蓋算法—SSG算法，該覆蓋算法的優點是不依賴于節點位置信息，并通過仿真實驗給出了覆蓋質量分析。
覆蓋問題是無線傳感器網絡(Wireless Sensor Network,WSN)設計中的一個基本問題。由于無線傳感器網絡節點攜帶的資源有限，如有限的處理能力、存儲和能量，且大部分無線傳感器網絡需要部署在無人看守的區域，因此，提高監測質量和延長網絡使用壽命是無線傳感器網絡設計的兩個重要方面。節約能源的使用是延長無線傳感器網絡壽命的有效措施，因此提出能量有效的覆蓋算法是覆蓋研究的方向之一。
目前無線傳感器網絡的大部分覆蓋算法是基于二維平面的。其中能量有效的算法可以分為兩類:與位置有關的算法和與位置無關的算法。與位置有關的算法需要在傳感器節點中嵌人GPS或有向天線等，不僅硬件成本相對較高，而且位置信息、方向變化等消息的傳遞和計算也會增大節點能量的開銷。而與位置無關的連通性覆蓋算法可以減少節點獲得和維護位置信息的開銷，極大地降低了硬件成本。然而，現有的覆蓋算法大多是與位置信息有關的。
與位置有關的算法需要節點自身和鄰居的位置信息，根據節點的位置信息計算覆蓋關系。例如，Slijepcevi。等人提出了集中式算法，該算法在獲知節點位置信息的條件下，可以計算其最大覆蓋集，但此算法的可擴展性不好。Xing等人提出了CCP算法，該算法能夠根據不同的應用和環境靈活地配置網絡覆蓋度與連通度，但是需要較為精確的位置信息。雖然在無線傳感器網絡中提出了很多節點定位算法，但位置誤差的可能還是很大。
與位置無關的算法不需要節點的位置信息。比如，Ye等人提出了PEAS算法。在PEAS算法中，工作節點一直工作到能量耗盡，而休眠節點以指數間隔時間開始工作，同時檢查是否至少有一個工作節點在它的探測范圍內。如果是，它再次休眠;否則，它工作直到能量耗盡。毛鶯池等人提出了一種節點位置無關的連通性部分覆蓋(Location-Unaware Connected Partial Coverage,LUCPC)協議。首先利用應用期望的覆蓋質量與所需的工作節點數量之間的數學關系，隨機選取工作節點滿足應用需求;然后根據每個節點距基站最小跳數，執行Add-On規則，增加額外節點保證網絡連通。Tian等人也提出了三種與位置無關的算法，包括基于最近鄰居的算法，基于鄰居數量的算法和基于概率的算法。Bai等人提出了一種與位置無關的能量有效的連通性覆蓋算法(Stand Guard Algorithm , SGA )。
以上算法都是在二維平面上考慮的。事實上，在一些環境中二維網絡是沒有意義的。例如，節點部署在森林中不同高度的樹上、水域的不同深度、多樓層建筑中或大氣層中都需要三維的網絡設計。森林防火、海洋學資料收集、污染控制和海上勘探等這些應用的成功與否取決于所考慮的三維空間的覆蓋率。全覆蓋網絡能夠檢測穿過這個三維空間的任何物體。因此，在三維空間中，滿足100%覆蓋且使監測所需的節點數最少成為覆蓋研究的重要問題之一。但從二維到三維的轉變并不容易，因為即使在二維中容易解決的問題，在三維中也是相當困難的。例如，Kelvin猜想、Kepler猜想以及Alam等人提出的三維空間中的節點配置策略，都沒有給出最優性的證明。
近幾年越來越多的研究者對三維無線傳感器網絡感興趣。例如，Ammari等人利用連續滲流理論給出三維無線傳感器網絡中覆蓋和連通的臨界密度。Alam等人在三維空間中找到一種節點部署策略，滿足100%覆蓋，同時使監測所需的節點數目最小。目前三維空間中能量有效的覆蓋算法也是研究的熱點之一，而把二維的算法推廣到三維是解決問題的一種有效途徑。
1、模型假設與定義
由于無線傳感器網絡經常應用于很多不同的環境，節點的布置通過輔助設備拋撒，如飛機將節點隨機播撒在監測區域內，所以本文以概率分布描述節點在空間的分布，采用的網絡模型和網絡滿足的條件如下。
1)所有節點隨機均勻地部署在一個三維空間中，節點是同類的，每個節點的傳感域是一個以節點的位置為中心、半徑為Rs的球，假設任何兩個節點不部署在同一位置，且節點是靜止的。
2)所有處于以某節點為中心、以定長R;為半徑的球內的點被認作能夠被該節點覆蓋。假設當所有節點工作時，目標區域一定能達到100%的覆蓋。
3)每個節點無需裝備GPS，且無需通過測量或定位方法獲得其具體的物理位置，每個節點有唯一的ID編號。
4)節點能量的高低只影響傳感時間，不影響傳感范圍。
定義臨界覆蓋范圍。對一個靜態WSN，存在距離集，且r滿足:以目標區域內任意一點為中心、;為半徑的球內至少有一個傳感器節點，則稱R1的最小值為臨界覆蓋范圍，用表示。
顯然，。
2、三維空間的覆蓋算法—SSG算法
2. 1SGA介紹
無線電波可以通過空氣、水等介質傳播，當某個節點發射信號時，其他節點接收到信號就執行相應操作，若沒有收到信號就不執行任何操作，執不執行操作與節點的位置無關。SGA即是用信號作為節點之間的“橋梁”這種思想設計的，避免了對節點位置的依賴性。SGA將監測區域分為若干網格，通過保證每個網格的覆蓋實現區域的全覆蓋。為了延長網絡壽命，SGA采用節點輪換工作機制，在每一輪中，對每個節點設置標記tag=0，該節點每收到一條消息，tag值加1，當tag值達到覆蓋度k時使該節點處于休眠狀態;否則，使其處于工作狀態。仿真表明SGA的覆蓋率或冗余節點率有一定優勢。但是SGA還存在不足:首先該算法是針對二維空間設計的，而一般節點部署的實際環境均是三維空間，不符合實際。其次是沒有考慮節點的能量消耗問題。在SGA中，第一輪執行時所有節點的能量相同，工作一段時間后，由于部分節點消耗能量，下一輪開始時節點的能量是不同的，SGA忽略了這個差異，使每一輪取到的工作節點都是相同的或大部分是相同的，導致集中消耗一部分節點的能量，而使另一部分節點完全浪費掉了，這樣會造成整體能量消耗的不均衡。為此本文將SGA推廣為考慮能量均衡消耗的三維空間的無線傳感器網絡覆蓋算法(SSG)。
2. 2SSG算法
在SSG算法中，也采用節點輪換工作機制，每一輪包括狀態選擇階段和工作階段。在每一輪開始，所有節點處于工作狀態，且進人狀態選擇階段。在狀態選擇階段，每個節點選擇自己的狀態(工作或休眠)，且保持這種狀態直到下一輪開始。在SSG算法中每一輪盡可能選取能量高的節點作為工作節點，使能量消耗分散在更多的節點上，從而可以達到能量平衡，延長網絡壽命。在工作階段，工作節點執行傳感任務。每個工作節點以半徑Rsg向周圍廣播SSG消息(SSGM )，其中包括節點ID。以工作節點為中心，Rsg為半徑的球內(包括邊界)的所有工作節點能夠收到這個消息。節點檢查自身傳感任務是否可由鄰居節點完成，收到SSGM的可替代節點返回一條狀態通告消息，之后進入休眠狀態，需要繼續工作的節點執行傳感任務。SSG算法詳細描述如下。
1)設置一個固定的時間片，并以其為周期。在每輪中，狀態選擇時間用T1表示，工作時間用T2表示。
2)在狀態選擇階段，按照低能量節點到高能量節點的次序等時間間隔，N為隨機部署的節點個數)廣播SSG消息(第一輪節點次序隨機)，如果在時間t內沒有其他節點收到廣播節點的SSG消息，轉4);否則，轉3)。
3)使廣播消息節點處于休眠狀態，轉4)。
4)保持它的狀態直到下一輪開始。
2. 3SSG算法的分析
根據SSG算法，任意一個處于休眠狀態的節點，在它的Rsg范圍內至少有一個工作節點(依賴Rsg，處于休眠狀態的節點集可能為空)。也就是說，Rsg≤Rs是目標區域內任意一個休眠節點被工作節點覆蓋的充分條件。因此，為了保證覆蓋質量，Rsg的取值一般小于傳感半徑Rs。下面給出目標區域內任意一點被工作節點覆蓋的充分條件。
定理 。是工作節點能100%覆蓋目標區域的充分條件。
證明假設P是目標區域內任意一點，根據的定義，以P為中心、。為半徑的球內至少有一個傳感器節點，記為A。以下分兩種情況討論:
1)若A是工作節點，因為，則P被A覆蓋。
2)若A是休眠節點，由SSG算法知，以A為中心、Rsg為半徑的球內至少有一個工作節點，記為B。根據三角不等式得:
又因為，所以，從而P被工作節點B覆蓋。其中|·|表示兩點間的歐氏距離。
綜上，由P點的任意性證得定理成立。
本文從理論上證明了定理的正確性，下面給出一個具體的實例。根據Alam等人提出的一種三維空間中的節點部署策略，假設目標區域的體積為V，部署目標區域所用的平截八面體(細胞)的體積為Vl，則滿足100%覆蓋所需要的工作節點數目M=V/Vl，其中，Vl = 0. 683 29 x (R可以看作節點的傳感半徑)。這樣，得到R的表達式為R =，如果V和M的值就能求出R的一個值。根據這種部署策略和的定義，可以用=來估計定理中的值。這里設目標區域為邊長為50的正方體，即V _- 50 x 50 x 50 ; M的值是運行算法的結果，隨Rsg的不同而不同。計算得到表1數據。
3、仿真
N個節點隨機均勻部署在一個邊長為L的正方體中，Ｌ=SO,Rs=10。在仿真中，本文考慮覆蓋率、冗余節點率和工作節點數。覆蓋率是工作節點覆蓋的區域和整個目標區域的比，它反映了WSN的監測質量。為了計算覆蓋率的值，把邊長為50的正方體劃分成邊長為1的小立方塊(共125 000個)，把中心被覆蓋的小立方塊數量和目標區域中所有立方塊數量的比作為覆蓋率。冗余節點率是休眠節點數目和總節點數目N的比。冗余節點率越高，網絡消耗的能量越少。
為了估計覆蓋率和冗余節點率，選擇N分別為800和1000 , Rsg是從I到15取值，仿真結果如圖1 ,2所示。
從圖中看到當Rsg增大時，冗余節點率上升，覆蓋率下降。為了證實工作過的節點數確實隨著輪數的增加而增加，以N=800為例，Rsg是從1到10取值，其中i(i=1,2,…,5)輪工作過的節點數是指第1輪到第i輪工作過的節點個數，仿真結果如圖3所示，所有圖中標記的每個點是多次重復實驗的平均值。
在實際應用中，選擇最優的Rsg值，使網絡既滿足覆蓋要求，同時使冗余節點率達到最大，從而節省節點能耗，延長網絡壽命。從圖中可以看出，當Rsg≤Rs/2時，覆蓋率為1(或接近1);當Rsg>Rs/2時，覆蓋率迅速下降。所以對于三維空間中的覆蓋問題，如果不能精確估計Rsg的值，最好取Rsg的值為傳感半徑的一半。
4、結語
本文將SGA推廣到三維空間中，提出SSG算法，解決在沒有節點位置信息的情況下三維空間的覆蓋問題。實驗結果表明，該算法在滿足100%覆蓋的前提下，使冗余節點的數目達到最大，從而節省了能耗，延長了網絡壽命。
論文相關查閱：畢業論文范文、計算機畢業論文、畢業論文格式、行政管理論文、畢業論文
【能量有效的三維無線傳感器網絡覆蓋算法】相關文章：
基于簇的無線傳感器網絡能量平衡策略11-16
無線傳感器網絡故障檢測11-16
無線傳感器網絡故障檢測研究11-21
無線傳感器網絡安全技術及運用實踐12-11
基于傳輸半徑倍數的無線傳感器網絡交替路由11-16
基于網格特征臨界點的三維工程模型檢索算法11-23
無線遙控開題報告11-14
- 相關推薦