（运筹学与控制论专业论文）分布式传感器网络中数据融合的移动代理路由问题.pdf

山东大学硕士学位论文 摘要 最近在微电子机械系统( m e m s ) 和无线通信技术领域的进步使得人们对一 种新型的网络系统一传感器网络的研究越来越多 1 】【2 】 3 】【4 】。这种网络是由一些集 成了传感、计算、通讯甚至移动能力的微小传感器节点组成。 一个传感器网络通常会由大量的配置于探测区域的传感器节点构成，这些传 感器节点的位置不需要事先确定，这就使得其可以随机部署于难以接近的地形或 者灾难救援中，另一方面，这意味着传感器网络的协议和算法要有自组织的能力。 在这种网络中多传感器节点的合作对于解决单个传感器节点的有限的传感、处理 能力，特别是有限的能量供应是最本质的，并且可以提高决策过程的可信度。现 在传感器网络已经得到了越来越多的应用，其中包括在军事，医疗，家庭中的应 用。 在通常的分布式网络中，低带宽的无线通信是传感器节点之间通讯的唯一方 式。由于这些传感器节点通常是处理能力，带宽有限的微电源装置，这就使得电 源消耗必须保持在足够小的水平以保证完成正常的通讯任务。 在传统的分布式网络大都是基于一个共同的网络计算模型：c s 模型，但是 c s 模型并不适合于分布式传感器网络中的数据融合。c s 模型存在网络流量大， 不能实时的响应负荷变化等缺点。为了克服传统分布式网络的这些不足，一种称 作基于移动代理的分布式网络( m a d s n s ) 被提出来【1 3 】。这种网络对于网络带 宽需求大大少，有着很强的网络稳定性，可扩展性。 m a d s n s 中一个重要的问题就是移动代理路由的计算问题。在文献 1 8 】中作 者针对一种特殊的情形目标识别与追踪环境下的m a d s n s ，研究了相应的 移动代理路由问题。我们将m a d s n s 中的移动代理路由问题( m a r p ) 表示为 一个组合优化问题。问题的目标是要找一条路由并使得路径损耗和节点损耗尽量 小。我们指出m a r p 问题是一个n p c 问题并且等价于一个特殊的m t s p 问题。 针对问题的特点，我们提出了一种改进的蚁群算法b b - a s 来求解该问题。 蚁群算法是由m d o r i g o 等 2 8 2 9 3 0 3 1 于上世纪9 0 年代提出的一类 群智能优化算法，在解决传统优化方法难以奏效的具有n p h a r d 特性的组合优化 问题，如中取得了令人鼓舞的效果，国际著名杂志( n a t u r e ) ) 曾经多次对蚁群算 山东大学硕士学位论文 法进行过报道 3 2 3 3 3 4 。目前，蚁群算法在理论和应用上都取得了很大进展， 成为蓬勃发展的热点研究课题，但是蚁群算法也存在算法收敛慢等表现不如时兴 的算法的缺点。针对基本蚁群算法收敛速度慢不适应于像m a r p 等问题求解的缺 点，本文中，我们提出了一种基于产生概率和转移概率合成的转移概率计算，基 于临域信息的初始化信息紊加权，混合信息素更新等改进策略，结合2 - o p t 局部 搜索优化提出了b b a s 算法。在与当前比较优秀的m m a s 的仿真比较显示该算 法收敛速度大大提高，而且求解质量也很令人满意。通过对算法流程的改进我们 又将b b a s 降低到与a s 算法相同的水平，因此b b a s 算法比较适合于像m a r f 等实时应用。 关键词：传感器网络：移动代理；分布式网络；t s p 问题；蚁群算法 山东大学硕士学位论文 a b s t r a c t r e c e n ta d v a n c e si nt h ef i e l d so fm i c r oe l e c t r om e c h a n i c a ls y s t e m ( 姬m s ) a n dw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e sh a v ed i r e c t e dr e s e a r c ht o w a r d s t h ed e v e l o p m e n to fan e wg e n e r a t i o nn e t w o r ks y s t e m - - t h es e n s o rn e t w o r k 1 2 3 4 i ti sc o m p o s e do fs m a l ls e n s o rn o d e si n t e g r a t i n gt h e c a p a b i l i t i e so fs e n s i n g ，c o m p u t i n g ，c o m m u n i c a t i o n ，a n de v e nm o b i l i t y as e n s o rn e t w o r kisc o m p o s e do fal a r g en u m b e ro fs e n s o rn o d e st h a t a r ed e n s e l yd e p l o y e de i t h e ri n s i d et h ep h e n o m e n o no rv e r yc l o s et oi t t h ep o s i t i o no fs e n s o rn o d e sn e e dn o tb ee n g i n e e r e do rp r e d e t e r m i n e d t h i s a l l o w sr a n d o md e p l o y m e n ti ni n a c c e s s i b l et e r r a i n so rd i s a s t e rt e l i e f o p e r a t i o n s o nt h eo t h e rh a n d ，t h i sa l s om e a n st h a ts e n s o rn e t w o r k p r o t o c o l sa n da l g o r i t h m sm u s tp o s s e s ss e l f o r g a n i z i n gc a p a b i l i t i e s t h e a b o v ed e s c r i b e df e a t u r e se n s u r eaw i d er a n g eo fa p p l i c a t i o n sf o rs e n s o r n e t w o r k s s o m eo ft h ea p p l i c a t i o na r e a sa r eh e a l t h ，m i l i t a r y ，a n dh o m e i nm i l i t a r y ，f o re x a m p l e ，t h er a p i dd e p l o y m e n t ，s e l f - o r g a n i z a t i o n ，a n d f a u l tt o l e r a n c ec h a r a c t e r i s t i c so fs e n s o rn e t w o r k s m a k et h e mav e r y p r o m i s i n gs e n s i n gt e c h n i q u e f o r m i l i t a r y c o m m a n d ， c o n t r o l ， c o m m u n i c a t i o n s ，c o m p u t i n g ，i n t e l l i g e n c e ，s u r v e i l l a n c e ，r e c o n n a i s s a n c e ， a n dt a r g e t i n gs y s t e m s i nh e a l t h ，s e n s o rn o d e sc a na l s ob ed e p l o y e dt o m o n i t o rp a t i e n t sa n da s s i s td i s a b l e dp a t i e n t s s o m eo t h e rc o m m e r c i a l a p p li c a t i o n si n c l u d em a n a g i n gi n v e n t o r y ，m o n i t o r i n gp r o d u c tq u a l i t y ，a n d m o n it o r i n gd is a s t e ra r e a s t h e s es e n s o r sa r et y p i c a l l yl i g h t w e i g h tw i t hl i m i t e dp r o c e s s i n gp o w e r ， b a t t e r yc a p a c i t y ，a n dc o m m u n i c a t i o nb a n d w i d t h t h ec o m m u n i c a t i o nt a s k s c o n s u m et h e1 i m i t e dp o w e ra v a i l a b l ea ts u c hs e n s o rn o d e sa n d ，t h e r e f o r e ， i no r d e rt oe n s u r et h e i rs u s t a i n e do p e r a t i o n s ，t h ep o w e rc o n s u m p t i o nm u s t b ek e p tt oam i n i m u m m o s td i s t r i b u t e ds e n s o rn e t w o r k su s eac o m m o nn e t w o r kc o m p u t i n gm o d e l ： t h ec ll e n t s e r v e r m o d e l h o w e v e r ，t h ec ll e n t s e r v e rm o d e li sn o t a p p r o p r i a t ef o rd a t ai n t e g r a t i o ni nd s n s f i r s t ，t h ed a t ai n t e g r a t i o na t m 山东大学硕士学位论文 t h es e r v e rr e q u i r e sd a t at r a n s f e rf r o ml o c a ls e n s o rn o d e s w h e nt h es i z e o fd a t af i l ei sl a r g ea n dt h en u m b e ro fs e n s o rn o d ei sb i g ，t h en e t w o r k t r a f f i cc a nb ee x t r e m e l yh e a v y ，r e s u l t i n gi np o o rp e r f o r m a n c eo ft h e s y s t e m s e c o n d ，t h ec l i e n t s e r v e rb a s e dd s nc a n n o tr e s p o n dt ot h el o a d c h a n g i n gi nr e a lt i m e w h e nm o r es e n s o r sa r ed e p l o y e d ，i tc a n n o tp e r f o r m l o a db a l a n c i n gw it h o u tc h a n g i n gt h es t r u c t u r eo ft h en e t w o r k t om e e t t h e s en e wc h a l l e n g e s ，t h ec o n c e p to fm o b il ea g e n t b a s e dd i s t r i b u t e d s e n s o rn e t w o r k s ( m a d s n s ) h a sb e e np r o p o s e db yq ie ta 1 1 3 m a d s no f f e r s t h ef o l l o w i n g i m p o r t a n tb e n e f i t s ：n e t w o r kb a n d w i d t hr e q u i r e m e n ti s r e d u c e d ：b e t t e rn e t w o r ks c a l a b i l i t y ：e x t e n d e de x t e n s i b i l i t y ：s t a b i l i t y w s qe ta 1 1 3 3p r o p o s e dt h em o b i l ea g e n tr o u t i n gp r o b l e m ( m a r p ) i ns o m e p r a c t i c a lm a d s n sd e p l o y e df o rt a r g e td e t e c t i o na n dt r a c k i n g w ef o r m u l a t e t h em o b i l ea g e n tr o u t i n gp r o b l e m ( 知姨r p ) i na nm a d s na sac o m b i n a t o r i a l o p t i m i z a t i o np r o b l e mi n v o l v i n gt h ec o s to fc o m m u n i c a t i o na n d t h ep a t hl o s s d u et ow i r e l e s s p r o p a g a t i o n t h eo v e r a l lr o u t i n go b j e c t i v e i st o m i n i 。m i z i n gt h ep o w e rn e e d e df o rc o m m u n i c a t i o na n dt h ep a t hl o s s e s w e s h o wm a r pt ob en p c o m p l e t eb yu s i n gar e d u c t i o nf r o mav a r i a t i o no ft h e m u l t i t r a v e l i n gs a l e s m a np r o b l e m ( m t s p ) w et h e np r o p o s ea na p p r o x i m a t e s o l u t i o nb a s e do n a ni m p r o v e da n ts y s t e m ( a s ) ， a n ts y s t e ma l g o r i t h m ， o r i g i n a l l yi n t r o d u c e db ym d o r i g oi n 2 8 2 9 3 3 0 3 1 i nt h e1 9 9 0 s ，i san e wc o o p e r a t i v es e a r c ha l g o r i t h m i n s p i r e db yt h eb e h a v i o ro fr e a la n t s g r e a tp r o g r e s sh a sb e e nm a d ei n t h e o r e t i ca n da p p l i e dr e s e a r c ho ft h ea n ts y s t e m i tg a v ee n c o u r a g i n g r e s u l t s ，y e ti t sp e r f o r m a n c ew a sn o tc o m p e t i t i v ew i t hs t a t eo ft h ea r t a l g o r i t h m sf o rt h et s p w ep r o p o s e da ni m p r o v e dv e r s i o no fa s ，w h i c h s i g n i f i c a n t l ys p e e d su pt h ec o n v e r g e n c er a t eo ft h es e a r c h i n gf o rs o l u t i o n s i m u l a t i o nr e s u l t sf o rt a p sw i t hd i f f e r e n tn o d es i z e sa n dn o d e d i s t r i b u t i o n ss h o wt h a to u ra l g o r i t h mh a ss u p e r i o rp e r f o r m a n c e sc o m p a r e d t o 脚a s i v k e y w o r d s ：s e n s o rn e t w o r k s ：m o b i la g e n t ：d s n s ：t s p ：a s 山东大学硕士学位论文 曼鼍詈詈詈皇喜量皇鼍i 。 i i 詈詈皇皇毫! ! 暑量鼍皇皇! 鼍皇詈曼詈苎! ! 曼曼曼! ! ! 鼍詈鼍詈詈鼍皇曼! 詈! ! 詈詈皇曼皇皇曼! 詈皇詈鼍量皇 主要符号说明 t s p 问题的点的个数 蚁群算法中人工蚂蚁的个数 t 时刻在i j 连线上的信息素量 与问题相关的启发式信息 时刻t ，人工蚂蚁k 从城市i 转移到城市j 的概率 当前蚂蚁所走过的城市 信息素量的重要程度 启发式因子的重要程度 第k 只蚂蚁在本次循环中留在路径( f ，) 上的信息量 路径上信息素的蒸发系数 第k 只蚂蚁在本次循环中所走过的路径的长度 i 当前允许转移集合 i 的w i n 窗口 t 时刻从i 到j 的一步转移概率 t 时刻从i 到j 的产生概率 t 时刻从i 到j 的接受概率 本代最优解长度 当前最优解长度 v ， o 力 o o n 删删啪 毗口 p 嵋p k k u 矿矿 r k k 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：王至：至皇二 日 期o 毋。妒。m 期：一乏! 竺：鲨 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：乏查兰至= 一导师 期：兰! ! 壁：坠19 山东大学硕士学位论文 第1 章前言 2 1 研究背景 最近在微电子机械系统( m e m s ) 和无线通信技术领域的进步使得人们对 一种新型的网络系统传感器网络的研究越来越多 1 】 2 】 3 】【4 】。这种网络是由一些 集成了传感、计算、通讯甚至移动能力的微小传感器节点组成。【1 】 2 】提到每个 传感器节点由五个部分组成，即电源、传感器、c p u 、内存和一个通讯单元。它 还可以包含一个全球定位系统( g p s ) 接收器用来确定其位置。图2 1 1 显示了了 一个传感器节点的组成，其中虚线表示可选组件： 图2 1 1 传感器节点组成 发电装置 ； 一 i 一个传感器网络通常会由大量的配置于探测区域的传感器节点构成，这些传 感器节点的位置不需要事先确定，这就使得允许随机部署于难以接近的地形或者 灾难救援中。另一方面，这意味着传感器网络的协议和算法要有自组织的能力。 在这种网络中多传感器节点的合作对于解决单个传感器节点的有限的传感，处理 能力，特别是有限的能量供应是最本质的，并且可以提高决策过程的可信度。现 在传感器网络已经得到了越来越多的应用，其中包括在军事，医疗，家庭中的应 用。例如在军事中，传感器网络的快速配置，自组织和容错特性使得它成为一种 非常有前途的传感技术，并且在军事指挥、控制、通讯、计算、智能、侦察、目 山东大学硕士学位论文 标识别系统中得到应用。在医疗领域中，传感器节点能够用来监控病人以及用来 帮助残疾人。其他一些应用包括库存管理，产品质量控制和受灾范围监测。 在通常的分布式网络中，低带宽的无线通信是传感器节点之间通讯的唯一方 式。由于这些传感盎节点辽常早处珲能力，带宽有限的微电源装置，这就使得电 源消耗必须保持在足够小的水平以保证完成正常的通讯任务。 同传统的有线通信相比，分布式传感器网络的设计更具挑战性。例如，待收 集的原始数据更大，通讯带宽更小，环境更不可靠以致不可靠的网络连接，背景 噪声并且增加了输入原始数据的出错率。传统分布式网络大都基于一个共同的网 络计算模型：c s 模型。但是c s 模型并不适合于分布式传感器网络中的数据融 合，为克服传统分布式网络的这些不足，一种称作基于移动代理的分布式网络 ( m a d s n s ) 被提出来【1 3 】。基于代理的系统 5 】是一种新的软件技术，这种技术 将人工智能( 鲇) 和面向对象的分布式计算技术结合起来。在分布式网络中引入 移动代理技术，使得网络带宽需求大大减少，网络稳定性大大增强，并且提高了 系统的可扩展性。 m a d s n s 网络中一个重要的问题就是移动代理的路由问题，即确定移动代 理在数据融合过程中对于各目标节点的访问次序，这直接决定了系统在进行数据 融合过程中的能量损耗，从而影响到整个系统的性能。在本文中我们来研究一种 比较通用的情况，即簇内所有节点的数据都被融合的情况。相应的移动代理路由 问题就是要为移动代理寻找一条路径，使得每个节点被访问一次，并且最小化系 统的能耗。我们将m a d s n s 中的移动代理路由问题( 1 厦a r p ) 表示为一个组合 优化问题。问题的目标是要找一条路由使得路径损耗和节点损耗尽量小。我们指 出m 6 姻问题是一个n p c 问题并且等价于一个起始点固定的m t s p 问题。如 何高效的确定移动代理的路由呢，我们提出了用蚁群算法来解决这个问题，通过 对基本蚁群算法进行了改进提高了算法的收敛速度，使得算法的实际应用能力大 大加强。仿真结果显示该算法有着良好的表现。 2 2 发展及研究现状 t s p 是组合优化领域中的一个经典问题，它涉及求多个变量的函数最小值， 目前尚无一个多项式时间算法，t s p 已经被证明为n p - c 问题 5 5 。假如需要求解 一个n = 1 0 0 的t s p 问题，即使使用了现有的或者是规划中的最强大的超级计算机也 2 山东大学硕士学位论文 不可能求出其真正的最小值。以国内现有最快的银河计算机为例，它每秒可以进 行大约一万亿次计算，假设一次计算就可以搜索到一条路径，这样也要用 2 9 6 x 1 0 1 3 6 年。这显然是不可能完成的任务，因此人们转而探索近似解法。对于 t s p 问题的近似求解有很多算法，。包括穷举搜索法、贪心法、动态规划法等。但 是这些算法难以在多项式时间内获得问题的解，对大规模问题，已有的能在可接 受计算时间内得到近似优化解的高效算法包括局域搜索算法( 如2 - o p t 2 0 ， 3 - o p t 2 1 等) 和宏启发式算法如遗传算法 2 2 ，模拟退火 2 3 ，蚁群算法 2 4 ， 禁忌搜索 2 5 以及进化算法 2 6 等。 蚁群算法是一种基于仿生原理，通过模拟简单生物体的群体行为的现代启发 式优化方法，是一种群智能( s w a r mi n t e lli g e n c e ) 优化算法。生物学家在对社会 性昆虫的群体行为研究中发现，昆虫个体的行为能力有限，且随机性大，但整个 群体却表现出高度的自组织性。如单只蚂蚁功能简单，但蚂蚁群体却能够完成诸 如筑巢、觅食、迁徙、清扫蚁巢等复杂任务 2 7 ；蜜蜂群体、鸟群也都具有类似 特征。这些自然现象引起了人们的极大兴趣，并相继提出了群智能优化算法，如 模拟生物蚁群觅食能力的蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ， a c o ) 2 8 3 2 9 3 0 3 1 。 蚁群算法是由d o r i g o 等 2 8 2 9 3 0 3 1 于上世纪9 0 年代提出的一类群 智能优化算法，在解决传统优化方法难以奏效的具有n p - h a r d 特性的组合优化问 题中取得了令人鼓舞的效果，受到学术界和工业界的广泛关注，国际著名杂志 n a t u r e 曾经多次对蚁群算法进行过报道 3 2 3 3 3 4 3 。尽管蚁群算法远未像 遗传算法、模拟退火等算法那样具有相对坚实的数学基础，但从其应用效果来看， 这种模仿自然生物系统的新颖寻优思想无疑具有十分光明的前景。目前，蚁群算 法在理论和应用上都取得了很大进展，成为蓬勃发展的热点研究课题。 基本蚁群算法有着许多的优点，但是也存在着一些缺点如求解速度慢，解的 随机性比较大，参数选择缺少相关的理论依据，经验性较强等。针对蚁群算法的 这些不足之处，许多学者提出了最蚁群算法的改进策略。其中最著名的包括蚁群 算法创始人d o r i g o 等提出的蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 3 7 ，德国学 者t s t u t z l e 等提出的最大一最小蚂蚁系统( m a x m i na n ts y s t e m ，m m a s ) 3 8 。 后来的许多对于蚁群算法的改进都是基于这两个算法进行的。 山东大学硕士学位论文 2 3 本文主要研究内容和本文组织结构 本文首先介绍了传统分布式网络以及移动代理传感器网络，对二者进行了比 较，然后对移动代理传感器网络提出 ，一般情况的移动代理路由问题( m a r p ) ， 并将其归结为一个起始点固定的m t s p 问题。论文的主要部分集中在对于当前 蚁群算法的分析以及改进，以及改进算法的性能分析。 本文正文由五部分组成，第一章前言主要介绍了移动代理传感器网络以及蚁 群算法的背景知识；第二章介绍了传统的分布式网络和移动代理传感器网络，分 析了二者的优缺点，并提出移动代理路由问题( m a r ) ；第三章首先介绍了基 本蚁群算法及当前的一些对于蚁群算法的改进；第四章给出了我们对于蚁群算法 的改进算法b b a s ，并且通过对算法的仿真对算法进行了评价；第五章是总结， 以及对今后研究的展望。 4 山东大学硕士学位论文 第2 章m a d s n s 介绍分析及m a r p 提出 2 1d s n 及m a d s n s 的介绍及分析 2 2 1 传统的分布式网络介绍及其缺点分析 传统的分布式网络，例如，d e b r u i j n 网络 7 】，平顶树网络 6 】【8 】，多代理融 合网络 7 】，以及分级网络【9 】。这些模型都是基于一个共同的网络计算模型：c s 模型，这个模型支持许多分布式系统，例如移动进程呼叫( r p c ) 【1 0 】，c o m m o n o b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ( c o r b a ) 11 1 1 1 2 1 等等。在c s 模型中，客户端( 传 感器节点) 向服务器( 处理单元) 发送原始数据，服务器负责数据处理。但是 c s 模型并不适合于分布式传感器网络中的数据融合； 首先，由于数据融合由服务器负责，因此需要由本地传感器节点向服务 器发送原始数据，当原始数据文件很大以及传感器节点的数量很大时会造成很大 的网络流量从而导致很差的系统性能。 其次，假设采用了面向连接的服务( 例如，邱应用协议) ，c s 模型要 求网络连接在整个数据发送阶段都要保持活跃并且健康。如果连接挂断，客户端 和服务器端都要等到连接恢复来完成数据传输以及进一步的分析，这样就会影响 系统的性能。 再者，基于c s 模型的分布式网络不能实时的响应负荷变化。当有更多 的传感器节点被配置后，它不能在不改变网络结构的情况下来进行负载均衡。， 2 2 2m a d s n s 介绍及其优点 为了克服传统分布式网络的这些不足，一种称作基于移动代理的分布式网络 ( m a d s n s ) 被提出来 1 3 】。基于代理的系统【5 】给出了一种新的软件技术，这种 技术将人工智能( a i ) 和面向对象的分布式计算技术结合起来。这里所说的代理 是指一些在应用系统中相互作用来达到一个共同的目标从而为解决给定的问题 提供支持的具有智能性，自动性的软件环节。一个代理可能会具有下面的几个特 性：自动性，通讯性，移动性，学习性和合作性。在m a d s n s 中移动代理选择 访问的传感器节点并逐步融合本地量测的数据。移动代理从源节点发送并且在中 间节点中被执行。到达中间节点后，一个移动代理会提供他的证书来获得本地服 务和数据的访问权从而收集所需的信息或者执行特定的操作，完成后会带着结果 山东大学硕士学位论文 离开。这样一种通过移动代理来传送部分融合结果的方式虽然仍可能有被恶意窃 取的可能，但是由移动代理逐步收集数据的过程显然减少了未加工的原始数据被 暴露的可能，从而增强了网络的安全性。关于使用移动代理的优缺点在文献 1 4 】 中有详细的介绍，其已成功的应用于电子商务以及军事等领域。移动代理在分布 式网络中得到了很好的应用，在分布式网络中引入移动代理技术有下列好处： 网络带宽需求大大减少。与传统分布式网络中沿着一些环形的路径传递 大量的原始数据不同，m a d s n s 中传送的是很小的代理。 增强的网络稳定性。网络的性能不受传感器节点数量增加影响。支持自 适应网络负载均衡的代理结构能够自动的完成网络重构。 可扩展性。移动代理可以被重新编程来完成适应任务的数据融合过程从 而提高了系统的可扩展性。 稳定性。移动代理可以在网络连接激活的时候被发送到中间节点，然后 在连接重新建立的时候将结果返回。因此，m a d s n s 的性能受网络可靠性的影 响不大。 2 2 3d s n 与m a d s n s 的比较 图2 1 1 提供了d s n 与s n s 的比较： d s n 理节点 移动代i 禽能出器 r 铲秒理 擎滔气 禽、土 n 【a d s n 图2 1 1d s n 与m a d s n s 的比较 传感器 在传统的分布式传感器网络中，数据是由各传感器节点收集然后再发送到一 个上层的处理器节点并在那里进行数据融合。这个过程中大量的数据在网络中移 山东大学硕士学位论文 动。在m a d s n s 中采用了一个新的计算方法：原始数据留在本地节点，融合过 程的代码被传送到数据节点，这样就使得m a d s n s 具有了上述比传统的分布式 传感器网络优秀的特点。 2 2 一种m a r p 及分析 2 2 1 问题综述 在这- - , j , 节中，我们重点研究m a d s n s 中的一种新的移动代理路由方法。 一个移动代理访问的节点数目和顺序决定了能量消耗，路径损失等，因此对 m a d s n s 的整体性能有着很重要的影响。在文献 18 】中作者针对一种特殊的情形 目标识别与追踪环境下的m a d s n s ，研究了相应的移动代理路由问题。文 中作者基于3 个方面的考虑：一减少传播中的路径损耗；二最小化节点能耗； 三尽量访问具有“高信号监测电平”的节点以获得更高的监测精度。这个模型 有一定的局限性，首先簇内的节点要经常通过全向天线来广播自己的监测电平， 这样将会产生大量的分组，增加了网络的能耗，也同时更容易引起发送冲突，再 者这种只访闯网络中部分节点的方式不利于保证数据的完备性和决策的准确性。 我们来研究比较通用的情况，即簇内所有节点的数据都被融合的情况。相应的路 由问题就是要为移动代理寻找一条路径，使得每个节点被访问一次，并且最小化 系统的能耗。我们将m a d s n s 中的移动代理路由问题( m a r p ) 表示为一个组 合优化问题。问题的目标是要找一条路由使得路径损耗和节点损耗尽量小。我们 指出m a r p 问题是一个n p c 问题并且等价于一个起始点固定的m t s p 问题。 2 2 2m a r y 介绍及其数学模型 2 2 2 1m a d s n s 的体系结构及m a r 预备知识 下面我们大体介绍下m a d s n s 的体系结构来引出路由优化问题的表示。 一个m a d s n s 通常由3 部分组成：处理器节点( p e ) ，传感器节点( s n ) 和通 讯网络( c n ) 【1 5 ，其中处理器节点和传感器节点通常通过无线通信网络来连接。 一组相邻的传感器节点和一个控制作用的处理器节点组成一个簇。图2 2 1 展示 了个采用l o b i l ea g e n t 的传感器网络的模型 7 山东大学硕士学位论文 图2 2 i 采用m o b i l ea g e n t 的传感器网络的模型 a ) 传感器节点 一个传感器节点( 又称作叶子节点) ，是m a d s n s 中负责数据收集的基本单 元。传感器节点呈分布式被投放于任务地点，用来收集如声音，震动，光线等相 关量的量测信号。数据收集是由一个采样子系统来控制，并且发送到处理器 1 6 】。 一个移动代理通过网络连接在传感器节点之间迁移，同时融合本地的信息然后将 最终的结果传送会原始的p e 节点。融合的信息可能被用来得到基于不同应用的 对于环境的适当的推断。一个p e 节点的设置时间包括载入移动代理代码的时间 和执行其它的初始化任务。各个传感器节点会将由自带的g p s 组件获得的位置 信息发送给其所属的p e 节点，从而p e 节点了解整个簇的地理位置分布情况。 b ) 通信连接 在移动代理沿着一条路由在相邻的节点之间迁移的过程中需要建立一个无 线通信连接。传感器节点上的嵌入式的r f 调制解调器提供了类似的低能耗的联 网功能。不同的簇选择不同的“网络i d ”，这些“网络i d ”是一些离散的跳跃 的伪随机序列来防止冲突。两个传感器节点之间的数据传递时间由他们之间的物 理距离、带宽、数据包的大小( 包括部分融合的数据和移动代理的代码) 以及丢 包率决定。由于电磁传播的时间在短波无线通信中可以忽略，在我们的模型中将 不考虑物理距离而是在计算路径损耗的时候再考虑。 系统损耗分析我们采用h e i n z e l m a n 等在 1 9 中提出的一种无线信道模型， 山东大学硕士学位论文 见图2 2 2 ： 图2 2 2 一种无线信道模型 路径损耗采用f r i i s 自由空间模型 1 7 ： 节点g 接收到的能量与节点墨发送的能量之间有如下的关系： 砒) 咄，器 汜1 ) 这里g 。，表示节点s 作为发送器的增益而g j ，代表节点s j 作为接收器时候 的增益。九表示载波的波长，卢表示系统损失系数。吐，表示s 与之间的物理 距离。 2 2 2 2一种简单的移动代理路由问题( m a r p ) 简单的移动代理路由问题( m a r p ) ，即只考虑簇中存在一个移动代理： 仅一个移动代理从p e 节点被配置好并且准备访问簇中的传感器节点的一个 子集合来融合覆盖范围的数据。选择一条使得整体能量消耗和路径损耗较小的路 由很重要。下图2 2 3 展示了一个简单配置的m a d s n s 的例子，这个网络中包含一 个p e ，标号为，以及n = 1 0 个叶子节点，分别标号为一，i = l ，2 ，n ，其中有一 个节点品挂掉。各传感器节点分布于监测范围内来收集环境的监测信息，并且通 9 一圈卜 节 i 接收器 i l 占 r 处 理 器 一 【_ j i _ 发送器广 发送放大器 i ； 7 节 1 l 点 r 处 理 器 叫发送器卜1 发送放大器l l 山东大学硕士学位论文 过无线连接来通讯。 2 2 2 3简单的m a r p 的数学模型提出 下面给出简单的移动代理路由问题( m a r p ) 的数学模型： 移动代理路由问题的目标函数基于两个方面的考虑：能量消耗和路径损耗： 1 能量消耗 单个结点的能量消耗由处理速度和耗费的时间决定。在无线数据传输中， 能量消耗依赖于节点的发送功率和数据传输时间。我们假定数据大小为s ( 包括 部分融合的数据大小d ，移动代理代码大小m ) 对于给定的分辨率d 的大小固定， 因此s 固定。数据传输信道带宽假定为b w ，数据传输时间为： s t = 一 “曙 b w 假定路径p 为p 0 ，p 1 ，p h - i ，则该路径上的能量消耗e c 定义为： e c ( p ) = ( 姗印+ t p 【o 】胖) o 伽。+ 昂【o 】 f 一f 啤 日一1 + ( 圮唧+ f 】，删) 尸尸嘲，胛。+ 耳嘲，一- t 懈) k = l 其中，t p 【0 b 。印为p e 的配置时间，t p o , p r o c 为p e 的数据处理时间，昂【。1 ，胛。为 p e 的数据处理功率，昂【0 1 ，一为p e 的数据发送功率，r p k , a c q 为p e k j 的数据收集时 间，t p 雎】柙。为p k 的数据处理时间，昂【】胛。为p k 的数据处理功率，0 【t 】，删为 p l - k - i 的数据发送功率，f 懈为p i ，i = 1 ，2 ，h 一1 的数据传输时间。 2 路径损耗 山东大学硕士学位论文 路径损失( p l ) 是用来表征信号衰减的量，其定义为有效发送的信号能量与接受 到能量之间的差( 单位是d b ) ，根据f r i i s 自由空间模型 1 7 得： 讯一g 争崦 器矿，l _ 从而可以得到系统在路径p 上的路径损失： 尸三c尸，=n白-,-u-ug一(4z)2,bd2p。吓。+，。耐， 的是一种同构的网络，即每一个节点采用相同的无线接受和发送设备，而且各节 点处理器功率也相同，由于移动代理的大小在整个路由中保持不变，因此总的能 量消耗为常量，因此需要找一条路由使得路径损失( p l ) 最小，由于各个节点的 发送和接受增益也都相同，问题转化为如下优化问题： n警npl(p)=n摹n蒸。-。giz：啬d2尸。，尸艮。+，。， 2 唧n c 兰k = oil。-。gzii：器+2。g d2h4虹c。+。，。一， = c o n s t + m i n ( 荟1 2 0 1 。g 白t 1 小+ 1 ) 酬 j 即要求一条路由p ， 一l r1 使得h：|n(ll。g砟嗍巾m)酬jk 。 - - - ol 。 。一 可以看出这个问题实际上是一个优化中的经典问题一一旅行售货员问题即 t s p 问题。 2 2 2 4简单的m a r p 数学模型分析 下面给出t s p 问题在图论中的描述： 定义2 2 1 有向图给定一个有向图d 的三元组为( v ，e ，f ) ，其中v 是一 个非空集合，其元素成为有向图的节点；e 是一个集合，其元素称为有向图的弧 段( 边) ；f 是从e 到v v 上的一个映射( 函数) 。 由定义1 可知，e 中的元素总是和v 中的序偶有对应关系，因此，可以用v 山东大学硕士学位论文 中的序偶代替e 中的元素。从而，一个有向图d 可以简记为( v ，e ) 。 定义2 2 2t s p 设c = c l ，乞，q ) 是n 个城市的集合，l = 1 0l q ，巳c c ) 是 集合c 中元素( 城市) 两两连接的集名，4 足，_ = ，2 ，玎) 是屯的欧式距离，即 设g = ( c ，l ) 是一个有向图，t s p 的目标是要从有向图g 中找出一条长度最短 的h a m i i t o n 圈，即一条对c = c 1c 2 ，巳) 中n 个元素( 城市) 访问且只访问 次的最短封闭曲线。 2 2 2 5整个簇中的m 削强 而考虑整个簇，问题的描述则是要给出数条从簇头出发的路由，使得簇中的 每个叶子节点都被访问到且只被访问一次，且最小化系统能耗。这实际上是一个 m t s p 问题，即要在有向图中找出k 个h a m i i r o n 圈，其中这k 个h a m i i t o n 圈满 足只有在一个指定的点相交，并且要求得的k 个h a m i l t o n 圈的总弧长最短。可