（应用数学专业论文）无线传感器网络中的k覆盖问题.pdf

i ； 镄 11lj一】11 at h e s i si na p k c o v e n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 一- 一 _ 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文 中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经 发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：客俊 日 期：砌孬，厶3 o 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文 的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以 将学位论文的全部或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年口 学位论文作者签名：粒 签字日期：沙占石知 导师签名：舷 签字日期伽& 参如 、l t tj， 一一一。 查! ! 查堂塑士学位论文a b s t 删 。- 一一- k c o v e r a g ep r o b l e mi nw i r e l e s ss e n s o r n e t w or k s a bs t r a c t r e c e n ta d v a n c e si n m i c r o e l e c t r o n i c t e c h n o l o g yh a v em a d ei tp o s s i b l et o c o n s t r u c tc o m p a c ta n d i n e x p e n s i v ew i r e l e s ss e n s o rn e t w o r k s s e n s o rn e t w o r k s h a v eb e e na p p l i e di nv a r i o u sa s p e c t s aw i r e l e s ss e n s o rn e t w o r kc o n s i s t i n go fa l a r g en u m b e ro fs e n s o r sd e p l o y e dr a n d o m l y o n eo ft h em a i np r o b l e m si se n e r g y c o n s e r v a t i o ns i n c em o s to ft h es e n s o r sa r ed e v i c e sw i t hl i m i t e db a t t e r yl i f e i nt h i sp a p e r ，c o v e r i n gs e n s o rl o c a t i o n sa p p r o x i m a t e sc o v e r i n gt h ew h o l ea r e a i no r d e rt op r o l o n gt h en e t w o r kl i f e t i m e ，w eu s u a l l ya c t i v a t et h em i n i m u ms e to f s e n s o r st os a v ee n e r g y i nt h i sp a p e r ，w ec o n s i d e rk - c o v e r a g ep r o b l e ma ss e l e c t i n g ah i t t i n gs e th an e wa p p r o x i m a t ea l g o r i t h mi sp r o p o s e d f i r s t ，w eu t i l i z ea d ju s t i n gs e n s i n gr a n g et oe n s u r ek - c o v e r a g ea n dg i v et w ok i n d s o fa r r a n g i n gi d e a s e c o n d ，a c c o r d i n gt ot w ok i n d so fp r i o r i t ym e n t i o n e di n t h i s p a p e r , t h ea l g o r i t h ms e l e c t ss e n s o rn o d e sw h i c ha r et h em o s tv a l u a b l es e n s o r sa n d m u s ta c t i v a t ef o r k - c o v e r a g e t h e n ，t h ea l g o r i t h ma d d ss u c hs e n s o rn o d e st o h i t t i n gs e thf o rs a v i n g e n e r g y t h i sp a p e rs h o w san e wa l g o r i t h mt oa c h i e v e k c o v e r a g eb a s e do na b o v ed i s c u s s i o n t i m ec o m p l e x i t yo ft h ea l g o r i t h mi sb e t t e rt h a nr k ca l g o r i t h mp r o p o s e d b e f o r e t h et i m ec o m p l e x i t yi so ( n l o g n ) s i m u l a t i o n sr e s u l t sv e r i f yt h e o r e t i c a l a n a l y s i s w o r d s ：w i r e l e s ss e n s o rn e t w o r k ；s a v ee n e r g y ；k - c o v e r a g e ；h i t t i n gs e t ；t i m e c o m p l e x i t y - i i 东北大学硕士学位论文摘要 无线传感器网络中的k 覆盖问题 摘要 近年来，微电子技术的新发展使得建立密集的，价格低廉的无线传感器网 络成为可能。传感器网络可以应用到很多方面。无线传感器网络是由大量的， 任意配置的传感器节点所组成。因为所有的传感器节点的能量都是由电池提供 的，所以节点工作时使用的能量非常有限。在传感器网络中，节省能量是主要 问题之一。 本文把区域覆盖问题近似的看成点覆盖问题。为了延长传感器网络的使用 寿命，通常使得最少的传感器节点处于活跃状态来节省能量。本文将k 覆盖问 题归结为求解最小交叉集合h 并给出了新的近似算法。 首先，我们利用可调的感应半径来达到完全k 覆盖，给出了两类排序的思 想。其次，设计了一种寻找h 中元素的算法。算法根据文中提到的两类优先权， 把最有价值的传感器节点和必须活跃的传感器节点加入到交叉集合h 中，达到 节约能量的目的。在此基础上给出了一种新的k 覆盖算法。 本文算法的时间复杂度比原算法更优，复杂度为o ( n l o g n ) 。仿真结果验证 了理论上的分析。 关键词：无线传感器网络；节约能量；k 覆盖；交叉集合；时间复杂度 i i i 曼 l l p 东北大学硕士学位论文 c a i a l o g u e c a t a l o g u e 独创性声明i a b s t r a c t i i 摘要i i i 1 i n t r o d u c t i o n 。1 1 1b a c k g r o u n d 1 1 2r e l a t e dw o r k 3 1 3b a s i ct h e o r y 6 1 4r e l a t i v ea r t i c l e 9 1 5a r t i c l es t r u c t u r e 9 厂lf 0 东北大学硕士学位论文 c a t a l o g u e 3 3t h en k ca l g o r i t h mp r o c e s s 2 6 3 4t h en k ca l g o r i t h mc o m p l e x i t y 2 8 4 p e r f o r m a n c ee v a l u a t i o n 。3 1 4 1s i m u l a t i o nb yv a r y i n gi n i t i a ls e n s i n gr a n g er 31 4 2s i m u l a t i o nb yv a r y i n gc o v e r a g ed e g r e ek ”一”3 2 4 3s i m u l a t i o nb yv a r y i n gs e n s o r sn u m b e r 3 2 4 4s i m u l a t i o nc o n t r a s t 。3 3 5 c o n c l u s i o n s 3 5 r e f e r e n c e s 。3 7 a c k n o w l e d g e m e n t 4 1 v 、 ； ： 东北大学硕士学位论文 1 i n t r o d u c t i o n 1 1b a c k g r o u n d 1 i n t r o d u c t i o n r e c e n ta d v a n c e si nm i c r o e l e c t r o n i c t e c h n o l o g y h a v em a d ei t p o s s i b l e t o c o n s t r u c tc o m p a c ta n dl o w p o w e r ，l o w - c o s tw i r e l e s ss e n s o r s w i r e l e s ss e n s o r n e t w o r k sc o n s i s to fal a r g en u m b e ro fs m a l l ，a u t o n o m o u ss e n s o r s as e n s o ri s m a d eu po ff o u rb a s i sc o m p o n e n t s ，as e n s i n gu n i t ，ap r o c e s s i n gu n i t ，at r a n s c e i v e r u n i ta n dap o w e ru n i t t h e ym a ya l s oh a v e a p p l i c a t i o nd e p e n d e n ta d d i t i o n a l c o m p o n e n t ss u c ha sal o c a t i o nf i n d i n gs y s t e ma n dap o w e rg e n e r a t o r s oi n w i r e l e s ss e n s o rn e t w o r k s ，a ni m p o r t a n tt a s ki st om o n i t o ra n dc o l l e c tt h er e l e v a n t d a t ai nag e o g r a p h i c a lr e g i o no ras e to ft a r g e t s t h e yc a np r o c e s st h eg a t h e r e d i n f o r m a t i o na n ds e n di tb a c kt ot h eb a s es t a t i o n s o t h e ya r eb e i n gw i d e l y e m p l o y e df o rm i l i t a r yf i e l d s ，n a t i o n a ls e c u r i t y ，e n v i r o n m e n t a lm o n i t o r i n g ，d i s a s t e r p r e v e n t i o na n dr e c o v e r y ，h o m ea p p l i a n c ea n do t h e rc o m m e r c i a la p p l i c a t i o n s 【1 】 si n c es e n s o ri naw i r e l e s ss e n s o rn e t w o r k sa r eo f t e nd e p l o y e di na n a r b i t r a r y m a n n e r ，t h e ya r ed e p l o y e di nar e g i o no fi n t e r e s t i nas e n s o rn e t w o r k ，e a c hs e n s o r 7 ，r i - 东北大学硕士学位论文1 i n t r o d u c t i o n f e a t u r eo fs e n s o rn e t w o r k si st h ec o o p e r a t i v ee f f o r to fs e n s o rn o d e s s e n s o rn o d e s a r ef i t t e dw i t ha no n - b o a r dp r o c e s s o r o n eo ft h em o s ti m p o r t a n tc o n s t r a i n t so n s e n s o rn o d e si st h el o wp o w e rc o n s u m p t i o nr e q u i r e m e n t s e n s o rn o d e s c a r r y l i m i t e d ，g e n e r a l l yi r r e p l a c e a b l e ，p o w e rs o u r c e s t h e r e f o r e ，w h i l et r a d i t i o n a l n e t w o r k sa i mt oa c h i e v e h i g hq u a l i t yo fs e r v i c ep r o v i s i o n s ，s e n s o rn e t w o r k p r o t o c o l sm u s tf o c u sp r i m a r i l yo np o w e rc o n s e r v a t i o n s i n c eal a r g en u m b e ro f s e n s o rn o d e sa r ed e n s e l yd e p l o y e d ，n e i g h b o rn o d e sm a yb ev e r yc l o s et oe a c ho t h e r h e n c e ，m u l t i - h o pc o m m u n i c a t i o ni ns e n s o rn e t w o r k si se x p e c t e dt oc o n s u m el e s s p o w e rt h a nt r a d i t i o n a ls i n g l eh o pc o m m u n i c a t i o n f u r t h e r m o r e ，t h et r a n s m is s i o n p o w e rl e v e l sc a nb ek e p tl o w ，w h i c hi sh i g h l yd e s i r e di nc o v e r to p e r a t i o n s si n c es e n s o r sh a v ev e r yl i m i t e de n e r g ys u p p l y ，i ti su s u a l l yh a r dt or e c h a r g et h e b a t t e r ya f t e rd e p l o y m e n t ，e i t h e rb e c a u s et h ed e p l o y m e n ta r e ai sh o s t i l e ，o rb e c a u s e t h en u m b e ro fs e n s o rn o d e si st o ol a r g e o n c ed e p l o y e d ，aw i r e l e s ss e n s o rn e t w o r k i se x p e c t e dt ok e e pw o r k i n gf o ral o n gt i m e t h e r e f o r e ，c o n s e r v i n ge n e r g ya n d p r o l o n g i n gt h es e n s o rn e t w o r kl i f e t i m ei sv e r yi m p o r t a n ta n di n t e g r a n t s o ，o n e i m p o r t a n tp r o b l e mt h a ta r i s e si nh i g h d e n s i t ys e n s o rn e t w o r k si sd e n s i t yc o n t r 0 1 a f u n c t i o nt h a tc o n t r o l st h ed e n s i t yo fw o r k i n gs e n s o r st oac e r t a i nl e v e l 【2 】t h e p u r p o s eo fd e n s i t yc o n t r o li ss a v i n ge n e r g yf o rt h ea c c e p t a b l eq u a l i t yo fs e r v i c e s p e c i f i c a l l y ，d e n s i t yc o n t r o le n s u r e so n l yas u b s e to fs e n s o r so p e r a t e si na c t i v e m o d e t h eo t h e rs e n s o rn o d e sa r es c h e d u l e dt os l e e p ( o re n t e rap o w e rs a v i n g m o d e ) w h i l et h er e m a i n i n ga c t i v en o d e sp r o v i d ec o n t i n u o u ss e r v i c e m i n i m i z i n g l 疆 呵 ： e n e r g yc o n s u m p t i o nt op r o l o n gt h es y s t e ml i f e t i m ei sam a jo rd e s i g no b je c t i v ef o r s e n s o rn e t w o r k ss i n c es e n s o r sn e e dt oo p e r a t ef o ra l o n gt i m eo nb a t t e r yp o w e r i f a l lt h es e n s o r sn o d e ss i m u l t a n e o u s l yo p e r a t ei na c t i v em o d e ，a ne x c e s s i v ea m o u n t o fe n e r g yi sw a s t e da n dt h ed a t ac o l l e c t e di sh i g h l yc o r r e l a t e da n dr e d u n d a n t t h u s ， m a x i m i z i n gt h en e t w o r kl i f e t i m ec a nb ea c h i e v e db y s c h e d u l i n gs o m en o d e st o s l e e pi e ，ap o w e rs a v i n gm o d e ，w h i l et h er e m a i n i n ga c t i v en o d e sc a ns t i l lp r o v i d e c o n t i n u o u ss e r v i c e a ni m p o r ti s s u ei st om a i n t a i nt h ef i d e l i t yo ft h es e n s e dd a t a w h i l em i n i m i z i n ge n e r g yu s a g ei nt h ew i r e l e s ss e n s o rn e t w o r k s e n e r g yc a nb e s a v e di ft h e s ea c t i v i t i e sa r eu s e do n l yt ot h ee x t e n ta b s o l u t e l yn e e d e d ，a n dn om o r e 2 i s oab a s i sp r o b l e mi st om i n i m i z et h en u m b e ro fn o d e st h a tr e m a i na c t i v e ，w h i l e s t i l la c h i e v i n ga c c e p t a b l eq u a l i t yo fs e r v i c ef o ra p p l i c a t i o n s 1 2r e l a t e dw o r k r e c e n t l y ，t h e r eh a sb e e nal o to fr e s e a r c hd o n et oa d d r e s st h ec o v e r a g ep r o b l e m i nw i r e l e s ss e n s o rn e t w o r k t h el i f e - t i m eo ft h en e t w o r ki sg e n e r a l l yp r o l o n g e db y s c h e d u l i n gs l e e pi n t e r v a l sf o rs o m es e n s o r s ，m e a n w h i l et h ec o n t i n u o u ss e r v i c ei s p r o v i d e db yt h ea c t i v es e n s o r s ( 3 ，4 】) i n 5 】，t h ea u t h o r sp r o p o s e dar a n d o m i z e d ， s i m p l es c h e d u l i n gf o rd e n s ea n dm o s t l ys l e e p i n gs e n s o rn e t w o r k s i nt h ep r o p o s e d r a n d o m i z e di n d e p e n d e n ts l e e p i n ga l g o r i t h m ，t i m ei sd i v i d e di n t o p e r i o d s t o h a n d l et h eb a s i cc o v e r a g ep r o b l e mt h ea u t h o r si n 【6 p r o p o s e dar o l e a l t e r n a t i n g ， c o v e r a g e 。p r e s e r v i n g ，c o o r d i n a t e ds l e e pa l g o r i t h m e a c hs e n s o rs e n d sam e s s a g e p e r i o d i c a l l y t oi t s n e i g h b o r h o o dc o n t a i n i n gi t sn e c e s s a r yi n f o r m a t i o n t h e c o o r d i n a t e ds l e e pi sm o r er o b u s ta n dr e d u c e st h ed u t yc y c l eo fs e n s o r sc o m p a r e d t ot h er a n d o ms l e e pa l g o r i t h m ，a n di tg u a r a n t e e s1 - c o v e r a g ei nt h en e t w o r k i n 【7 】， t h ea u t h o r sf i r s ti n t r o d u c e d t h ep a r t i a l c o v e r a g ec o n c e p ta n da n a l y z e d i t s p r o p e r t i e sf o rt h ef i r s tt i m ei no r d e rt op r o l o n gt h en e t w o r kl i f e t i m e t h e nt h e y p r e s e n t e dah e u r i s t i ca l g o r i t h mw h i c ht a k e si n t oa c c o u n tt h ep a r t i a lc o v e r a g ea n d s e n s o rc o n n e c t i v i t y s i m u l t a n e o u s l y t h e ys e l e c t e dac o n n e c t i v e c a n d i d a t ep a t h a c c o r d i n gt ot h et w oc o n d i t i o n s ，t h ea v e r a g eg a i na n dt h e - c o v e r a g eg a i n s i n c et h es e n s o r sa r ep e r f o r m i n gb o t hs e n s i n ga n dc o m m u n i c a t i o nt a s k st h e m a i np r o b l e m so fs e n s o rn e t w o r k sa r ea s s o c i a t e dt ot h e s et w oa c t i v i t i e s 8 1 t h e s e n s o rn e t w o r ks h o u l db ec a p a b l eo ft a k i n gm e a s u r e m e n ti nt h et a r g e ta r e aa n d t r a n s m i t t i n gt h em e a s u r e dv a l u e st os i n kn o d e s i n 9 】t h ea u t h o r sp r e s e n t e dt h e g r a p hi sc o n n e c t e di ft h er7 2 r ( ri st h ec o m m u n i c a t i o nr a n g ea n d ri st h es e n s i n g r a n g e ) i n 【10 ，t h ea n a l y t i c a lr e s u l t sa n dt h ee x i s t i n ga l g o r i t h m sw h i c hc o n s t r u c t t h ec o n n e c t e dd o m i n a t i n gs e t ，a ne n e r g ye f f i c i e n tc o n n e c t e dc o v e r a g ep r o t o c o l ( e e c c p ) i sp r o p o s e d t h ep r o p o s e dc o n n e c t e dc o v e r a g ep r o t o c o lc a ne f f e c t i v e l y m a i n t a i nb o t hh i g hq u a l i t ys e n s i n gc o v e r a g ea n dc o n n e c t i v i t yf o ral o n gt i m e s o m ea r t i c l e sc o n s i d e rt h ed i s c r e t et a r g e t s i n 【11 】，t h ea u t h o r sg e n e r a l i z e dt h e s l e e po ra c t i v em o d eb ya d ju s t i n gs e n s i n gr a n g et o m a x i m i z et o t a ln u m b e ro f r o u n d sa n dp r e s e n t e dad i s t r i b u t e dh e u r i s t i ct o a d d r e s st h ec o n n e c t e dc o v e r a g e p r o b l e m i n 【12 ，t h e a u t h o r sc o n s i d e r e dt h ep a r t i a lt a r g e t a r e af o re f f i c i e n tq u e r y e x e c u t i o n t h e yd e s i g n e da n da n a l y z e da l g o r i t h m sf o rs u c hs e l f - o r g a n i z a t i o no fa s e n s o rn e t w o r kt or e d u c ee n e r g yc o n s u m p t i o n t h e yd e v e l o p e dt h en o t i o no fa c o n n e c t e ds e n s o rc o v e ra n dd e s i g n e dac e n t r a l i z e da p p r o x i m a t i o na l g o r i t h mt h a t c o n s t r u c t sat o p o l o g yi n v o l v i n gan e a r - o p t i m a lc o n n e c t e ds e n s o rc o v e r t h e y d i v i d e dt h eg i v e nq u e r yr e g i o ni n t om a n yv a l i ds u b - e l e m e n t s t h e nt h e yd e s i g n e d ag r e e d ya l g o r i t h mt os e l e c tac o n n e c t e ds e n s o rc o v e ro fn e a r o p t i m a ls i z e t h e a l g o r i t h mw o r k sb yi t e r a t i v e l ys e l e c t i n gac o m m u n i c a t i o np a t h o fs e n s o r st h a t c o n n e c t sa na l r e a d ys e l e c t e ds e n s o rt oap a r t i a l l yc o v e r e ds e n s o ra n dt h e na d d i n g t h es e l e c t e dp a t ht ot h ea l r e a d ys e l e c t e ds e n s o r s a tt h es a m et i m et h es e l e c t e d p a t hc o v e r st h em o s tv a l i ds u b e l e m e n t s t h e ya l s od e v e l o p e d ad i s t r i b u t e d s e l f - o r g a n i z a t i o nv e r s i o no ft h ea p p r o x i m a t i o na l g o r i t h ma n dp r o p o s e ds e v e r a l o p t i m i z a t i o n st or e d u c et h ec o m m u n i c a t i o no v e r h e a do f t h ea l g o r i t h m t h e r ea l s oh a sb e e nal o to fr e s e a r c hd o n et oa d d r e s st h em u l t i p l ep o i n t c o v e r a g e ，i e ，k - c o v e r a g e ，i nw i r e l e s ss e n s o rn e t w o r k s i n 【13 ，t h ea u t h o r sf i r s t f o r m a l i z e dt h ek ( c o n n e c t e d ) c o v e r a g es e t ( k c c s k - c s ) p r o b l e m si nt e r m so f l i n e a rp r o g r a m m i n g ，a n da na p p r o x i m a t i o na l g o r i t h m ( l p a ) i n t e g e rp r o g r a m m i n g w a sd e v e l o p e df o rt h ek c sp r o b l e m t h eg l o b a ls o l u t i o nc o n s t r u c t e dar e l a x e d l i n e a r p r o g r a m m i n g t o o u t p u ta p p r o x i m a t es o l u t i o n t h e yp r o p o s e d t w o n o n g l o b a lk - c o v e r a g es o l u t i o n s o n e ( c k a ) i sq u a s i - l o c a lc l u s t e r b a s e dw i t ha d e t e r m i n i s t i cb o u n db yu s i n gac l u s t e r i n ga l g o r i t h ma n dag a t e w a ys e l e c t i o n ， c 东北大学硕士学位论文 1 i n t r o d u c t i o n a p p r o a c h ，t h eo t h e r ( p k a ) i sl o c a l i z e dw i t hap r o v e np r o b a b i l i s t i eb o u n db y c o m p a r i n gt h en e i g h b o rs e n s o r sp r i o r i t y i n 14 ，t h ea u t h o r sp r o p o s e dc e n t r a l i z e d a n dd i s t r i b u t e da l g o r i t h m st os o l v et h ek c o v e r a g es e n s i n gp r o b l e ma n dm a x i m i z e n e t w o r kl i f e t i m e w h e n p h y s i c a l l yp o s s i b l e ，t h ep r o p o s e dr o b u s tc o n t r o l l e d g r e e d ysl e e pa l g o r i t h mp r o v i d e sg u a r a n t e e ds e r v i c ei n d e p e n d e n t l yo fn o d ea n d c o m m u n i c a t i o ne r r o r si nt h en e t w o r k i n 【15 ，t h ea u t h o r sp r o p o s e ds o l u t i o n st o f o r m i n gk - c o n n e c t e dc o v e r a g eo ft a r g e t sw i t ht h em i n i m a ln u m b e ro fa c t i v en o d e s t h e yp r o p o s e dt w oh e u r i s t i ca l g o r i t h m st os o l v et h ep r o b l e m t h e r ea r et w os t e p s i nt sa l g o r i t h m ：( 1 ) c o n s t r u c tas e tc o v e r ，a n d ( 2 ) c o n n e c ts e ti n t ok - c o n n e c t e d s u b g r a p hb a s e do nt h es t e i n e rt r e ep r o b