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