《无线传感器网络中连通与覆盖控制算法研究》由会员分享，可在线阅读，更多相关《无线传感器网络中连通与覆盖控制算法研究（70页珍藏版）》请在金锄头文库上搜索。
1、分类号 UDC 密级 编号 十- 初大学 C E N T R A LS o U T HU N I V E R S I T Y 硕士学位论文 无线传感器网络中连通与覆盖 论文题目 控制算法研究 学科、专业 控制科学与工程 研究生姓名 导师姓名及专业 技术职务 常光强 樊晓平教授 2 0 11 年5 月 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中
2、作了明确的说明。 作者签名： 日期：迎丛年上月粤日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名： 日期：竺年月乒日 点能量有限，为了减少整个网络的能耗，本文提出了一种最小连通覆 盖集求解算法，算法降低了网络覆盖冗余，减少了网络检测过程中的 能量消耗，在不满足通信半径大于2
3、 倍感知半径的情况下，进一步提 出了两种求解最小连通集的算法，虚拟半径调整的连通算法和基于最 小生成树的连通算法。保证了通信半径和感知半径在任何比例下网络 覆盖集的连通性。仿真实验表明，通过本文算法求解的连通覆盖集的 节点数目相对较少了，并保证了整个工作节点网络的连通性。 目前，大部分的无线传感器网络连通与覆盖算法都是依赖节点位 置信息对节点进行冗余判断，忽略了节点的定位也需要浪费很多能耗 的问题。为此，本文提出了一种无位置无关的覆盖控制算法，分析讨 论了节点时钟异步对网络覆盖强度的影响，并通过在生成树中广播时 间同步算法保证了工作节点网络的时间同步，减少了时间异步对网络 覆盖强度的影响。通过
4、实验仿真比较表明，该算法不依赖节点的位置 信息，可以减少网络中工作节点，并保持网络的连通性。 关 关键字：无线传感器网络，覆盖控制，连通，生成树，与位置无 硕士学位论文 A B S T R A C T A BS T R A C T T w oo ft h em o s tf u n d a m e n t a lp r o b l e m si nW i r e l e s sS e n s o rN e t w o r k ( W S N ) a r ec o n n e c t i v i t ya n dc o v e r a g e C o n n e c t i v i t yi n
5、 d i c a t e st h a te v e r y n o d ec a nc o m m u n i c a t ew i t ha n yo t h e rn o d e si nW S N ，w h i c hi st h e p r e c o n d i t i o nt oc r e a t eas e l f - o r g a n i z a t i o nn e t w o r k C o v e r a g em e a n st h a t o v e r a l la r e as h o u l db es e n s e db ya l ln o d e
6、sS Ot h a tt h eo b s e r v e rc a no b t a i n t h ew h o l ei n f o r m a t i o n I nt h et h e s i s ，t h eb a s i cp r i n c i p l ea n dt h er e s e a r c hs t a t u sw o r l d w i d eo f w i r e l e s ss e n s o rn e t w o r ka r ei n t r o d u c e db r i e f l y S i n c et h e r ea r em a n y
7、 r e d u n d a n tn o d e si nW S N ，a n dt h es e n s o rn o d ee n e r g yi sl i m i t e d ，i no r d e r t or e d u c et h ee n e r g yc o n s u m p t i o no ft h ee n t i r en e t w o r k ，t h i st h e s i s p r o p o s e sam i n i m u mc o n n e c t e dc o v e rs e ta l g o r i t h m ，w h i c hr
8、 e d u c e st h e c o v e r a g er e d u n d a n c y ，r e d u c en e t w o r ke n e r g yc o n s u m p t i o ni nt h et e s t i n g p r o c e s s W h e nt h ec o m m u n i c a t i o nr a d i u si sl e s st h a nt h et w ot i m e so f t h e p e r c e p t i o nr a d i u s ，i t f u r t h e rp r o p o s
9、 e st w oa l g o r i t h m st os o l v et h e m i n i m u mc o n n e c t e ds e t ，i e ，t h ec o n n e c t e da l g o r i t h mt oa d j u s tt h ev i r t u a l r a d i u sa n dt h ec o n n e c t e da l g o r i t h mb a s e do nm i n i m u ms p a n n i n gt r e e S o t h ec o m m u n i c a t i o nr a
10、 d i u sa n dp e r c e p t i o nr a d i u so fc o v e r a g ei na n y p r o p o r t i o nc o n n e c t e d n e s so ft h es e tc a nb ee n s u r e d S i m u l a t i o nr e s u l t s s h o wt h a tt h i sa l g o r i t h mn e e d sas m a l ln u m b e ro fn o d e st ot h ec o n n e c t e d c o v e rs e
11、 t ，a n de n s u r e st h ew o r ko ft h en o d en e t w o r kc o n n e c t i v i t y C u r r e n t l y ，m o s ta l g o r i t h m s a r e d e p e n d e n t o nn o d el o c a t i o n i n f o r m a t i o nt od e t e r m i n er e d u n d a n tn o d e s ，i g n o r i n gt h ep o s i t i o n i n go ft h e
12、 n o d e sn e e dt ow a s t eal o to f e n e r g yp r o b l e m s T ot h i se n d ，w ep r o p o s ea n o n - p o s i t i o ni n d e p e n d e n tc o v e r a g ec o n t r o la l g o r i t h m ，a n da n a l y z ea n d d i s c u s st h ea f f e c t i o no ft h en o d ec l o c ka s y n c h r o n o u so
13、nt h es t r e n g t ho f n e t w o r kc o v e r a g e B yt h eb r o a d c a s t i n ga l g o r i t h mi nt h es p a n n i n gt r e e ，t h e t i m es y n c h r o n i z a t i o no fw o r k i n gn o d en e t w o r kC a nb ee n s u r e d ，a n dt h e a f f e c t i o no ft h et i m ea s y n c h r o n i z
14、a t i o no nn e t w o r kc o v e r a g ei n t e n s i t yb e r e d u c e d S i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mi S i n d e p e n d e n to f 硕士学位论文 A B S T R A C T n o d el o c a t i o ni n f o r m a t i o na n dc a nr e d u c et h ew o r ko ft h en e t w o r kn o d e
15、s a n dm a i n t a i nt h en e t w o r kc o n n e c t i v i t y K E YW O R D S ：W i r e l e s sS e n s o rN e t w o r k s ，C o v e r a g ec o n t r o l ， C o n n e c t i v i t y ，S p a n n i n g t r e e ，L o c a t i o nu n a w a r e 目录 2 1 无线传感器网络的基本模型。1 3 2 1 1 感知原型1 3 2 1 2 二元感知模型( B S M ) 1 3 2 1 3 渐近式感知模型( A S M ) 。1 4 2 1 4 概率感知模型( P S M ) 1 4 2 1 5 面向认知过程的感知模型( D S M ) 1 5 2 2 无线传感器网络覆盖控制算法的主要指标1 6 2 3 无线传感器网络连通与覆盖问题分析l7 2 3 1 无线传感器网络中的覆盖问题：1 7 2 3 2 无线传感器网络中的连通问题1 9 2 4 本章小节。2 0 第三章无线传感器网络最小连通覆盖集问题求解算法2 1 3 1 最小连通覆盖集问题描述
