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