南陽(yáng)醫(yī)學(xué)高等專科學(xué)校 田 肖

基于覆蓋控制的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度機(jī)制研究

南陽(yáng)醫(yī)學(xué)高等?？茖W(xué)校 田 肖

無(wú)線傳感器網(wǎng)絡(luò)是這幾年新興的一個(gè)熱門研究領(lǐng)域，它是由大量靜止或移動(dòng)的傳感器節(jié)點(diǎn)以自組織和多跳的方式構(gòu)成的無(wú)線網(wǎng)絡(luò)。目前，對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度的研究偏向于網(wǎng)絡(luò)能耗和網(wǎng)絡(luò)性能折衷的WSN節(jié)點(diǎn)調(diào)度機(jī)制，因此，本文基于覆蓋控制，從覆蓋能力、網(wǎng)絡(luò)連通、能量消耗、能耗均衡等多方面綜合探索WSN節(jié)點(diǎn)調(diào)度。

無(wú)線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)能耗；網(wǎng)絡(luò)性能；節(jié)點(diǎn)調(diào)度

1 引言

無(wú)線傳感器網(wǎng)絡(luò)實(shí)質(zhì)是分布式系統(tǒng)，由于傳感器在感知區(qū)域中要作為網(wǎng)絡(luò)節(jié)點(diǎn)用來(lái)采集和處理感知到的數(shù)據(jù)，又要路由、發(fā)送這些數(shù)據(jù)信息，而且無(wú)線傳感器網(wǎng)絡(luò)功能單一、節(jié)點(diǎn)覆蓋范圍小、單個(gè)節(jié)點(diǎn)沒辦法獨(dú)立完成復(fù)雜任務(wù)，需多個(gè)節(jié)點(diǎn)協(xié)同工作。目前出現(xiàn)的節(jié)點(diǎn)調(diào)度機(jī)制按照約束條件側(cè)重點(diǎn)不同，有不同的實(shí)現(xiàn)方法。其中，基于覆蓋控制的節(jié)點(diǎn)調(diào)度機(jī)制，是以覆蓋性能為一個(gè)重要的約束條件，選擇節(jié)點(diǎn)以優(yōu)化的方式覆蓋監(jiān)測(cè)區(qū)域，保證監(jiān)測(cè)數(shù)據(jù)的全局有效性。因此，研究無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度機(jī)制對(duì)無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用有重要的實(shí)際意義。

2 WSN中的節(jié)點(diǎn)調(diào)度機(jī)制分析

在多目標(biāo)跟蹤下的節(jié)點(diǎn)調(diào)度機(jī)制中，WSN中隨機(jī)部署的傳感器節(jié)點(diǎn)數(shù)要遠(yuǎn)大于完成任務(wù)所須的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)調(diào)度須依據(jù)規(guī)則在眾節(jié)點(diǎn)中找出執(zhí)行任務(wù)的節(jié)點(diǎn)，將余節(jié)點(diǎn)設(shè)定為休眠狀態(tài)，從而在完成感知任務(wù)的同時(shí)延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命期。本文主要討論在節(jié)點(diǎn)位置信息未知的情況下選取工作節(jié)點(diǎn)完成區(qū)域覆蓋。主要從以下幾個(gè)方面探討節(jié)點(diǎn)覆蓋調(diào)度的機(jī)制。

2.1 覆蓋能力

WSN最基本功能是用節(jié)點(diǎn)監(jiān)測(cè)部署區(qū)域情況，收集數(shù)據(jù)，因而，網(wǎng)絡(luò)覆蓋能力是網(wǎng)絡(luò)服務(wù)質(zhì)量的重要指標(biāo)之一，它也是衡量WSN覆蓋調(diào)度是否優(yōu)劣的一個(gè)首要標(biāo)準(zhǔn)。

文獻(xiàn)[1]提出局部面向曝光的覆蓋和位置發(fā)現(xiàn)算法，提出3個(gè)移動(dòng)傳感器從密集區(qū)域移動(dòng)到稀疏區(qū)域的分布式協(xié)議，證明了協(xié)議的有效性。在多目標(biāo)跟蹤過(guò)程中，不僅需要對(duì)跟蹤區(qū)域完全覆蓋，還須依據(jù)實(shí)際需要改變某些區(qū)域的覆蓋程度，這時(shí)覆蓋算法需根據(jù)要求作相應(yīng)的調(diào)整。文獻(xiàn)[2]中的覆蓋調(diào)度，能夠自動(dòng)地調(diào)節(jié)成與跟蹤問題相匹配的高程度的覆蓋。在現(xiàn)有多數(shù)文獻(xiàn)中，為實(shí)現(xiàn)好的監(jiān)測(cè)質(zhì)量常采用完全覆蓋，完全覆蓋網(wǎng)絡(luò)需大量節(jié)點(diǎn)同時(shí)工作，會(huì)造成能源浪費(fèi)。因此，不一樣的應(yīng)用可采用不同程度覆蓋。且事實(shí)上，適度的覆蓋盲區(qū)是允許的。

2.2 網(wǎng)絡(luò)連通性

網(wǎng)絡(luò)連通性保證網(wǎng)絡(luò)自身以無(wú)線多跳自組織方式協(xié)同工作，決定了WSN 感知、監(jiān)視、傳感、通信各種服務(wù)質(zhì)量，也是衡量節(jié)點(diǎn)覆蓋調(diào)度的標(biāo)準(zhǔn)。文獻(xiàn)[3]中，根據(jù)構(gòu)造連通支配集(CDS)來(lái)選擇活動(dòng)節(jié)點(diǎn)。采用CDS來(lái)選擇活動(dòng)節(jié)點(diǎn)集，來(lái)確保網(wǎng)絡(luò)連通性。Gupta[4]通過(guò)選擇連通的傳感器節(jié)點(diǎn)路徑來(lái)得到最大化的網(wǎng)絡(luò)覆蓋效果，連通傳感器覆蓋的目標(biāo)是：選擇最小的連通傳感器節(jié)點(diǎn)集合并充分覆蓋WSN區(qū)域。算法中節(jié)點(diǎn)傳感區(qū)域模型是任意凸形區(qū)域，更加符合實(shí)際環(huán)境。

當(dāng)前，在確保網(wǎng)絡(luò)連通性的同時(shí)，需要增加額外的節(jié)點(diǎn)來(lái)維護(hù)網(wǎng)絡(luò)的覆蓋質(zhì)量，從而使網(wǎng)絡(luò)能耗增加。因此，若把覆蓋程度和連通性同時(shí)考慮，會(huì)使得節(jié)點(diǎn)覆蓋更加完善。

2.3 能量有效性

由于傳感器節(jié)點(diǎn)能力有限、節(jié)點(diǎn)數(shù)量大且大多不允許節(jié)點(diǎn)電池更換，因此須采用控制算法減少節(jié)點(diǎn)的能量消耗，延長(zhǎng)整體網(wǎng)絡(luò)的生存時(shí)間。

Gaurav S.Kasbekar[5]等人提出了分布式無(wú)坐標(biāo)的調(diào)度機(jī)制，在保證完全覆蓋下，延長(zhǎng)了網(wǎng)絡(luò)壽命。但文獻(xiàn)中的DLM算法有明顯不足，DLM算法探測(cè)到覆蓋空洞即告終止，即使大量的節(jié)點(diǎn)還有多的能量?jī)?chǔ)備。如果將有能量?jī)?chǔ)備的能量利用起來(lái)，必然會(huì)延長(zhǎng)網(wǎng)絡(luò)的壽命。因此，為提高節(jié)點(diǎn)能量利用率，文獻(xiàn)[6]在DLM算法上進(jìn)行了改進(jìn)，提出一種調(diào)整感知半徑的節(jié)點(diǎn)調(diào)度算法ASR-DLM。設(shè)置小的感知半徑，對(duì)每個(gè)節(jié)點(diǎn)賦權(quán)。選取權(quán)值最大的感知半徑為最優(yōu)感知半徑，達(dá)到最小感知消耗和覆蓋最多交叉點(diǎn)的雙重目標(biāo)。

通過(guò)分析可知,常采用合理組織網(wǎng)絡(luò)節(jié)點(diǎn)的工作狀態(tài)來(lái)降低整個(gè)網(wǎng)絡(luò)能量消耗，從而最小化能耗。

2.4 能耗負(fù)載平衡

在WSN中，若節(jié)點(diǎn)能耗負(fù)載過(guò)大導(dǎo)致節(jié)點(diǎn)過(guò)早死亡，使網(wǎng)絡(luò)監(jiān)控產(chǎn)生盲點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)不能轉(zhuǎn)發(fā)到基站，因此節(jié)點(diǎn)能耗負(fù)載平衡也是覆蓋控制設(shè)計(jì)的目標(biāo)之一。

袁煉勇等人[7]提出在高密度環(huán)境下能量均衡覆蓋控制算法。通過(guò)引入集合論思想，將傳感器節(jié)點(diǎn)分為若干個(gè)節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)集合都能單獨(dú)覆蓋整個(gè)傳感器網(wǎng)絡(luò)區(qū)域。根據(jù)各個(gè)集合當(dāng)前平均能量設(shè)置一個(gè)調(diào)度權(quán)值β，保證任意時(shí)刻只有一個(gè)集合處于工作狀態(tài)，其余節(jié)點(diǎn)集合全處于休眠狀態(tài)，從而大大節(jié)省了節(jié)點(diǎn)能量，避免了不必要的沖突。

文獻(xiàn)[8]中采用能量平衡度作為進(jìn)入睡眠的決策條件。通過(guò)收集到所有鄰居節(jié)點(diǎn)的能量值，計(jì)算出剩余能量方差D(Er)。根據(jù)D(Er)值大小來(lái)反映該節(jié)點(diǎn)所處區(qū)域的能量是否平衡。

目前，覆蓋調(diào)度算法常采用分簇來(lái)實(shí)現(xiàn)節(jié)點(diǎn)能耗均衡。每個(gè)簇所承擔(dān)的覆蓋和傳輸任務(wù)是不均衡的，離基站近的簇承受負(fù)載大，更容易先于離基站遠(yuǎn)的簇死亡。

3 總結(jié)

根據(jù)對(duì)WSN中的節(jié)點(diǎn)調(diào)度機(jī)制分析研究，在下一步的工作中，作者擬對(duì)下列問題進(jìn)行研究，集中體現(xiàn)在：(1)感知模型的完善。使用的節(jié)點(diǎn)感知模型沒考慮傳感器本身和物理環(huán)境的影響和傳感器節(jié)點(diǎn)協(xié)同合作給網(wǎng)絡(luò)帶來(lái)的團(tuán)體力量，未反映網(wǎng)絡(luò)的實(shí)際感知能力，需進(jìn)一步完善。

(2)選擇節(jié)點(diǎn)機(jī)制的改進(jìn)。在隨機(jī)調(diào)度算法中，由于節(jié)點(diǎn)選擇工作時(shí)間段的隨機(jī)性而可能出現(xiàn)某個(gè)時(shí)間段內(nèi)工作節(jié)點(diǎn)過(guò)于集中，必然會(huì)出現(xiàn)另一個(gè)時(shí)間段內(nèi)節(jié)點(diǎn)過(guò)于分散，容易造成覆蓋漏洞增大，影響網(wǎng)絡(luò)整體覆蓋質(zhì)量，因此，需進(jìn)一步合理組織節(jié)點(diǎn)完成覆蓋。

能耗均衡算法改進(jìn)。對(duì)于隨機(jī)分布節(jié)點(diǎn)，達(dá)到完全能耗均衡是不可能的，因此，擬將節(jié)點(diǎn)剩余能量加以考慮，使網(wǎng)絡(luò)達(dá)到次優(yōu)能耗均衡。

[1]Meguerdichian S,Slijepcevic S,Karayan V,et al.Localized algorithms in wireless Ad-hoc networks:location discovery and sensor exposure[A].In ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing[C].2001:106-116.

[2]Li D,Wong K,Hu Y H,et al.Detection,classification and tracking of targets in distributed sensor networks[J].IEEE Signal Processing Magazine,2002,19(2):17-29.

[3]Wang Yu,WangWeizhao,Li Xiangyang.Efficient distributed low-cost backbone information for wireless networks[C].// Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing,2005:2-13.

[4]Gupta H,Das SR,Gu Q.Connected sensor cover:Self-Organization of sensor networks for efficient query execution.In:Gerla M,ed.Proc.of the ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing(MobiHOC).New York:ACM Press,2003:189-200.

[5]Kasbekar G,Bejerano Y,Sarkar S.Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation[C].//Proceeding of the 15th Annual International Conference on Mobile Computing and Networking MobiCom 09.Beijing:ACM Press,2009:169-180.

[6]崔彥新等.無(wú)線傳感器網(wǎng)絡(luò)中一種延長(zhǎng)壽命的覆蓋算法[J].傳感技術(shù)學(xué)報(bào),2010(23)12:1772-1777.

[7]袁煉勇,武俊等.WSN中基于能量均衡的優(yōu)化覆蓋算法[J].計(jì)算機(jī)工程,2008,34(15):100-104.

[8]劉琳嵐,郭少華,陳宇斌.無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)調(diào)度算法的能量平衡研究[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(18):97-99.

田肖，初級(jí)職稱，現(xiàn)供職于南陽(yáng)醫(yī)學(xué)高等?？茖W(xué)校，研究方向：云計(jì)算。