（应用数学专业论文）无线传感器网络中可靠性优化问题及启发式算法.pdf

摘要 本论文研究了无线传感器网络中关于可靠性和被激活节点数的两种优化算 法主要讨论了一定数目的传感器节点正常工作情况下，二终端可靠性优化问题 及其解决方法以及二终端可靠性和能量限制下的激活节点数的优化问题，提出了 解决这两个优化问题的两种新算法 1 研究了无线传感器网络中一些节点由于能量耗尽导致节点损坏而影响二终 端网络可靠性的优化问题，提出了无线传感器网络中，m 个节点被损毁情况下使得 边不交道路可靠性最大的优化问题通过引入s t 子图边不交道路可靠性的概念， f 当c 0 满足c c oi nt h eo p t i m i z a t i o nm o d e l ，w h e r ec 。i st h en u m b e ro fn o d e si n t h es h o r t e s ts - tp a t h 2 t h i sp a p e rp r o p o s e st h em i n i m u mn u m b e ro fa c t i v es e n s o rn o d e so p t i m i z a t i o n i s s u es u b j e c t st ot h ec o n d i t i o n so ft w o t e r m i n a ln e t w o r kr e l i a b i l i t ya n dt h ep o w e rc o s to f ac e r t a i na r e a b yi n t r o d u c i n gt h en o t i o n so rs ts u b - g r a p h sa n dt h ea a r e a sp o w e rc o s t ， am a t ho p t i m u i z a t i o nm o d e li ss e tu p i nt h i sm o d e l ，w ep r e s e n tih e u r i s t i co p t i m i z a t i o n a l g o r i t h m m i n i m u m n o i 扯sa l g o r i t h ms u b j e c t st o r e l i a b i l i t y a n dp o w e r ( m n r p i i a l g o r i t h m ) ，w h i c hc a nf i g u r eo u tt h e m i n i m u mn u m b e ro fa c t i v es e n s o rn o d e sa st h e g e n s o rn o d e ss a t i s f yt h ei n i t i a lv a l u e si nt h ec o n s t r a i n tc o n d i t i o n w ep r o v et h e p r o p o s e da l g o r i t h m i si n p o l y n o m i a lt i m ea l s o c o n s e q u e n t l ys i m u l a t i o nr e s u l t s i l l u s t r a t et h e a l g o r i t h mc a ns o v e t h i s o p t i m i z a t i o np r o b l e me f f e c t i v e l yu n d e r t h e d i f f e r e n ti n i t i a lv a l u e s k e yw o r d s ：n e t w o r k ：t w o - t e r m i n a lr e l i a b i l i t y ；o p t i m i z a t i o na l g o r i t h m e d g e - d i s j o i n tp a t h s ；w i r e l e s ss e n s o rn e t w o r k n i 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写 成硕士学位沧文 ! 五绫篮壁昼旦终生互盎丝趁丝坦壁丞扈筮述篁鎏：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公丌发表的成果。 本声明的法律责任由本人承担。 论文作者签名：殆举 b 年j 月f 7 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编八有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作者签名：冶备支 导师签名：卯务硷 日期：晦；月i ，日 i 第1 章绪论 1 1引言 近年来在微电子机械系统( m e m s ) 、无线通讯、低功耗高集成数字设备方面取 得的巨大成就使得发展低成本、低功耗、微体积、短通信距离的多功能传感器成 为可能无线自组传感器网络就是在这些技术之上出现的新事物它是由一组传 感器以自组网的形式构建的无线网络，其目的是协同地感知、采集和处理网络覆盖 地理区域中感知对象的信息，并传送给观察者它是集数据采集、数据处理、数据 传输于一体的复杂系统无线自组传感器网络在军事、工业、医疗、环境检测、交 通管理、抢险救灾、民用等领域的巨大的应用价值和潜在应用前景，引起军事部门、 工业界、学术界的广泛关注【1 - 3 】 传感器网络由大量传感器节点组成，它们密集地被放置在要测量环境或非常 接近要测量的环境中，传感器的节点不用经过工程处理或预先定位，可以进行随 机地放置在不可达的地形或灾难区域，减轻人们的工作强度换句话说，这些也就 意味着传感器网络的协议和算法应该具有白组织特征传感器节点的另一个特征 是传感器节点间的协作每个传感器节点上都安装有小型处理器，传感器节点不 是把大量的原始数据传送给汇总节点，而仅仅是把需要和部分处理后的数据发给 汇总节点传感器节点的基本组成见图1 1 ，包括电源、传感器、a d 转换器、处理 器单元、存储器单元、数据发送接收的传输单元个别功能强大的可能还包括定位 系统、运动或执行机构、电源再生装置【3 j 图1 2 中的四张图描述的是传感器网络的生成过程首先，传感器节点进行随 机的撒放，包括人工、机械、空投等方法；第二步是撒放后的传感器节点发出信号 侦测周围传感器节点并记录；第三步是这些传感器节点会根据侦测到周围传感器 ； 节点的情况采用一定的组网算法从而形成按定规律结合而成的网络；第四步是 组成网络的传感器节点根据一定的路由算法选择合适的路径进行数据通信1 3 j 图1 1 节点基本组成 f i g 1 1t h e b a s i cs t r u c t u r eo fs e n s o rn o d e 1 i o 卜一_ 7 厂一_ _ 7 ff 。 f f 。j fri 二一? ? ! ! i ? f 放置传感器唤醒和相互侦测 自动连接成网络 选择路由进行通讯 图1 2 传感器网络的放置到传感器网络的生成 f i g1 2f r o md e p l o y i n g t ob u i l d i n go f t h es e n s o rn e t w o r k 2 1 2 无线传感器网络中的重要指标 无线传感器网络中节点的能量资源、计算能力和带宽都非常有限，而且无线传 感器网络通常由大量密集的传感节点构成，这就决定了无线传感器网络协议栈各 层的设计都必须以能源有效性为首要的设计要素无线自组传感器网络的节点往 往不能预先进行定位，大量传感器节点密集地，随机地被放置在要测量环境与非 常接近要测量的环境中，测量环境通常是不可达的地形或灾难区域而且随机撒 放的传感器节点往往由于传感器的损毁、失效，传感器节点自身能量的耗尽以及环 境的变化等原因造成损坏，不能正常地工作，从而导致整个网络拓扑发生变化【1 。引 在网络拓扑不断变化的无线传感器网络中，实时工作的节点数，网络的能量以及 网络的可靠性都是测试网络能否正常工作的重要指标 1 3 无线传感器网络能量问题的概述m 8 1 近些年来，无线传感器网络已经变得日益普遍，并且在战争通讯和灾难救助通 讯等领域有着重要应用这些网络面临着多种在有线网络中不会出现的限制条件 在无线网络中的节点是典型的耗电型装置，并且更换这些装置是昂贵的，有时甚 至是不可能的现在学者们研究的方向已经集中到针对一些典型的网络任务例如 广播传输、连通性容错性等，设计耗费最小能量的算法1 5 7 j 无线传感器网络由一些简单的经由无线发射器来通信的移动装置组成一个 网络的任务范围是由每一个节点所带有的能量装置决定的，并且这个任务范围的 能量费用( c o s t ) 或者是该任务所需装置的平均能量或者是该任务所需装置的最大能 量本文中，我们选择用其最大能量来衡量，网络中来自于单个节点的信息可以到 达传输范围内的所有节点每一个节点都可以通过改变它所传输信息的能量来改 变它的传输范围这一事实说明传输一个信息的费用不是依赖于接受节点的数目 而仅仅是依赖于发射节点的最大传输距离r 的一个函数大多数的无线网络都是多 跳的( m u l t i h o p ) ，换句话说，节点可以传输信息也可以发送信息在一些装置中， 可能不需要每一个节点都以最大能量传输信息来传播或维持网络的连通性这就 允许我们寻找节点的能量最优分配范围和相关的网络性质【4 j 以前的文章中已经从事于维持网络连通性的能量最优分配范围的研究由于 这个问题是n p 难问题甚至是e u c l i d e a np l a n e 的，一些研究方法集中于启发式算法 的研究 本文中我们主要研究的模型是静态对称系统中的多跳无线传感器网络，并且 网络中信息传输是双向的，这也是c a l i n e s c ee ta 1 1 7 1 和k i r o u s i se la 1 1 8 1 等人在研究 关于连通性的文章中所考虑的模型对于这样的模型，算法的发展有着重要的现 实意义，许多从前已经存在的路由协议可以被简单地更改为边的双向传输即可 这早我们简单地重述这个模型 无线传感器网络山一组带有无线传输和接收信号的移动装置构成每一个无 线发射器都带有一个能量装置和一个定义了传输的接收区域的定位装置有向发 射器通过发射特定方向的信号来节省能量，但是实际上，大多数的发射器都是双 向的，这也是本文中所引用的网络模型( 事实上，所有引用的文章中都是用这个模 型的) 在理想装置中，能量为r 2 的双向传输可以到达半径为r 范围内的所有传感器 接收器然而，来自其它传输和后台噪声的干扰会削弱信号，故一般地，一个节点 要想传输信息到达距离为，范围内的所有传感器接收器就必须以能量r c ( 2 m ，芑f 1 其中随着i 的增长m ：可以被连续地计算： 一烈? ” 例如，1 0 的4 - 鳓( 5 ，4 ，2 ) ( ；) + ( ；) + ( i ) = ，。 任何非负整数的卜规范表示都是唯一的【7 “ 定义1 2 如果( m t ，m “l ，m 1 ) 是非负整数m 的卜规范表示，那么对于 k l 1 ，t ，m “，掰，) 的第( i ，k ) 个下伪幂( ( 七) 加l o w e r p s e u d o p o w e r ) 为： 附 n m 并且被记为( m 七 卅“1 ，m f ) 珊1 例如1 0 的4 - 规范表示的第( 3 ，4 ) 个下伪幂为： 1 。3 ，4 篁( ；) + ( ：) + ( ；) = 1 8 - m 的第( i ，曲个下伪幂被记为小叶，它被用于描述m 的l 】卜规范表示的下伪幂 k r u s k a l 和k a t o n a 指出： 防。 如果 玳 d 条边发生错误，s 与t 就变得不连通， 因为少于，条边有效因此只= 0 当i d 时， 在二终端情况下，c 是最小s - t 割集的基数如果少于c 条边发生错误，s 与t 一 定连通，因为没有足够的边发生错误以形成一个s - t 割集因此互。f ? 1 当f 。 c ， 最短s t 道路的数量乃，可以用b a l l 和p r o v a n 在文献【7 2 中给出的多项式算法 来准确计算，然而，计算最小j t 割集的数量n 。，对于一般的图已经被证明是牟尸- 1 4 完划7 3 1 因此c 。阶心计算也是犯完全的然酏的值可以被向下估计 得到下界来获得，c 的上界因为每一个图都至少有一个最小s t 割集，因此n e1 就是一个下界，它可以被用于获得r 的上界：e 丘2 ( ：) _ 1 利用以上法则，求得的二终端可靠性多项式边界i u u s k a l k a t o n a 边界【6 6 】为： - e s 蒿( ；p 6 一口+ ；d ! - ；i ，? 7 。p 6 一q + - 。p 6 一。q 。 c z t 4 ， 尺z 霪( ；) p 6 g 十善d ，：“p 6 g 这罩c 是最小割集的基数，d 曲。，是最短p r 道路的边数，丘。( ：) - 1 ( 2 ) 边不交道路法一e d g e d i s j o i n tp a t h sb o u n d s 。“ p o l e s s k i i 【删证明了一个图中边不交生成树的最大数目至少为睦j ，这里c 是最 小割集的基数p o l e s s k i i i7 5 j 利用了在图失效之前每一个边不交生成树必然先失效的 事实，得到了全终端网络可靠性的下界： 月：1 一( 1 一p 一) ( 1 1 5 ) 这样，想要计算这个边界只需要计算唯一一个未知数c ；并曰这个边界可以被简单 地在多项式时间内计算出来 b r e c h t 将p o l e s s k i i 的这种利用边不交生成子图的方法用于二终端情况，因为 在二终端情况下最小有效子图就是道路，所以他提出了边不交道路边界 ( e d g e d i s j o i n tp a t h sb o u n d s ) f o r d 和f u l k e r s o n 的最大流最小割定理【7 6 】保证了源点 和终端节点之间至多有c 条边不交道路， 此b r e c h t 6 6 给出了二终端网络可靠性的 下界： 胁卜陋) 均 这罩p , - 县第i 条道路失效的概率b 可以被表示为： 只2 ( 卜冉p 0 n 忉 这里研是道路中第j 条边有效的概率，厶表示第i 条道路的长度 例如图1 3 中图的可靠性下界由两条明显不相交的道路求出 r s ，2 1 - 【( 1 一p i p 2 p 3 ) ( 1 - p 。p s ) 】 图1 3 边不交道路边界的计算 f i g 1 3t h ec a l c u l a t i o no f e d g e - d i s j o i n tp a t h sb o u n d s 与k r u s k a l k a t o n a 边界相比，边不交道路边界有一个显而易见的优点子图计 数方法依赖于图中的边有相等的失效概率，而边不交道路边界利用的是边不交的 有效予图，所以边的失效概率并不需要相等 因为图中边的错误是统计独立的，因此边不交道路边界可以通过“严格”的最 小费用最大流定理给予改善如果图中有一个或多个割点使之被划分成双连通分 支，整个图的二终端可靠性就等于包含割点的每一个分支可靠性的乘积例如图 1 4 中，图的可靠性边界可以通过两次计算：先计算点s 和茗可以通信的可靠性边界 ( 第一个分支中至少有一条道路有效的概率) ，记为c ；然后计算点石和f 可以通信的 可靠性边界( 第二个分支中至少有一条道路有效的概率) ，记为d ，则整个图的可靠 性边界也就是点s 和r 可以通信的可靠性边界为cx d i 图1 4 边不交道路边界的改善计算 f i g 1 4t h ea m e n d a t o r yc a l c u l a t i o no fe d g e d i s j o i n tp a t h sb o u n d s 1 8 本文研究的主要内容 本文对无线传感器网络可靠性以及能量的优化进行了研究，主要内容如下： 第2 章研究的问题是无线传感器网络中一些节点由于能量耗尽导致节点损 坏而影响二终端网络可靠性的优化问题，提出了无线传感器网络中，m 个节点被损 毁情况下使得边不交道路可靠性最大的优化问题通过建立其优化模型，给出了 ! c o 满足c s c o ( c 是设计的启发式算法得到的最可靠的子网中所包含的节点 数) ，而被损毁的节点数聊蚤f 吲c 时，寻找源点与终端节点之间最大的j t 子图可靠 性的启发式算法，即最大边不交道路可靠性算法( m e d p r 算法) ，并证明了这个算 法的计算复杂性是多项式时间的此外本文也用类似的方法简单地处理了优化模 型中c 苫c o 时的最大s t 予图可靠性，其巾c 。是最短s r 道路中所含的点数 第3 章在第2 章优化算法的基础上，研究了无线传感器网络中，最少激活多 少个传感器节点能够保证网络正常通讯的问题主要提出了在二终端网络可靠性 以及某一区域能量限制的约束条件下如何得到网络中被激活的节点数最少的优化 问题通过建立优化模型，我们给出了当网络中的节点满足两个约束条件的初值 时，可以求得最少被激活节点数的启发式算法，即可靠性和局部能量限制下的最 少节点优化算法( m n r p 算法) ，并证明了这个算法的计算复杂性是多项式时间的 仿真结果说明约束条件初值的不同对结果的影响，而m n r p 算法可以有效地处理 浚优化问题 第2 章基于无线传感器网络中二终端可靠性的一种优化算法 2 1 引言 在传感器网络中，大量传感节点密集地，随机被放置在要测量环境与非常接 近要测量的环境中，测量环境通常是不可达的地形或灾难区域但随机撒放的传 感器节点往往由于节点的损毁，能量的耗尽以及环境的变化等原因造成损坏，而 不能正常地工作，从而导致整个网络拓扑发生变化m 】 在无线传感器网络的研究中，文献【3 】的工作是利用大量的仿真实验得到随机 抛撒均匀分布的节点的邻居节点的分布规律，并给出了在一个固定区域内要抛撒 多少传感器节点爿能保证这些点组成的网络基本连通和保证其满足2 点的连通可 靠性实际l ：，保证无线传感器网络性能及可靠性具有重要的意义在传感器网络 中，若存在节点间通信概率，那么就存在从一个节点( s e n s o rn o d e ) 至0 目标节点( d a t a s i n k ) 的二终端可靠性所谓二终端可靠性是网络中源点与终端节点间至少存在 条道路可以通信的概率【9 , 6 6 1 一个重要问题是在撒放的传感器节点组成的连通的网 络中研究m 个传感器节点损坏后，如何得到最大的s t 子图可靠性而文献【7 7 】将二 终端边不交道路可靠性下界应用于无线网络，并给出了多项式时问的边不交道路 集选择启发式算法( d p s p 算法) ，证明了其在多跳路径网络中的有效性从而说明， 边不交道路集构成的子网在无线传感器网络路由选择等问题中有重要的作用 为使该子网计算的复杂性简化，联系到实际中传感器节点的不稳定性，这一 章我们提出了一个优化问题： m 个节点被损毁情况下使得网络中的5 t 子网可靠性最大通过建立相关的优 化模型，给出优化模型中的c o 满足c s c o ( c 是设计的启发式算法得到的最可靠的 “子网中所包含的节点数) ，而被损毁的节点数m t i 卅c 时，s ，r 子网可靠性最大的 启发式算法，朗最大边不交道路可靠性算法；并证明了此算法复杂性是多项式时间 的，仿真结果说明该算法可以有效地处理这类优化问题同时这一章也简单地给 出了优化模型中c 。c o 的最优解，其中c 是最短s t 道路中所含的点数 2 2 假设 本文用无向图作为网络的模型，文中不区分网络和图，这些图满足如下假设 ( 1 ) 图的边是以一定概率正常工作的，所有顶点都是正常工作的并且是完美 可靠的；拯个网络、源点及每条边只有两个工作状态，即正常工作( o p e r a c i v e ) 或失 效( f a i l e d ) ，因而亦把图称为概率图 ( 2 ) 整个网络、源点及边的工作状态在统计上都是相互独立的 2 3 记号 下面给出本章所用到的符号表示： v 点集，有i 卅个节点 e 边集，有陋i 条边 p 各边的有效工作概率的集合 网络图g = ( v , e ，p ) ，图中各边的有效概率对应于集合p 节点z 的状态变量：z 产怯雩军鬻 所有x i 的集合：缸b 。2 ，j 。 正常工作的点的个数 对应于点的状态集合x 的网络图 z = x 1 # 2 ，加) 状态下的第k 条s t 道路 x = 忸l # 2 ，而) 状态下道路竹o 。中第j 条边有效的概率 x - - 慨2 ，而 状态下网络图g ( 啊一的s f 子网可靠性 2 4 基本概念 在无线传感器网络中，由于网络状态与所有节点的工作状态有关，因此网络 的数学模型描述为一个无向图g ( p ) ，其中y 表示传感器节点的集合，e 表示传 感器节点间可以通信连接的边的集合，p 表示各边有效工作的概率的集合因而本 文中网络与无向图是互相等价的概念我们定义一个网络元素的可靠性为这个元 素可以工作的概率在本文论述中，假设节点是完美可靠的而边发生错误的概率 是统计独立的，边的通信概率为这条边能够正常工作的概率网络中5 t 可靠性表 示在g ( 啪闩中源点s 与终端节点t 之间通信的概率m6 1 ，定义如下： 定义2 1 若 p 1 j ) 2 ，w 表示图g ( 啊力的所有简单s t 道路集合，日表示道 d 。 e 征， 以 聊 。旧=莓= 硼 ( # “ ，z 哪 茸 。蕊哪所地 路尸2 中所有边有效的事件，对源点s 和终端节点f o f ) ，二终端可靠性就是在 g ( 哪一中至少存在一条道路使得s 与t 连通的概率，记为r e l 。( g ) ，即： r e l s f ( g ) = p t 1 u 历u u e k ) ( 2 1 ) 由于传感器网络拓扑的不稳定性，传感器节点工作状态不同就会导致整个网 络拓扑发生变化这样，我们定义节点i 的状态变量x i ：当节点f 被激活时x i = 1 ：当 节点f 被损毁时x i = o 而秽仁z j 2 ， ) 就表示网络中所有节点的工作状态，n 是网 络中所含节点的个数l 每一个x = 缸，, x 2 ，。) 都对应一个网络拓扑，当整个网络 拓扑发生变化，x = 缸l 一2 ，而) 也就随之变化在路由选择算法中从源点到终端节点 的边不交道路是非常重要的【7 7 】实际上，边不交道路就是一个子网络故给出该子 网络定义： 定义2 2 称g ( 巧e p ) 中s t 边不交道路集合中所包含的点和边构成的子网络为 一个s 。t 子网络，记为j d 事实上5 t 子网络也就对应着s t 边不交道路集合 实际上，个网络图中的s t 子网络的个数是个组合问题，在所有子网络中找 到可靠性最大的子网络是一个n p 一难i ；3 题【9 】而文献 7 7 】给出了一个可以在二终端 情况下寻找最可靠的边不交道路集合的d p s p 道路选择启发式算法这个算法和文 献 7 8 1 中给出的二终端边不交道路最大下界定义结合起来存在着改善网络中由贪 婪算法找到的可靠边不交道路集合的优化算法 设网络在某一状态x = 扛1 , x 2 ，尚) 下，对应的网络g ( v , e 一中共有r 个s t 子网， 分别为：d l ，d 2 ，研，那么一定存在某一个d f 是最可靠的s t 子网因为 工= 协声2 ，尚) 的变化就会引起网络拓扑结构g ( p ) 的变化以及边不交道路集合 d f 的变化，所以网络图g ( 尸) 、s t 子图d f 以及d f 的可靠性等都是关于 z = 协, x 2 ， ) 的函数，分别记为g ( p ) 、毋0 ) 和，g ，p j ) 因此任意一个s - t 子网 的可靠性定义如下： 定义2 3 某一状态工= 缸1 2 ，# 。) 下，网络g ( 瞪力的一个s t 予网d 舡) 的可 靠性为： f r1 1 f ( x ，p j ) 2 键答忆。玑”，黔| 2 这里d r ) 是工= 恤l 芦2 ，而) 状态下r 个边不交道路完全集中的第f 个，p k ( x ) 表f f ； x = i x l 抛，而) 状态下d f o 。中的第k 条道路，研表示工= 缸，# 2 ，而 状态下道路晟0 ) 中第j 条边有效的概率， 2 5 优化模型的提出 在兀线传感器网络g ( 旧尸) 中，随着时间的变化某些节点由于能量的损耗而 失效，一个相关的优化问题i 是m 个传感器节点被损毁的条件下，g ( 憾p ) 的s t 子网的可靠性m ，西) 最大这个问题可以转化为下面的优化问题l i ：c o 个传感器节 点f 常工作情况下，使g x ( v , e , p ) 的s t 子网络的可靠性最大其数学模型描述如下： m a d c 辩，确 s td f = c o ( 2 3 ) 其中c 0 是一个非负整数，c o = n - mo 是网络中节点数i 卅，m 是被损毁的节点的个数) ， x - - - - 扛1 # 2 ) ， f 1 第f 个节点正常工作 “一1 0第f 个节点被损毁 优化问题的意义是解决了某一个无线传感器网络中有m 个节点被损毁的条件 下，仍然存在最优的s t 子网络，从而保证从一个节点( s e n s o rn o d e ) 至0 目标, 点( d a t a s i n k ) 的边不交道路可靠性最大 2 6 优化算法的设计思想 在数学理论中，对于优化问题l i ，解决方法可以考虑测试不同数目的节点 f 常工作来计算子网的可靠性，并比较得到最优解，但那不是多项式算法本文考 虑搜寻最优p t 子网的一个多项式启发式算法( 最大边不交道路可靠性算法) ，来解 决优化问题i i 中c c o 时的情况，其中c 是设计的启发式算法得到的最可靠的s t 子网中所包含的节点数在此基础上优化问题j 在被损毁的节点数小h c 的条件 下，得到很好的解决 在所提出的网络模型g x ( v , e , p ) 下，为了使s t 子网络的可靠性尽可能的大，一 方面可以通过增加路径的方法来增大可靠性：在两点之问肯定存在着最可靠的单 路径，如果在单路径的基础上再增加路径，则可靠性会增大；另一方面这些路径之 间的影响尽可能的小，它们的可靠性会更大也就是说，我们的目的是寻找到边不 相交的尽可能多且尽可能可靠的道路为了用最短路算法( d i j k s t r a 算法) 来得到最 可靠道路，必须将道路可靠性的计算由各边有效概率的乘法变为加怯计算使用 的方法是：将各边分别赋权值为i n j ) ，那么道路中边的权值之和为 胙罗卜l n ( p ，) 1 一i n ( 兀p ，) ，其中l 为道路所含的边数【”而道路的可靠性为 ilp ，由此可见，w 最小即是道路可靠性最火，这样就将最可靠道路问题转化为 暑t 最短路问题来解决 算法的基本想法是通过两次迭代构造一个最可靠的边不相交的道路集合第 一次迭代：搜索图中可靠的边不交道路集合用最短路( d i j k s t r a ) 算法搜索图 g ( k e p ) 中最可靠的5 t 道路p 1 ，为了使路径之间的边互不相交，把s t 道路p 1 中 的边从网络g ( 巧e p ) 中暂时去掉，然后再在剩余的网络中继续选择最可靠的s t 道 路p 2 ，依次迭代直到剩余的图变为不连通为止若最后得到了r 条道路p l ，尸2 ，只， 将这r 条道路暂时存入集合d 中由于这个过程下来得到的边不交道路集d 的可 靠性并不一定是最大的，所以进行第二次迭代：替换集合d 中的某些道路，使d 的 可靠性增大方法是对d 中的道路尸1 ，p 2 ，一进行迭代：将最可靠的单路径p 1 中 的边赋上与卜+ f 相反的方向添加到已经不连通的图中，检验是否存在s t 道路，若 存在，找出可靠性最大的那条道路p 。，在图中删去尸中的后向边( 已经赋了方向的 边) ，这时将边的方向去掉寻找图中可靠性大于单路径| p 。的边不交道路集合，如果 存在，则在d 中更改道路集，将单路径替换为更可靠的两条或多条边不交道路在 原图中删去此时d 中的道路得到新的不连通图以同样的方式进行下一条道路尸2 的比较，直到将r 条道路检验完毕所以整个程序下来最后得到的道路集d 是最可 靠的边不交道路集合由其用公式( 2 2 ) 求得的可靠性如0 ，功) 即是最大的5 一t 子网可 靠性在两次迭代之后，统计出在此最可靠的边不交道路集合中的节点数c ，就得 到该优化问题在正常工作的节点数c s c o 条件下的最优解：因为c o = n - m ，所以也 就得到了被损毁的节点数肌，1 c 时的最优解：当c = c o 条件下，只有最可靠的边不 交道路集合中的节点正常工作，其它m 个节点处于损毁状态时才可以保证最大s - t 子网可靠性f o ( x ，p j ) ，有唯一解；当c c o 时，s 与f 变得不连通，所以最大s t 子网的可靠性为0 ，这时网络中_ ，1 个节点 任意被损毁m 个都可以使目标函数达到最大值0 ，所以有f ”1 个最优解 i 当c c o c 时，可以考虑将c o 个正常工作的节点的组合情况一列出求最大 的“子网可靠性，这显然不是多项式时间的算法，但目前还没有多项式时问的算 法可以解决这个问题由于优化模型中c 2 c o 的情况十分简单，而c c o r 结束 第二步结束后得到的d 就是最可靠的边不交道路集合 第三步：在d 中由公式( 2 2 ) 计算的可靠性即最大s - f 子网边不交道路可靠性知0 ，乃) 第四步：在图g 中找出d 中各条道路上的点，统计个数记为c ，当c = c o 即m = n c 条件下，只有其余m 个节点被损毁时能够保证最大s t 予网的可靠性f o ( x ，a ) ，是唯 一解；若c c o 即m 新c 时，不属于d 的各条道路上的n c 个点中任意研个被损 毁都可以保证最大子网的可靠性，0 0 ，所) ，有f ”一c 1 个最优解 、“， 算法结束 28 计算复杂度分析 若网络g 中节点个数i v = n ，第一步中每一次迭代的最短路算法的计算复杂性 为o ( n 2 ) ，共有，条边不交道路，那么第一步总的计算复杂性为r - 0 0 2 ) = o ( n 2 ) 第 二步对道路集合d 的改善，它的计算复杂性不大于道路选择最糟情况的计算复杂 性o ( n 5 ) 【7 7 1 第三步计算可靠性的复杂性为0 0 ) 第四步中对不在d 中各条道路上 的点的搜索的计算复杂性最大为d ) 所以整个算法的计算复杂性最大为o ( n 2 ) + o ( n 5 ) + d ( 1 ) + d ) = 0 0 5 ) ，可见它还是多项式时间的算法， 29 实例与仿真结果比较 为了便于说明这一优化算法，给出如下例子： 例2 1设随机生成的无线传感器网络给定了源点s = l 和终端节点t = 2 2 后的 网络拓扑为图2 1 所示：此图中我们设节点是完美的，边的有效概率分别为o 9 5 ( 图 中虚线的边) ，0 9 ( 图中粗线的边) ，0 8 ( 图中细线的边) ，并且边的工作状态在统计上 都是相互独立的 2 4 图2 1 传感器网络源点s = 1 利终端节点t = 2 2 f i g 2 1 t h es e n s o rn e t w o r k ，t h es o u r c e s = ia n d t h ed e s t i n a t i o n t - 2 2 对这个例子用m e d p r 算法( 最大边不交道路可靠性算法) 的m a p l e 程序进行仿 真处理( 程序见附录b ) ，得到图中的最可靠边不交道路集合为d = p 1 , p 2 , p 3 ，p 4 ) 其 叶1p i = 1 ，2 ，3 ，2 2 ，p 2 = 1 ，1 4 ，1 5 ，1 7 ，1 9 ，2 0 ，2 2 ，p 3 = 1 ，1 3 ，1 4 ，2 ，1 6 ，3 ，1 8 ，2 2 ，p 4 = 1 ，4 ，5 ，8 ， 9 , 6 ，2 2 这四条边不交道路的可靠性分别为：0 8 5 7 4 ，0 5 9 2 1 ，o 5 0 4 9 ，o 4 1 9 9 此时可 靠性o ( x ，p j ) = l - ( 1 - 0 8 5 7 4 ) ( 1 0 5 9 2 1 ) ( 1 0 5 0 4 9 ) ( 1 0 4 1 9 9 ) = 0 9 8 3 2 接着在图中搜索 到在d 中各道路上的点数c = 1 7 ，而不在d 中各道路上的点为7 ，1 0 ，n ，1 2 ，2 1 这5 个，所以m = 2 2 1 7 = 5 时m a x f ( x , 劫= 矗 历) = o 9 8 3 2 只有 7 ，1 0 ，1 1 ，1 2 ，2 1 j 塞5 个点同 时被损毁可以保证最大值，是唯一最优解；而m 5 时，m a x 其x , 所) = ，0 如砌= o 9 8 3 2 ， ， 、 在 7 ，1 0 ，1 1 ，1 2 ，2 1 ) 这5 个点中任意损毁m 个都可以保证，因而有f 。1 个最优解 l 肌 通过这个例子我们看到对于一个随机生成的无线传感器网络，我们都可以得 到源点与终端节点之间在c 满足设定条件下m 垂珏一c 个节点被损毁后还能够保证s - t 子网的可靠性最大，这样也就得到了被损毁的节点数m s ，l - c 条件下的源点与终端 节点之间最可靠的边不交通讯路径 表21 例2 1 的仿真结果比较 t a b 2 1c o m p a r i s o no fe m u l a t i o n a lr e s u l t so fe x a m p l e2 1 m 值损毁的节点 可靠性结果 最大边不交道路可 7 ，1 0 ，1 2 ，2 1 靠性算法计算的结 ，抖= ， ( 唯一最优解) 0 9 8 3 2 果 3 ，7 ，1 0 ，1 4 ，1 9 0 4 1 9 9 2 ，5 ，1 2 ，1 5 ，1 8 o 随机取点，由d p s p 道路选择算法计算 m = 5 6 ，1 0 ，1 2 ，1 7 ，1 9 0 9 3 3 2 的可靠性 4 ，8 ，1 1 ，1 6 ，2 0 0 9 3 2 4 7 ，1 0 ，1 1 ，t 2 或 7 ，1 0 ，1 1 ，2 1 或 最大边不交道路可 7 , 1 0 ，1 2 , 2 1 1 或 靠性算法计算的结 m = 4 7 ，1 1 ，1 2 ，2 1 或 o 9 8 3 2 果 1 0 ，1 1 ，1 2 , 2 1 ( 5 个撮优解) 3 ，6 ，1 4 ，1 8 0 7 2 1 5 随机取点，由d p s p f 5 ，1 1 ，1 8 ，2 1 0 9 6 5 0 道路选捍算法计算 m = 4 的可靠性 4 ，7 ，1 0 ，2 0 9 7 1 2 6 ，9 ，1 2 ，1 9 0 9 3 3 2 表2 1 给出m = 5 时随机的5 个点被损毁用d p s p 道路选择算法求出的p t 子网的 可靠性、川：5 由最大边不交道路可靠性算法计算出的损毁的点和最大5 t 子网的可 靠性的仿真结果比较以及m 取其它小于5 的数h 时随机h 个点被损毁由d p s p 道 路选择算法得到的s t 予网的可靠性与由最大边不交道路可靠性算法计算出的损毁 的h 个点和最大s t 子网的可靠性的仿真结果比较可见随机选点甫d p s p 道路选 择算法所得的可靠性总是不大于由m e d p r 算法得到的损毁的节点后的s t 子网的 可靠性 例2 2 对于一个随机生成的无线传感器网络( 见图2 2 ) ，设s = 1 ，f = 2 0 ，设点是 完美可靠的，边的有效概率分别为o 9 ( 图中虚线的边) ，0 8 ( 图中粗线的边) ，0 7 ( 图中 细线的边) ，并且边的工作状态在统计上都是相互独立的 图2 2 一个随机生成传感器网络s = 1 t = 2 0 f i g 2 2ar a n d o mc o n s t r u c t e ds e n s o rn e t w o r ki nw h i c hs = la n dt = 2 0 我们由最大边不交道路可靠性算法的m a p l e 程序得出图2 , 2 的3 条最可靠边不 交道路分别为尸产 1 ，1 2 ，1 0 ，9 ，8 ，2 0 ) ，p 2 = 1 ，1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，2 0 1 ，p 3 = 1 ，2 ，3 ，4 ，9 ，5 ，6 ，7 ，2 0 这三条边不交道路的可靠性分别为：0 5 2 4 9 ，0 1 7 2 9 ，0 1 2 4 5 ，求得此时最大可靠性 为，0 p j ) = l 一( 1 - 0 5 2 4 9 ) ( 1 0 1 7 2 9 ) ( 1 - 0 1 2 4 5 ) = 0 6 5 6 0 统计出c = 1 7 ，并且共有3 个点 1 1 ，1 3 ，1 9 不在最可靠边不交道路上，即损毁3 个节点 1 1 ：t 3 ，1 9 ) 能够保证最大可靠 性0 6 5 6 0 ，是唯一解；损毁的节点数m 3 时，损毁这3 个节点中任意m 个都可以 保证最大可靠性o 6 5 6 0 ，有f 。1 个最优解 1 埘 表2 2 例2 2 的仿真结果比较 t a b 2 2c o m p a r i s o no fe m u l a t i o n a lr e s u l t so fe x a m p l e2 2 m 值损毁的节点可靠性结果 最大边不交道路可靠m = 3 l o ，1 3 ，1 9 性算法计算的结果 ( 唯一最优解) 0 6 5 6 0 4 ，8 ，1 8 o 2 0 0 0 5 ，1 2 ，1 9 0 ，4 4 3 0 随机取点，由d p s p m = 3 道路选择算法计算的 3 ，7 ，1 5 0 5 7 3 0 可靠性 6 ，1 1 ，1 7 ) 0 5 2 4 9 l o 1 3 或 i 最大边不交道路可靠 m = 2 1 0 1 9 或 0 6 5 6 0 性算法计算的结果 1 3 ，1 9 ( 3 个最优解) 6 ，1 4 0 5 7 9 8 1 1 ，1 8 0 5 2 4 9 随机取点由d p s p m = 2 道路选择算法计算的 4 ，l o o 5 1 0 5 可靠性 7 ，1 9 0 6 0 7 0 表2 2 给出随机的三个点被损毁用d p s p 道路选择算法求出的s 。t 子网的可靠性、 m = 3 由最大边不交道路可靠性算法计算出的损毁的点和最大s t 子网的可靠性的仿 真结果比较以及m 取其它小于3 的数h 时随机h 个点被损毁由d p s p 道路选择算 法得到的s t 子网的可靠性与由最大边不交道路可靠性算法计算出的损毁的h 个点 和最大。，t 子网的可靠性的仿真结果比较可见随机选点由d f s f 道路选择算法所 得的可靠性总是不大于由m e d p r 算法得到的损毁的节点后的5 t 子网的可靠性 2 1o 结论 在无线传感器网络中，随着时间的变化某些节点由于能量的损耗而失效，导 致整个网络拓扑结构的变化实际上存在一个优化问题：网络中有m 个传感器节 点被损毁的条件下，如何使得s o 子网可靠性最大；本章研究在c 0 满足c s c o ( c 是 设计的启发式算法得到的最可靠的s t 予网中所包含的节点数) 而被损毁的节点数 r a i n ，c 条件下使得s t 予网可靠性最大的启发式算法，即最大边不交道路可靠性算 法并证明其计算复杂性是多项式时间的仿真结果说明了该算法的有效性同时 简单地处理了优化模型中c 。c o 的情况，其中c 。是最短s t 道路中所含的点数，给 出了此时的最优解但对于c 。 c o c 的情况的多项式算法仍然有待进一步研究 第3 章基于无线传感器网络中激活节点数的一个优化算法 31 引言 无线传感器网络是由组传感器节点通过无线介质连接构成的无线网络，通 过节点的协同工作来采集和处理网络覆盖区域中的目标信息近年来的研究表明， 无线传感器网络在环境与军事监控、地震与气候预测、地下、深水及外层空间探 索等许多方面都具有广泛的应用前景1 1 _ 3 】在传感器网络中，大量传感节点密集地， 随机被放置在要测量环境与非常接近要测量的环境中，测量环境通常是不可达的 地形或灾难区域但随机撤放的传感器节点往往由于节点的损毁，能量的耗尽以 及环境的变化等原因造成损坏，而不能正