一種鏈狀巷道WSN定位覆蓋控制算法

摘 ?要：根據(jù)鏈狀巷道WSN定位的需求和節(jié)點(diǎn)部署的特點(diǎn)，提出一種適用于鏈狀無(wú)線傳感器網(wǎng)絡(luò)的K（K≥3）重覆蓋控制算法——LKCC，仿真實(shí)驗(yàn)表明：LKCC算法通過(guò)休眠機(jī)制能有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期。與經(jīng)典的K重覆蓋控制算法CCP相比，該算法能夠保證鏈狀網(wǎng)絡(luò)K（K≥3）重覆蓋以及相同的WSN網(wǎng)絡(luò)生命周期下使用節(jié)點(diǎn)個(gè)數(shù)平均降低34.26%。

關(guān)鍵詞：鏈狀巷道;節(jié)點(diǎn)部署;覆蓋控制;節(jié)點(diǎn)數(shù)量

中圖分類號(hào)：TP212.9;TN929.5 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）21-0053-03

A WSN Positioning Coverage Control Algorithm for Chain Roadway

WANG Fei

（Anhui Sun Create Electronics Co.，Ltd.，Hefei ?230088，China）

Abstract：According to the requirements of WSN positioning in chain roadway and the characteristics of node deployment，a K-coverage（K≥3）control algorithm LKCC is proposed for chain wireless sensor networks. The simulation experiments show that LKCC algorithm can effectively extend the network life cycle through sleep mechanism. Compared with the classical K-coverage control algorithm CCP，the algorithm can guarantee K-coverage（K≥3）of the chain network and the average number of nodes used in the same WSN network life cycle is reduced by 34.26%.

Keywords：chain roadway;node deployment;coverage control;node number

0 ?引 ?言

本單位因人防項(xiàng)目需要，需對(duì)人防地下巷道人員進(jìn)行長(zhǎng)期定位，在無(wú)衛(wèi)星信號(hào)和無(wú)持續(xù)電源供電情況下，本單位產(chǎn)品組將無(wú)線傳感器網(wǎng)絡(luò)（WSN）考慮進(jìn)來(lái)。因受巷道地形特點(diǎn)影響，迫使傳感器節(jié)點(diǎn)沿著狹長(zhǎng)巷道部署。傳感器節(jié)點(diǎn)的隨機(jī)部署，不僅浪費(fèi)節(jié)點(diǎn)個(gè)數(shù)，而且易造成節(jié)點(diǎn)損壞頻繁退出網(wǎng)絡(luò)[1，2]。采用固定部署方式將節(jié)點(diǎn)有規(guī)劃地部署在巷道的兩側(cè)，保障了節(jié)點(diǎn)不易遭受人為損壞或自然損壞。但是這樣的部署會(huì)給同側(cè)兩節(jié)點(diǎn)的通信帶來(lái)困難，主要是因?yàn)榭拷鼔Ρ诘膬晒?jié)點(diǎn)是一種非視距、非自由空間的傳播通信方式，因此對(duì)于巷道相鄰節(jié)點(diǎn)的通信使用上下兩側(cè)節(jié)點(diǎn)之間的通信方式，任意相鄰三點(diǎn)之間的通信與巷壁構(gòu)成三角形。

所謂的覆蓋控制，就是在保證網(wǎng)絡(luò)覆蓋度和通信連通的前提下，僅將部分節(jié)點(diǎn)作為活躍節(jié)點(diǎn)，而其余節(jié)點(diǎn)都轉(zhuǎn)入低功耗的睡眠狀態(tài)。這樣，網(wǎng)絡(luò)中活躍節(jié)點(diǎn)數(shù)量可以降低，減少通信干擾，從而降低WSN的整體能耗[3]。對(duì)于巷道移動(dòng)節(jié)點(diǎn)的定位，要想保證一定的定位精度，目標(biāo)區(qū)域?qū)π艠?biāo)節(jié)點(diǎn)的個(gè)數(shù)應(yīng)有所要求，少則定位精度不高，多則浪費(fèi)節(jié)點(diǎn)能耗。只有保證巷道下WSN相對(duì)恒定地處于K（K≥3）重覆蓋范圍，才能滿足移動(dòng)節(jié)點(diǎn)定位過(guò)程中需要信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。因此，設(shè)計(jì)出一種能夠使用盡可能少的工作節(jié)點(diǎn)來(lái)達(dá)到所期望的覆蓋度的算法是很有意義的。Zhang和Hou在已知傳感器位置信息的條件下提出了最優(yōu)完全覆蓋算法OGDC[4]，但其是利用正三角形來(lái)設(shè)計(jì)的，對(duì)于巷道的鏈狀環(huán)境不適合。Xu等人提出GAF算法只考慮到WSN的連通性，并沒(méi)有考慮WSN的覆蓋問(wèn)題，它是利用正四邊形來(lái)設(shè)計(jì)的[5]。下文依據(jù)巷道WSN和節(jié)點(diǎn)部署的特點(diǎn)以及相鄰節(jié)點(diǎn)的通信方式設(shè)計(jì)出一種等腰三角形部署模型，LKCC算法根據(jù)此模型執(zhí)行對(duì)鏈狀巷道WSN的覆蓋控制，保證使用較少的工作節(jié)點(diǎn)來(lái)滿足鏈狀巷道WSN的K（K≥3）重覆蓋。

1 ?部署策略

根據(jù)巷道WSN網(wǎng)絡(luò)節(jié)點(diǎn)部署模型設(shè)計(jì)，文中引用以下假設(shè)：

（1）所有節(jié)點(diǎn)同構(gòu)，即每個(gè)節(jié)點(diǎn)具有相同的探測(cè)半徑、通信半徑、初始能量、發(fā)送功率和接收功率。

（2）采用基于布爾的感知模型，即0/1模型。節(jié)點(diǎn)感知半徑內(nèi)發(fā)生的事件以概率1感知，而半徑之外的事件感知率為0，傳感區(qū)域定義為一個(gè)半徑為rs的圓。

（3）所有的傳感器節(jié)點(diǎn)都處于同一平面。

由于巷道狹長(zhǎng)地理特征，參考節(jié)點(diǎn)與基站節(jié)點(diǎn)通信都采用多跳方式，易造成越離基站近的節(jié)點(diǎn)需要轉(zhuǎn)發(fā)的數(shù)據(jù)信息也就越多，消耗的能量也就越大，從而出現(xiàn)靠近基站的節(jié)點(diǎn)過(guò)早死亡的問(wèn)題。在巷道的左右兩巷壁部署節(jié)點(diǎn)時(shí)，應(yīng)該采用非均勻的節(jié)點(diǎn)部署策略，這樣才能夠保證巷道整體網(wǎng)絡(luò)能耗的均衡性，延長(zhǎng)網(wǎng)絡(luò)生命周期[6]。

根據(jù)巷道的相鄰節(jié)點(diǎn)通信方式的特點(diǎn)，可以把巷道WSN虛擬分成若干個(gè)三角形網(wǎng)格，類似于常見(jiàn)覆蓋算法中虛擬單元格的劃分。然而對(duì)于常見(jiàn)的正三角形、正四邊形或是正六邊形網(wǎng)格也不再適合巷道線型環(huán)境，對(duì)于巷道劃分的三角形網(wǎng)格大部分是普通的三角形，下面介紹如何保證這些普通的三角形網(wǎng)格在巷道長(zhǎng)度、寬度以及節(jié)點(diǎn)的傳感半徑rs已知的情況下使用最少的工作節(jié)點(diǎn)保證巷道WSN的K（K≥3）重覆蓋網(wǎng)絡(luò)部署模型。

模型：等腰三角形部署網(wǎng)絡(luò)K（K≥3）重覆蓋的最小覆蓋集

下面通過(guò)固定其巷道的節(jié)點(diǎn)布撒的密度和節(jié)點(diǎn)的感應(yīng)半徑rs，通過(guò)調(diào)節(jié)巷道的長(zhǎng)度L來(lái)對(duì)LKCC算法和CCP算法對(duì)巷道WSN形成的滿足K（K≥3）重覆蓋的需要的工作節(jié)點(diǎn)個(gè)數(shù)作了統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖4所示，結(jié)果對(duì)比CCP算法，在滿足定位覆蓋要求的同時(shí)，能使工作的傳感器節(jié)點(diǎn)個(gè)數(shù)平均降低34.26%。

4 ?結(jié) ?論

針對(duì)巷道的地形以及WSN節(jié)點(diǎn)部署特點(diǎn)，設(shè)計(jì)出一種滿足定位條件的K重覆蓋算法LKCC，相比經(jīng)典的CCP算法，在保證工作節(jié)點(diǎn)滿足定位條件的K重覆蓋和相同WSN網(wǎng)絡(luò)生命周期同時(shí)，能使傳感器節(jié)點(diǎn)個(gè)數(shù)平均降低34.26%。

參考文獻(xiàn)：

[1] 閆雒恒，賀昱曜.一種魯棒的無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞修補(bǔ)方法 [J].計(jì)算機(jī)科學(xué)，2017，44（2）：123-128+146.

[2] 田豐，王飛，劉華艷，等.一種線型無(wú)線傳感器網(wǎng)絡(luò)部署策略 [J].傳感技術(shù)學(xué)報(bào)，2010，23（11）：1633-1637.

[3] 孫澤華，裴二榮，韓昊哲.無(wú)線傳感器網(wǎng)絡(luò)中基于網(wǎng)絡(luò)覆蓋的節(jié)點(diǎn)睡眠調(diào)度機(jī)制 [J].計(jì)算機(jī)應(yīng)用研究，2016，33（9）：2731-2734+2742.

[4] ZHANG H H，HOU J C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks [J].Ad Hoc & Sensor Wireless Networks，2005，1（1-2）：89-124.

[5] XU Y，HEIDEMANN J，ESTRIN D. Geography-Informed energy conservation for ad hoc routing [C]//Proceedings of the 7th annual international conference on Mobile computing and networking.New York：Association for Computing Machinery New York NY United States，2001：70-84.

[6] 牛玉剛，杜國(guó)杰，賈廷綱.一種基于能耗均衡的分區(qū)節(jié)點(diǎn)部署算法 [J].控制與決策，2016，31（6）：1021-1026.

[7] NIE H，WU J H. Coexistence of an unstirred chemostat model with Beddington-DeAngelis functional response and inhibitor [J].Nonlinear Analysis：Real World Applications，2010，11（5）：3639-3652.

作者簡(jiǎn)介：王飛（1983—），男，漢族，安徽含山人，產(chǎn)品經(jīng)理，高級(jí)工程師，碩士，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。