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