087 计算机学报 201 年 1 引言无线传感器网络 (WirelesSensorNetwork, WSN) 的数据传输受信号衰减 干扰和通信环境等不确定因素的影响. 无线链路的可靠性是否受噪声干扰是随机的, 而对链路质量和干扰程度的估计是模糊的. 事实上, 无线链路的时延和可靠性同时具有模糊性和

Transcription

1 第 34 卷第 5 期 201 年 5 月 计算机学报 CHINESEJOURNALOFCOMPUTERS Vol.34No.5 May201 模糊随机环境下的无线传感器网络多约束多路径路由王小明 1) 卢俊岭 1) 李英姝 2) 郝克刚 3) 1)( 陕西师范大学计算机科学学院西安 71062) 2)( 佐治亚州立大学计算机科学系美国亚特兰大 30303) 3)( 西北大学软件工程研究所西安 71069) 摘要无线传感器网络路由约束同时存在模糊性和随机性, 传统路由算法只考虑随机性, 不能准确刻画无线传感器网络路由约束. 文中引入模糊随机过程理论和模糊随机规划方法, 对无线链路时延和可靠性的模糊性 随机性以及时变性进行统一建模, 提出了一种模糊随机多约束多路径路由模型, 能够更真实地反映无线传感器网络链路特征. 在此基础上, 设计了一种同时考虑模糊性 随机性和时变性的无线传感器网络多项式复杂度路由算法. 仿真实验结果表明, 文中所提出的算法能够灵活地调节路由约束强度, 满足具体应用对不同服务质量的需要. 关键词物联网 ; 无线传感器网络 ; 不确定性 ; 多路径路由 ; 约束 ; 算法中图法分类号 TP393 犇犗犐号 : /SP.J 犕狌犾狋犻犮狅狀狊狋狉犪犻狀犲犱犕狌犾狋犻狆犪狋犺犚狅狌狋犻狀犵犳狅狉犠犻狉犲犾犲狊犛犲狀狊狅狉犖犲狋狑狅狉犽狊犻狀狋犺犲犉狌狕狔犚犪狀犱狅犿犈狀狏犻狉狅狀犿犲狀狋 WANGXiao Ming 1) LUJun Ling 1) LIYing Shu 2) HAOKe Gang 3) 1)( 犛犮犺狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲, 犛犺犪狀狓犻犖狅狉犿犪犾犝狀犻狏犲狉狊犻狋狔, 犡犻 犪狀 71062) 2)( 犇犲狆犪狉狋犿犲狀狋狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲, 犌犲狅狉犵犻犪犛狋犪狋犲犝狀犻狏犲狉狊犻狋狔, 犃狋犾犪狀狋犪 30303, 犝犛犃 ) 3)( 犐狀狊狋犻狋狌狋犲狅犳犛狅犳狋狑犪狉犲犈狀犵犻狀犲狉犻狀犵, 犖狅狉狋犺狑犲狊狋犝狀犻狏犲狉狊犻狋狔, 犡犻 犪狀 71069) 犃犫狊狋狉犪犮狋 Fuzinesandrandomnesexistsimultaneouslyintheroutingconstraintsofwireles sensornetworks.however,thexistingroutingalgorithmsonlyconsiderandomnes,whichcan notdescribetheroutingconstraintsprecisely.thispaperadoptsfuzystochasticprocesand fuzyrandomprogrammingtomodelfuzines,randomnesandtime varyingpropertyofthede layandreliabilityofwireleslinks,andproposesafuzyrandommulticonstrainedmultipathrou tingmodeltoreflectrealcharacteristicsofwireleslinks.anovelroutingalgorithmforwireles sensornetworksispresented,whichconsidersfuzines,randomnesandtime varyingproperty andhaspolynomialcomplexity.simulationresultsshowthattheproposedalgorithmcanmet diferentnedsofpracticalaplicationsforqualityofservicebyflexiblyadjustingthestrengthof theroutingconstraints. 犓犲狔狑狅狉犱狊 InternetofThings;wirelessensornetwork;uncertainty;multipathrouting;con straint;algorithm 收稿日期 : ; 最终修改稿收到日期 : 本课题得到国家自然科学基金 ( ,607324, ) 和教育部留学回国人员科研基金资助. 王小明, 男,1964 年生, 博士, 教授, 博士生导师, 主要研究领域为无线传感器网络和安全普适计算技术.E mail: wangxm@snu.edu.cn. 卢俊岭, 男,1972 年生, 博士研究生, 讲师, 主要研究方向为无线传感器网络. 李英姝, 女,1978 年生, 博士, 副教授, 主要研究方向为无线传感器网络和信息物理融合系统. 郝克刚, 男,1936 年生, 教授, 博士生导师, 主要研究领域为计算机软件与理论.

2 087 计算机学报 201 年 1 引言无线传感器网络 (WirelesSensorNetwork, WSN) 的数据传输受信号衰减 干扰和通信环境等不确定因素的影响. 无线链路的可靠性是否受噪声干扰是随机的, 而对链路质量和干扰程度的估计是模糊的. 事实上, 无线链路的时延和可靠性同时具有模糊性和随机性. 例如, 在考虑服务质量 (Qualityof Service,QoS) 的 WSN 应用中, 人们可能要求 WSN 链路时延明显小于 40ms, 这种约束条件同时具有模糊性和随机性. 传统的研究方法将数据传输的不确定性笼统地归结为单一的随机性或者单一的模糊性, 因此不可能准确刻画真实的链路特征, 无法满足 WSN 的应用需求. 对链路质量的评估只强调随机性而忽略模糊性是不合理的, 主要原因有 : (1) 模糊性和随机性反映了不同性质的不确定性, 而且往往同时存在. 在上述 WSN 应用中, 链路时延小于 40ms 本身是确定的, 但时延小于 40ms 是否发生是不确定的, 这是随机性 ; 修饰词 明显 刻画了小于的程度, 但 明显 并没有准确的定义, 可根据实际应用约定 明显 的程度, 因此, 对 程度 的估计是不确定的, 这是模糊性. (2) 由于设备误差和方法近似等不确定性因素的存在, 链路时延和可靠性的真实值通常是无法获取的, 但结合实际应用需求, 对链路时延和可靠性进行模糊估计更符合实际情景. 在数据传输过程中, 链路时延和可靠性的模糊性和随机性是随着时间的推移不断变化的. 因此, 模糊性 随机性和时变性是无线链路时延和可靠性同时具有的不确定性特征. 我们知道, 模糊随机过程理论能够同时刻画事件的模糊性 随机性和时变性 [1], 可应用于 WSN 数据传输的 QoS 不确定性的分析和建模. 路由是从源节点到 Sink 节点选择一条或多条由节点构成的路径用于数据传输.QoS 路由是满足一种或多种应用约束条件的路由,QoS 路由研究一直是 WSN 领域的研究热点 [2 5].WSN 的节点资源和计算能力有限, 节点随机布设, 无线链路稳定性差, 节点通信相互干扰等特点, 决定了 WSN 路由涉及到时延 可靠性 能量和带宽等多种约束. 因此, WSN 的 QoS 路由研究只考虑其中某一种约束条件是无法满足实际应用需求的. 然而, 同时满足多种约束条件的 WSN 路由路径选择是 NP 完全问题 [6]. 多路径路由是选择多条路径进行数据传输的路由, 为了提高 WSN 数据传输的可靠性, 可将同一数据分组的多个副本使用多条路径同时进行传输. 另一方面, 为了实现负载均衡, 可建立源节点到 Sink 节点的多条不相交的路径轮流进行数据传输. 因此, 多路径路由可提高系统的容错性, 使节点消耗的能量均衡, 并且能够降低端到端的数据传输时延. 在近期的 WSN 多约束多路径路由研究中,Huang 等人提出的多约束多路径路由 (Multiconstrained Multipathrouting,MCMP) 模型和路由算法具有代表性 [7]. 与通常端到端的 QoS 机制相比较,MCMP 通过对路径质量的近似估计, 将端到端的 QoS 约束转化为局部链路的 QoS 约束, 从而把 NP 完全问题转化为复杂度适中的近似问题, 进而把 WSN 路由问题表示为时延和可靠性软约束下的随机优化问题, 并基于已有的近似方法将上述随机优化问题转化为确定的线性规划问题, 从而降低了问题求解的计算复杂度. 然而,MCMP 模型及其路由算法仅仅刻画了链路 QoS 不确定性中的随机性和时变性, 忽略了同时存在的模糊性, 这是不尽合理的. 本文以 MCMP 模型为基础, 同时考虑 WSN 的 QoS 路由约束的模糊性 随机性和时变性, 利用模糊随机规划和模糊随机过程理论进行分析和建模, 从而把 WSN 多约束路由问题表示为模糊随机非线性规划问题, 提出了一种新的模糊随机多约束多路径路由模型 (FuzyRandomMultiConstrainedMultiPath routing,frmcmp), 用模糊随机变量刻画链路时延和可靠性的模糊性和随机性, 用模糊概率表示 QoS 软约束 [8], 期望更真实地反映链路的不确定性因素. 为了降低模型求解的计算复杂度, 利用文献 [7] 的约束线性化思路和 Nanda 等人针对模糊机会约束规划问题提出的求解方法 [9] 把 FRMCMP 模型的模糊随机非线性约束转化为确定的线性约束. 在此基础上, 设计了相应的多项式时间复杂度路由算法 FRMCMP. 基于 NS2 的仿真实验结果表明, 基于 FRMCMP 模型的路由算法在不同 QoS 约束要求下, 具有良好的鲁棒性. 在 WSN 路由中, 同时考虑模糊性 随机性和时变性的优势在于 : (1) 链路质量的模糊感知更符合 WSN 的实际情况, 而且用模糊概率描述 QoS 软约束比单个实数刻画 QoS 软约束更为合理. (2) 通过在 FRMCMP 模型和路由算法中引入模糊数, 利用模糊数的截集运算的置信水平调节

3 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 QoS 约束的强弱程度, 能够满足不同及时分组递交率和平均时延约束的 WSN 应用需求. (3) 把 FRMCMP 模型中的 QoS 路由约束的模糊数退化为确定的实数, 则 FRMCMP 模型相应地转化为 MCMP 模型, 因此 MCMP 模型成为 FRMCMP 模型的特例, 表明 FRMCMP 模型具有更好的自适应性. ( 4) 用模糊随机过程描述 QoS 路由约束, 能够更好地反映无线链路的 QoS 约束的时变性. 本文第 2 节介绍 WSN 的 QoS 路由相关研究工作 ; 第 3 节提出 FRMCMP 模型, 并讨论 FRMCMP 模型模糊随机约束的线性化 ; 第 4 节描述 FRMCMP 路由算法 ; 第 5 节是仿真实验与结果分析 ; 最后总结全文. 2 相关工作当前大多数 WSN 的路由算法将 QoS 的不确定性笼统地归结为单一的随机性或模糊性, 分别采用概率论或模糊数学的方法进行研究 [7,10 12]. 在同一个路由算法中既考虑 QoS 约束的随机性, 又考虑其模糊性和时变性的研究工作目前尚未见文献报导. 文献 [7] 与本文工作紧密相关. 在文献 [7] 中,Huang 等人基于链路状态信息将多约束多路径路由表示为时延和可靠性软约束下的随机优化问题, 提出了一种基于本地邻居节点的分布式 QoS 路由模型, 并利用已有的近似方法对模型进行了线性化, 在满足 QoS 约束要求的前提下, 降低了模型求解的复杂 度. 该文的 MCMP 模型形式描述为烄 min 狓犼犼 犖犻 ) s.t. 犘狓犼犱犻犼 λ 犻 ) δ, 当 λ 犻烅 >0 (1) 犘 ( 1- 狓犼 (1- 狉犻犼 ) ζ 犻 ) ν 烆狓犼 =0 或 1, 其中,min 表示取最小值函数 ; 狓犼是路由选择的决策变量, 狓犼 =1 表示选择链路犾犻犼, 狓犼 =0 表示不选择链路犾犻犼 ; 犖 ( 犻 ) 是节点犻的邻居节点集合 ; 随机变量犱犻犼用于刻画链路犾犻犼的时延特征,λ 犻是节点犻一跳的时延要求,δ 是时延软约束的概率阈值 ; 随机变量狉犻犼用于刻画链路犾犻犼的可靠性特征,ζ 犻是节点犻一跳的可靠性要求,ν 是可靠性软约束的概率阈值. 文献 [7] 通过引入链路犾犻犼时延的随机变量犱犻犼的均值和方差以及单侧切比雪夫不等式进行概率估计, 从而对模 187 型的时延约束进行线性化, 将时延非线性约束转化为决策变量狓犼的线性约束 ; 通过引入链路犾犻犼可靠性的随机变量狉犻犼的均值和方差, 假设链路犾犻犼上已完成传输的所有数据和是近似服从正态分布的随机变量, 对约束式两边取对数运算并进行正态分布标准化, 从而对模型的可靠性约束进行线性化, 将可靠性非线性约束转化为决策变量狓犼的线性约束. 在此基础上, 设计了相应的 MCMP 路由算法. 仿真结果验证了 MCMP 路由算法在及时分组递交率 平均时延 超期率和单个分组传输代价方面的有效性. 但文献 [7] 的模型和路由算法仅仅刻画了链路时延和可靠性不确定性中的随机性和时变性, 而忽略了同时存在的模糊性, 这是很不合理的. 文献 [10] 从模糊逻辑的角度提出了一种在线多路径路由算法, 期望获得最长的网络生命周期, 其基本思想是将节点剩余能量定义为语言变量, 把网络生命周期定义为模糊集合, 并将指定的语言变量值映射到对应模糊集合的隶属函数值, 从而给出模糊生命周期的模糊隶属函数, 通过模糊隶属函数刻画 WSN 生命周期的良好程度. 仿真结果表明, 该算法能够有效延长网络生命周期. 文献 [10] 突出了 WSN 生命周期的模糊性, 但是忽略了 WSN 生命周期同时存在的随机性和时变性, 这仍然是不合理的. Nanda 针对模糊机会约束规划问题提出了一种用于同时考虑模糊性和随机性的优化模型的求解方法, 适用于约束中存在模糊随机变量的情形. 其基本思路是通过定义模糊随机变量均值和方差的 α 截集 (0 α 1) 运算和模糊数的偏序关系, 给出一种将不确定约束转化为确定非线性约束的方法, 能够将 FRMCMP 模型的模糊随机 QoS 约束转化为确定的非线性约束. 3 犉犚犕犆犕犘模型 3.1 预备知识以下叙述建立在读者已具有模糊数学基本知识的基础上. 本文涉及到的模糊数的偏序关系 模糊随机变量及其事件 均值与方差的 α 截集和独立性等概念和相关定理引用文献 [9], 在后续模型构造和约束线性化中被引用. 定义 1. 设犃和犅是两个模糊数, 其 α 截集是两个区间数, 分别记为犃 [α]=[ 犪 -(α), 犪 +(α)] 和犅 [α]=[ 犫 -(α), 犫 +(α)], 其中犪 -(α) 和犪 +(α) 分别是犃 [α] 的下限和上限, 均为实数而且满足犪 -(α)

4 287 计算机学报 201 年 犪 +(α), 犫 -(α) 和犫 +(α) 分别是犅 [α] 的下限和上限, 均为实数而且满足犫 -(α) 犫 +(α), 则两个模糊数之间的偏序关系 定义为犃 犅, 当且仅当对任意 α [0,1], 有犪 +(α) 犫 -(α). 定义 2. 模糊随机变量是从概率空间到模糊 变量集合的可测函数, 是取值为模糊数的随机变量. 设连续随机变量犡的概率密度函数为犳 ( 狓,θ), 其中 θ 为刻画概率密度函数的参数. 设模糊数 θ 是 θ 生成并用置信水平估计的不确定参数, 则犡为连续模糊随机变量, 其概率密度函数为犳 ( 狓,θ). 定义 3. 设连续模糊随机变量犡的概率密度函数为犳 ( 狓,θ),θ[α] 为模糊数 θ 的 α 截集, 犮和犱均为实数, 定义犡的事件 { 犮 犡 犱 } 的概率是一个模糊数, 该事件概率的 α 截集为犘 ( 犮 犡 犱 )[α]=[ 狆 -(α), 狆 +(α)] { } = 犱犮犳 ( 狓,θ)d 狓 θ θ[α], + 犳 ( 狓,θ)d 狓 =1, 其中, 区间下限狆 -(α) 和上限狆 +(α) 分别为狆 -(α)= min { 犱犮犳 ( 狓,θ)d 狓 θ θ[α], + 犳 ( 狓,θ)d 狓 =1, } 狆 +(α)= max { 犱犮犳 ( 狓,θ)d 狓 θ θ[α], + 犳 ( 狓,θ)d 狓 =1. } 定义 4. 设连续模糊随机变量犡的概率密度函数为犳 ( 狓,θ), 犿犡 (θ) 为犡对应的连续随机变量犡的均值, 定义犡的均值犿犡 (θ) 和方差 犡 (θ) 是模糊数, 犿犡 (θ) 和 犡 (θ) 的 α 截集分别为犿犡 (θ)[α]= { 犱犮狓犳 ( 狓,θ)d 狓 θ θ[α], + 犳 ( 狓,θ)d 狓 =1, } 犡 (θ)[α]= { 犱 ( 狓 - 犮犿犡 (θ) 2 犳 ( 狓,θ)d 狓 θ θ[α ], 犿犡 (θ) 犿犡 (θ)[α], + 犳 ( 狓,θ)d 狓 =1. } 定义 5. 设连续模糊随机变量犡犻 ( 犻 =1,2,, 狀 ) 的联合密度函数为犳 ( 狓 1, 狓 2,, 狓狀 ;θ), 犳 ( 狓犻 ;θ) 是犡犻的边缘密度函数, 则犡 1, 犡 2,, 犡狀是独立的当且仅当对任意 θ θ[α], 有犳 ( 狓 1, 狓 2,, 狓狀 ;θ)= 狀 犳 ( 狓犼,θ). 犼 =1 在上述定义的基础上, 定理 1 和定理 2 分别给出模糊随机变量线性组合的均值和方差的性质. 定理 1. 设犡, 犢和犣是连续模糊随机变量, 犡 犢和犣的均值分别为犿犡 (θ) 犿犢 (θ) 和犿犣 (θ), 犪和犫均为实数, 且犣 = 犪犡 + 犫犢, 则有犿犣 (θ)= 犪犿犡 (θ)+ 犫犿犢 (θ). 定理 2. 设犡, 犢和犣是连续模糊随机变量, 犡 犢和犣的方差分别为 犡 (θ) 犢 (θ) 和 犣 (θ), 犡和犢是独立的, 犪和犫均为实数, 且犣 = 犪犡 + 犫犢, 则有 犣 (θ)= 犪 2 犡 (θ)+ 犫 2 犢 (θ). 定理 3 是模糊数函数截集的性质. 定理 3. 设狔 = 犳 ( 狓 1, 2,, 狓狀 ) 为狀元实连续函数, 犃犻为实数域上的有界闭模糊数 ( 犻 =1,2,, 狀 ), 犃犻 [α] 为犃犻的 α 截集, 则对 α (0,1], 有犳 ( 犃 1, 犃 2,, 犃狀 )[α]= 犳 ( 犃 1[α], 犃 2[α],, 犃狀 [α]). 3.2 模型构造 MCMP 模型将链路的不确定性归结为随机性, 主要表现在链路的时延和可靠性均为随时间变化的随机变量 ( 即随机过程 ), 时延和可靠性两个约束均使用概率表示为软约束. 我们认为,WSN 链路时延和可靠性同时具有随机性 模糊性和时变性, 因此, 引入模糊随机规划方法和模糊随机过程理论将 MCMP 模型扩展为 FRMCMP 模型. 具体表现在 : (1) 将链路的时延和可靠性约束的不确定性区分为随机性和模糊性, 采用模糊随机变量描述链路 QoS 的双重不确定性, 时延和可靠性两个约束均采用模糊概率 ( 模糊数 ) 加以刻画. (2) 在模糊和随机双重不确定性基础上考虑链路时延和可靠性的时变性, 将 WSN 链路犾犻犼的时延和可靠性约束描述为模糊概率空间 (Ω,, 犘 ) 上的二元模糊随机过程 { 犇犻犼 ( 狋,ω), 犚犻犼 ( 狋,ω), 狋 犜 = (0,+ )}, 其中,Ω 为基本事件空间, 为 Ω 上的事件域, 犘为可测空间 (Ω, ) 上的模糊概率, 狋为时间参数,ω 为基本事件, 对任意狋 犜 ( 犜是时间参数集 ), 时延犇犻犼 ( 狋,ω) 和可靠性犚犻犼 ( 狋,ω) 约束均是 (Ω,, 犘 ) 上的模糊随机变量. 与 MCMP 模型相似的是, 本文也假设随机过程 { 犇犻犼 ( 狋,ω), 狋 犜 } 和 { 犚犻犼 ( 狋,ω), 狋 犜 } 在模糊概率空间 (Ω,, 犘 ) 上是相互独立的, 不同的是链路时延和可靠性的值是模糊数而不是实数, 从而能够更好地刻画链路的实际特征, 并通过模糊数置信水平调节 QoS 约束的强弱程度, 满足不同 QoS 约束的应用需求. 为了简化讨论, 我们在模型描述时省略狋和 ω. 下面具体描述 FRMCMP 模型的构造过程. 首先,FRMCMP 模型和 MCMP 模型的目标函数是相同的. 多路径路由可提高数据传输的可靠性, 但每个节点向多条路径发送同一个分组, 这样会增加节点的能量消耗. 为了尽可能降低能量消耗, 希望在满足 QoS 约束的前提下, 每次路由选择的路径数

5 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 最少, 于是目标函数为 min 狓犼 (2) FRMCMP 模型的时延约束在 MCMP 模型的基础上进行了扩展. 为了同时描述链路时延的模糊和随机双重不确定性, 引入模糊随机变量犱犻犼表示链路犾犻犼上的时延 ( 模糊数 ), 则狓犼犱犻犼表示未选择或选择链路犾犻犼进行数据传输需要的时延. 由于链路犾犻犼上的时延是模糊数, 则分组从源节点传输到节点犻的实际时延犇犻也是模糊数, 用三角模糊数 ( 犇犻 -, 犇犻 #, 犇犻 +) 表示, 其中犇犻 - 为时延模糊估计的下限, 犇犻 # 为实测的时延, 犇犻 + 为时延模糊估计的上限, 犇犻 - 犇犻 # 和犇犻 + 均为实数而且满足犇犻 - 犇犻 # 犇犻 +. 本文以下内容涉及到的三角模糊数均满足类似条件, 不再重复说明. 设犇表示分组从源节点到 Sink 节点的时延要求, 犺犻表示从节点犻到 Sink 节点的最小跳数, 则节点犻到 Sink 节点的中间各跳节点平均分担的时延 λ 犻表示为 λ 犻 = 犇 - 犇犻 # (3) 犺犻 λ 犻作为狓犼犱犻犼的比较上限. 于是, 在节点犻选择链路犾犻犼应满足的时延约束可表示为模糊随机变量犱犻犼的事件 { 狓犼犱犻犼 λ 犻 }, 根据定义 3, 其概率为模糊数. 引入模糊数 δ 表示事件 { 狓犼犱犻犼 λ 犻 } 发生至少应满足的概率阈值. 于是, 当 λ 犻 >0 时, 节点犻选择链路犾犻犼应满足的时延软约束为犘 ( 狓犼犱犻犼 λ 犻 ) δ (4) 最后, 我们采用与时延约束类似的思路来扩展 MCMP 模型中的可靠性约束. 为了同时描述链路可靠性的模糊和随机双重不确定性, 引入模糊随机变量狉犻犼表示链路犾犻犼上的可靠性 ( 模糊数 ), 则 1- 狉犻犼表示分组在链路犾犻犼上没有成功传输的概率 ( 不可靠性 ). 由于 WSN 链路本身可靠性不高, 而且一条端到端的路径的可靠性由组成路径的各条链路的可靠性的乘积决定, 因此单条路径的可靠性通常很难满足数据传输的可靠性要求, 需要在源节点和每个中间节点确定由多少个前向邻居节点 ( 即邻居节点犼的犺犼小于当前节点犻的犺犻 ) 转发分组来保证可靠性约束. 引入犚表示分组从源节点到 Sink 节点的端到端的可靠性要求, 犚犻表示分组通过中间节点犻的路径上分配到的可靠性要求. 由于链路犾犻犼上的可靠性是模糊数, 则犚犻也是模糊数, 用三角模糊数 ( 犚犻 -, 犚犻 #, 犚犻 +) 表示, 其中犚犻 - 为可靠性模糊估计的下限, 犚犻 # 为实测的可靠性, 犚犻 + 为可靠性模糊估计的上限. 于是节点犻到 Sink 节点的中间各跳节点平均分担的可靠性 ζ 犻表示为 ζ 犻 = 犺犻犚犻槡 # (5) ζ 犻作为节点犻的可靠性约束的比较下限. 节点犻所分担的可靠性 τ 犻由通过节点犻的多条链路保证, 于是有 τ 犻 =1- 狓犼 (1- 狉犻犼 ) (6) 用犚犻犼表示链路犾犻犼分担的可靠性,ζ 犻由通过节点犻的多条链路保证, 于是有 ζ 犻 1- ( 1- 狓犼犚犻犼 ) (7) 对式 (7) 两边取对数有犼 lg (1- 狓犼犚犻犼 ) lg(1-ζ 犻 ) (8) 犖 ( 犻 ) 节点犻应满足的可靠性约束可表示为模糊随机变量狉犻犼的事件 {τ 犻 ζ 犻 }, 根据定义 3, 其概率为模糊数. 引入模糊数 ν 表示事件 {τ 犻 ζ 犻 } 发生至少应满足的概率阈值, 则节点犻应满足的可靠性软约束为犘 (τ 犻 ζ 犻 ) ν (9) 于是,FRMCMP 模型概括为烄 min 狓犼 烅 s.t. (10) 犘 ( 狓犼犱犻犼 λ 犻 ) δ 烆犘 (τ 犻 ζ 犻 ) ν 其中, 狓犼 =0 或 1,τ 犻 =1- 狓犼 (1- 狉犻犼 ),λ 犻 = ( 犇 - 犇犻 #)/ 犺犻,ζ 犻 = 犺犻犚犻槡 #. 式 (10) 与式 (1) 中含义不同的符号总结如下 : 犱犻犼为同时刻画链路犾犻犼上时延模糊性和随机性的模糊随机变量,δ 为时延约束满足的模糊概率阈值 ( 模糊数 ); 狉犻犼为同时刻画链路犾犻犼上可靠性的模糊性和随机性的模糊随机变量,ν 为可靠性约束满足的模糊概率阈值 ( 模糊数 ); 犇为数据分组从源节点到 Sink 节点的时延要求, 犇犻 # 为分组从源节点到节点犻的实际时延 ( 三角模糊数最大隶属度对应的值 ), 犺犻为节点犻到 Sink 节点的最小跳数, 犚犻 # 为分组通过中间节点犻的路径上分配到的可靠性要求 ( 三角模糊数最大隶属度对应的值 ). 3.3 模型线性化 时延约束的线性化链路时延犱犻犼是未知分布的模糊随机变量, 根据定义 2, 它们是取值为模糊数的随机变量, 根据定义 4, 它们的均值和方差也是模糊数. 设犱犻犼的均值犿犻犼 方 差 σ犻犼和模糊概率阈值 2 δ 均为三角模糊数, 分别记为犿犻犼 =( 犿 -, 犿 #, 犿 +), 犻犼 =( -, #, +),δ= (δ-,δ#,δ+), 其中犿 - 犿 # 和犿 + 分别是犿犻犼的下限 最大隶属度对应的值和上限, - # 和 + 分别是 犻犼的下限 最大隶属度对应的值和上限,δ- δ# 和 δ+ 387

6 分别是 δ 的下限 最大隶属度对应的值和上限, 而且满足 0 δ- δ# δ+ 1. 由三角模糊数截集运算可知, 犿犻犼 σ犻犼和 2 δ 的 α 截集犿犻犼 [α] 犻犼 [α] 和 δ[α] 分别为烄犿犻犼 [α]=[ 犿 -+α( 犿 #- 犿 -), 犿 +-α( 犿 +- 犿 #)] 烅 犻犼 [α]=[ -+α( #- -), +-α( +- #)] 烆 δ[α]=[δ-+α(δ#-δ-),δ+-α(δ+-δ# )] ( 1) 为便于求解, 对式 (4) 作如下变换. 令犝 = 狓犼犱犻犼, 则式 (4) 可表示为犘 ( 犝 λ 犻 ) δ (12) 由于狓犼的值只能是 0 或 1, 则有狓犼 = 狓 2 犼. 设犝的均值犿狌犱和方差 σ狌犱的 2 α 截集分别为犿狌犱 [α] 和 狌犱 [α], 根据定理 1 和 2, 有犿狌犱 [α]= 狓犼犿犻犼 [α] 烅烄烆 狌犱 [α]= 狓犼 犻犼 [α ] (13) 由式 (1) 和式 (13) 得烄犿狌犱 [α]=[ 犿狌犱 -(α), 犿狌犱 +(α)] =[ 狓犼犿 -+ 狓犼 α( 犿 #- 犿 -), 狓犼犿 +- 狓犼烅 α( 犿 +- 犿 #)] (14) 狌犱 [α]=[ 狌犱 -(α), 狌犱 +(α)] =[ 狓犼 -+ 狓犼 α( #- -), 烆狓犼 +- 狓犼 α( +- #)] 其中, 犿狌犱 -(α) 和犿狌犱 +(α) 分别是犿狌犱 [α] 的下限和上限, 狌犱 -(α) 和 狌犱 +(α) 分别是 狌犱 [α] 的下限和上限. 设犝是模糊随机变量犝对应的随机变量, 犳 ( 狌,θ) 是犝的概率密度函数, 犿狌犱和 σ狌犱分别是犝的均值和方差 2. 对式 (12) 左端取截集, 由定义 3 得犘 ( 犝 λ 犻 )[α]= { 犘 ( 犝 λ 犻 ) θ θ[α], 犳 ( 狌,θ) =1 } =1- { 犘 ( 犝 λ 犻 ) θ θ[α], 犳 ( 狌,θ) =1(15) } 设 ξ 是随机变量, 犈 (ξ) 犞犪狉 (ξ) 分别是 ξ 的均值和方差,η 是实数, 且 η>0, 由单侧切比雪夫不等式 得 则 487 计算机学报 201 年 犘 (ξ- 犈 (ξ) η) 犞犪狉 (ξ) 犞犪狉 (ξ)+η 2, 犘 ( 犝 λ 犻 )= 犘 ( 犝 - 犿狌犱 λ 犻 - 犿狌犱 ) σ2 狌犱狌犱 +(λ 犻 - 犿狌犱 ) 2, 1- 犘 ( 犝 λ 犻 ) 1- σ2 狌犱 狌犱 +(λ 犻 - 犿狌犱 ) 2 = ( λ 犻 - 犿狌犱 ) 2 狌犱 +(λ 犻 - 犿狌犱 ) 2. 令 Δ{ = 犿狌犱 犿狌犱 [α], 狌犱 狌犱 [α], θ θ[α],,θ)} 犳 ( 狌 =1, { 则引入新的区间数 (λ 犻 - 犿狌犱 ) 2 狌犱 +(λ 犻 - 犿狌犱 ) 2 }Δ, 可验证其对犿狌犱和 σ狌犱均是递减的 2, 于是 {(λ 犻 - 犿狌犱 ) 2 狌犱 +(λ 犻 - 犿狌犱 ) 2 }Δ= [ ( λ 犻 - 犿狌犱 +(α) 2 狌犱 +(α)+(λ 犻 - 犿狌犱 +(α) 2, (λ 犻 - 犿狌犱 -(α) 2 狌犱 -(α)+(λ 犻 - (16) 犿狌犱 -(α)]2 为使式 (12) 成立, 由式 (16) 式 (1) 和定义 1 得 (λ 犻 - 犿狌犱 +(α) 2 狌犱 +(α)+(λ 犻 - 犿狌犱 +(α) 2 δ+-α(δ+-δ#)(17) 将式 (14) 右端的上限代入式 (17) 得 (λ 犻 - 狓犼犆犿 ) 狓犼犆 2 +(λ 犻 - 狓犼犆犿 ) 2 犆狆 (18) 其中, 犆犿 = 犿 +-α( 犿 +- 犿 #), 犆 = +-α( +- #), 犆狆 =δ+-α(δ+-δ#). 由于狓犼 = 狓 2 犼, 式 (18) 整理后得狓犼犆犱 (λ 犻 ) 2 (19) 其中, 犆犱 =2λ 犻犆犿 -( 犆犿 ) 2 + 犆狆 1- 犆狆犆. 由于式 (19) 中犆犱是常数, 因此这是线性约束, 从而实现了时延约束的线性化 可靠性约束的线性化链路犾犻犼的可靠性狉犻犼是未知分布的模糊随机变量, 根据定义 2, 狉犻犼是取值为模糊数的随机变量. 根据定义 4, 狉犻犼的均值和方差也是模糊数. 将分组在链路犾犻犼上的一次传输看作一次试验, 每次传输成功的概率可能不相同. 可以将一次传输成功的概率看作为模糊数 ε, 则一次传输失败的概率为 1-ε. 设犓表示链路犾犻犼上已经完成的分组传输的次数, 分组在链路犾犻犼上每次传输是相互独立的, 则链路犾犻犼上执行犓次分组传输之后, 成功传输的分组次数可用模糊随机变量狀犻犼表示, 并且狀犻犼 = 犓狉犻犼. 由于狉犻犼的取值是模糊数, 所以狀犻犼服从模糊二项分布, 表示为狀犻犼 ~ 犅 ( 犓,ε). 考虑到正态分布的普遍性, 我们利用模糊正态分布犖 ( 犓 ε, 犓 ε(1-ε) 近似表示模糊二项分布犅 ( 犓,ε), 以便于链路可靠性的计算 [8]. 为使近似计算更合理, 设 ε 为三角模糊数表示的模糊概率 ε 的最大隶属度对应的值, 并且满足犓 ε>5 和犓 (1-ε)>5, 此时, 用模糊正态分布近似表示模糊二项分布的误差较小. 为了降低可靠性约束的计算复杂度, 先定义如下概念.

7 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 定义 6 [13]. 设正三角模糊数犙 =( 犪, 犫犮 ),LR 型正三角模糊数犙 =( 犫 - 犪, 犮 - 犫 ), 其中犪 犫和犮均为实数, 而且满足 0< 犪 犫 犮, 定义犙 和犙的对数分别为 lg 犙 =(lg( 犫 / 犪 ),lg 犫,lg( 犮 / 犫 ),lg 犙 = (lg 犪,lg 犫,lg 犮 ). 对任意两个正三角模糊数犙 1 和犙 2, 则犙 1 和犙 2 的乘积的对数满足 lg( 犙 1 犙 2)=lg 犙 1+ lg 犙 2. 定义 7. 设区间数犐 =[ 犪, 犫 ], 其中犪和犫均为实数, 而且满足 0< 犪 犫, 数犪也可表示为 [ 犪, ], 定义犐的映射犺 ( 犐 )=[ 犺 ( 犪 ), 犺 ( 犫 )]. 定义 8. 设区间数序列犐犻 =[ 犪犻, 犫犻 ], 其中犪犻和犫犻均为实数, 而且满足 0< 犪犻 犫犻,1 犻 犖, 犖是正 犘 ( 狓犼狉犻犼 狓犼犚犻犼 ) ν (2) 设式 (2) 左端模糊概率满足定义 6, 对式 (2) 两边取对数得 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 ) lgν (23) 当狓犼 =0 时, 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )=1, 则 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )=0, 因此 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )= 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ); 当狓犼 =1 时, 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )= 犘 ( 狉犻犼 犚犻犼 ), 则 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )=lg 犘 ( 狉犻犼 犚犻犼 ), 因此 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )= 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ); 综合狓犼取值的两种情形, 则 lg 犘 ( 狓犼狉犻犼 狓犼犚犻犼 )= 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ). 于是, 式 (23) 可写成 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ) lgν (24) 令犃犼 = 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ), 则式 (24) 左端可写成 犃犼. 用 犖 ( 犻 ) 表示节点犻的邻居节点的个数, 记犳 ( 犃 1, 犃 2,, 犃 犖 ( 犻 ) )= 犃犼. 设 β (0,1], 犃犼 [β] 为犃犼的 β 截集, 由定理 3 得 ( 犼 )[β]= 犃犼 [β] 犳 ( 犃 1, 犃 2,, 犃 犖 ( 犻 ) )[β]= 犃 (25) 令犅犼 = 犘 ( 狉犻犼 犚犻犼 ), 犅犼 [β] 为犅犼的 β 截集, 则犃犼 = 狓犼 lg 犅犼, 把定义 7 中的映射犺实例化为对数函数, 则由定理 3 和定义 7 得犃犼 [β]= 狓犼 lg( 犅犼 [β]) (26) 将式 (26) 代入式 (25) 得犳 ( 犃 1, 犃 2,, 犃 犖 ( 犻 ) )[β]= 狓犼 lg( 犅犼 [β])(27) 设狉犻犼的均值为犕犻犼, 狉犻犼的方差为 ρ 2 犻犼, 由 节已知狀犻犼服从模糊正态分布, 得狀犻犼 ~ 犖 ( 犓犕犻犼, 犓 2 ρ 犖犖犖整数, 定义区间数序列之和 犐犻犻 =1 = [ 犪犻犻 =1, 犫犻 ] 2 犻犼 ) (28), 又犅犼可变换为犅犼 = 犘 ( 狉犻犼 - 犚犻犼 0)= 犘 ( 狀犻犼 - 犻 =1 犓犚犻犼 0), 令狌犼 = 狀犻犼 - 犓犚犻犼, 由定理 1 2 和式 (28), 它仍然是一个区间数. 则有狌犼在上述概念基础上, 对可靠性约束作如下变换 ~ 犖 ( 犓犕犻犼 - 犓犚犻犼, 犓 2. ρ 2 犻犼 ), 设狌犼的均值犕狌犼和方差把式 (9) 左端的模糊随机事件 {τ 犻 ζ 犻 } 进一步加强为 ρ狌犼的 2 β 截集分别为犕狌犼 [β] 和 ρ 2 狌犼 [β], 犕犻犼和 ρ犻犼的 2 { 狓犼狉犻犼 狓犼犚犻犼 }, 将犚犻犼看作正三角模糊数 ( 犚犻犼, β 截集分别为犕犻犼 { [β] 和 ρ 2 犻犼 [β], 根据定理 1 和 2, 则有犕狌犼 [β]= 犓犕犻犼 [β]- 犓犚犻犼犚犻犼, 犚犻犼 ), 设犕犻犼表示狉犻犼的均值, 此时犚犻犼满足 ρ 犚犻犼 犕犻犼 (20) 2 狌犼 [β]= 犓 2 ρ 2 犻犼 [β ] (29) 设狉犻犼的均值犕犻犼 狉犻犼的方差 ρ犻犼和式假设分组在链路犾犻犼上每次传输的可靠性狉犻犼是相互 2 (2) 右端模糊概率阈值 ν 均为三角模糊数, 分别记为犕犻犼 = 独立的, 于是有犘 (τ 犻 ζ 犻 )= 犘 ( ( ( 犕 -, 犕 #, 犕 +),ρ 犼 犖犻 ) 狓犼狉犻犼 狓犼犚犻犼 )) 2 犻犼 =(ρ 2 -,ρ 2 #,ρ 2 +),ν=(ν-,ν#, ν+), 其中犕 - 犕 # 和犕 + 分别是犕犻犼的下限 最大隶 = 犘 ( 狓犼狉犻犼 狓犼犚犻犼 ) (21) 属度对应的值和上限,ρ 2 - ρ 2 # 和 ρ 2 + 分别是 ρ犻犼的下 限 最大隶属度对应的值和上限 2,ν- ν# 和 ν+ 分别是将式 (21) 代入式 (9), 则可靠性约束可表示成 ν 的下限 最大隶属度对应的值和上限, 而且 0< ν- ν# ν+ 1. 由三角模糊数截集运算可知, 犕犻犼 ρ犻犼和 2 ν 的 β 截集犕犻犼 [β] ρ 2 犻犼 [β] 和 ν[β] 分别为烄犕犻犼 [β]=[ 犕 -+β( 犕 #- 犕 -), 犕 +-β( 犕 +- 犕 #)] 烅 ρ 2 犻犼 [β]=[ρ 2 -+β(ρ 2 #-ρ 2 -),ρ 2 +-β(ρ 2 +-ρ 2 #)] 烆 ν[β]=[ν-+β(ν#-ν-),ν+-β(ν+-ν# )] ( 30) 由式 (20) 式 (30) 和定义 1, 得 0 犚犻犼 犕 -+β( 犕 #- 犕 -) (31) 由式 (29) 和式 (30) 得 烄犕狌犼 [β]=[ 犓犕 -+ 犓 β( 犕 #- 犕 -)- 犓犚犻犼, 犓犕 +- 犓 β( 犕 +- 犕 #)- 犓犚犻犼 ] 烅 ρ 2 狌犼 [β]=[ 犓 2 ρ 2 -+ 犓 2 (32) β(ρ 2 #-ρ 2 -), 烆犓 2 ρ 2 +- 犓 2 β(ρ 2 +-ρ 2 #)] 由于犅犼 = ( 狌犼 0), 由定义 3 得犅犼 [β]= 犘 ( 狌犼 0)[β]=[ 犫犼 -(β), 犫犼 +(β)](3) 用 Φ 表示正态分布函数, 犿狌犼 -(β) 和犿狌犼 +(β) 分别表示犕狌犼 [β] 的下限和上限,ρ 狌犼 -(β) 和 ρ 狌犼 +(β) 分别表示均方差 ρ 狌犼的 β 截集 ρ 狌犼 [β] 的下限和上限, 则犅犼 [β] 587

8 687 计算机学报 201 年 的下限犫犼 -(β) 和上限犫犼 +(β) 分别为犫犼 -(β)=1-φ 0- 犿狌犼 -(β) ρ 狌犼 -(β ) (, 犫犼 +(β)=1-φ 0- 犿狌犼 +(β) ) ρ 狌犼 +(β ) ( 34) 将式 (3) 代入式 (27), 由定义 7 和定义 8 得式 (24) 左端的 β 截集为 ( 犼 狓犼 lg 犘 ( 狉犻犼 犚犻犼 ))[β]= 犖 ( 犻 ) [ 犼 狓犼 lg( 犫犼 -(β 犖 ( 犻 ) ), 狓犼 lg( 犫犼 +(β] )(35) 由式 (30) 定理 3 和定义 7, 并把定义 7 中的映射犺用对数函数实例化, 则式 (24) 右端的 β 截集为 (lgν)[β]= [lg(ν-+β(ν#-ν-),lg(ν+-β(ν+-ν#)](36) 为使式 (24) 成立, 由式 (35) 式 (36) 和定义 1 得犼 狓犼 lg( 犫犼 -(β) lg(ν+-β(ν+-ν#)(37) 犖 ( 犻 ) 将式 (34) 和式 (32) 代入式 (37) 整理得 ( ) 犆犕犼 狓犼 lgφ - 犚犻犼 犖 ( 犻 ) 槡犆 ρ2 lg(ν+-β(ν+-ν#)(38) 其中, 犆犕 = 犕 -+β( 犕 #- 犕 -), 犆 ρ 2 =ρ 2 -+β(ρ 2 #- ρ 2 -). 式 (38) 左端括号中是常数, 因此这是线性约束, 实现了可靠性约束的线性化. 3.4 链路时延和可靠性的时变性为了描述链路的时延和可靠性随时间变化的特征, 我们扩展文献 [7] 的均方差加权公式, 使其适用于三角模糊数的情形. 把链路犾犻犼的时延用三角模糊数表示为犱犻犼 =( 犱犻犼 -, 犱犻犼 #, 犱犻犼 +), 其中犱犻犼 - 为时延模糊估计的下限, 犱犻犼 # 为实测的时延, 犱犻犼 + 为时延模糊估计的上限 ; 犱犻犼的均方差表示为 σ 犻犼 =(σ-,σ#,σ+), 其中 σ- 为时延均方差模糊估计的下限,σ# 为实际的时延均方差,σ+ 为时延均方差模糊估计的上限. 类似地, 链路犾犻犼的可靠性表示为狉犻犼 =( 狉犻犼 -, 狉犻犼 #, 狉犻犼 +), 其中狉犻犼 - 为可靠性模糊估计的下限, 狉犻犼 # 为实测的可靠性, 狉犻犼 + 为可靠性模糊估计的上限 ; 狉犻犼的均方差表示为 ρ 犻犼 =(ρ-,ρ#,ρ+), 其中 ρ- 为可靠性均方差模糊估计的下限,ρ# 为实际的可靠性均方差,ρ+ 为可靠性均方差模糊估计的上限. 则链路犾犻犼的时延均方差计算公式为 烄 σ-( 狋 )=(1- 狑犱 ) σ-( 狋 -1)+ 狑犱 犱犻犼 ( 狋 )- 犱犻犼 ( 狋 -1) σ#( 狋 )=(1- 狑犱 ) σ#( 狋 -1)+ 烅狑犱 犱犻犼 ( 狋 )- 犱犻犼 ( 狋 -1) (39) σ+( 狋 )=(1- 狑犱 ) σ+( 狋 -1)+ 狑犱 犱犻犼 ( 狋 )- 犱犻犼烆 ( 狋 -1 ) 其中, 狑犱用于平滑链路犾犻犼的时延的均方差变化程度, 并且 0 狑犱 1. 链路犾犻犼的可靠性均方差计算公式为 烄 ρ-( 狋 )=(1- 狑狉 ) ρ-( 狋 -1)+ 狑狉 狉犻犼 ( 狋 )- 狉犻犼 ( 狋 -1) ρ#( 狋 )=(1- 狑狉 ) ρ#( 烅狋 -1)+ 狑狉 狉犻犼 ( 狋 )- 狉犻犼 ( 狋 -1) ρ+( 狋 )=(1- 狑狉 ) ρ+( 狋 -1)+ 烆狑狉 狉犻犼 ( 狋 )- 狉犻犼 ( 狋 -1 ) (40) 其中, 狑狉用于平滑链路犾犻犼的可靠性的均方差变化程度, 并且 0 狑狉 1. 链路犾犻犼的时延和可靠性的均方差的变化既受参数狑犱和狑狉的影响, 也受模糊数置信水平 α 和 β 的影响. 参数狑犱和狑狉取较小的值, 可降低狑犱和狑狉对链路时延和可靠性均方差的影响, 从而突出算法模糊性扩展的有效性. 4 犉犚犕犆犕犘算法 FRMCMP 路由算法建立在 FRMCMP 模型基础上, 同时考虑了链路时延和可靠性的模糊性 随机性和时变性. 以下先给出路由节点选择算法, 在此基础上, 设计模糊随机多约束多路径路由算法. 算法 1. 路由节点选择. 输入 : 端到端时延要求犇, 端到端可靠性要求犚, 当前节点犻及其邻居列表犖 ( 犻 ), 链路犾犻犼的时延约束概率阈值 δ, 节点犻的可靠性约束概率阈值 ν, 链路犾犻犼的时延约束模糊数置信水平 α, 节点犻的可靠性约束模糊数置信水平 β, 链路犾犻犼的时延均方差更新计算权值狑犱, 链路犾犻犼的可靠性均方差更新计算权值狑狉输出 : 节点犻的满足约束的下一跳节点集合犖犙 ( 犻 ) 1. 初始化, 置犖 ( 犻 ) 中每个节点犼对应的链路犾犻犼是否满足约束的标记犉犙狅犛犻犼为 -1, 表示约束未被满足 ; 2. 将节点犻的前向邻居节点标记为候选下一跳节点, 即置犉犙狅犛犻犼为 0; 3. 根据式 (3) 和 (5) 分别计算 λ 犻和 ζ 犻 ; 4. 根据式 (39) 和 (40) 分别更新链路犾犻犼的时延和可靠性的模糊均方差 ; 5. 根据式 (19) 判断犉犙狅犛犻犼为 0 的链路犾犻犼是否满足时延约束, 如果满足则标记节点犼为满足时延约束的下一跳节点, 即置犉犙狅犛犻犼为 1, 否则犉犙狅犛犻犼仍为 0; 6. 将犖 ( 犻 ) 中犉犙狅犛犻犼为 1 的链路按可靠性犚犻犼由大到小排序 ; 7. 根据式 (38) 和式 (8) 依次判断犉犙狅犛犻犼为 1 的链路是否满足可靠性约束, 如果满足则标记节点犼为同时满足时延和可靠性约束的下一跳节点, 即置犉犙狅犛犻犼为 2, 否则犉犙狅犛犻犼仍为 1;

9 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 8. 返回所有犉犙狅犛犻犼为 2 的链路犾犻犼对应的节点集合犖犙 ( 犻 ). 算法 1 的正确性是容易验证的, 其时间复杂度为犗 ( 犖 ( 犻 ) log( 犖 ( 犻 ) ), 其中 犖 ( 犻 ) 表示节点犻的邻居节点个数. 以算法 1 为基础, 设计模糊随机多约束多路径路由算法. 算法 2. 模糊随机多约束多路径路由. 输入 : 源节点,Sink 节点, 源节点待发送的数据分组输出 : 路由成功或失败 1. 置节点路由选择队列犚犖犙队列为空, 置分组传输成功计数器犛犝犆为 0; 2. 将源节点作为当前节点犻, 然后节点犻入队列犚犖犙 ; 3. 从犚犖犙中取一个节点作为当前节点犻, 如果节点犻是 Sink 节点, 则犛犝犆 犛犝犆 +1, 转步 3; 否则, 转步 4; 4. 调用算法 1, 得到节点犻的所有下一跳节点集合犖犙 ( 犻 ), 转步 5; 5. 如果节点犻的犖犙 ( 犻 ) 集合为空, 则转步 6; 否则, 从当前节点犻向犖犙 ( 犻 ) 中的所有节点发送同一分组的副本, 犖犙 ( 犻 ) 中所有节点入队列犚犖犙, 转步 7; 6. 如果节点犻是源节点, 则犛犝犆 0, 转步 8; 否则, 转步 7; 7. 如果队列犚犖犙为空, 则转步 8; 否则, 转步 3; 8. 如果犛犝犆的值大于等于 1, 则路由成功 ; 否则, 路由失败. 算法 2 中调用了算法 1, 于是在算法 1 的基础上, 算法 2 的正确性也是容易验证的, 其在最坏情形下的时间复杂度不超过犗 ( 犞 犛 2log 犛 ), 其中犞表示 WSN 的节点数, 犛表示所有节点的邻居节点个数的最大值. FRMCMP 算法对 MCMP 算法的扩展体现在以下两点 : (1) 算法 1 中步 5 对时延约束判断使用扩展后的式 (19), 步 7 对可靠性约束判断使用扩展后的式 (38), 这两个线性约束式是引入模糊随机变量和模糊数后的 FRMCMP 模型线性化的结果. (2) 算法 1 对链路时延和可靠性的比较阈值以及均方差计算公式进行适当的模糊性扩展, 包括步 3 中 λ 犻和 ζ 犻分别使用新的式 (3) 和 (5) 进行计算, 步 4 中 σ 犻犼和 ρ 犻犼更新分别使用扩展后的式 (39) 和 (40) 进行计算. FRMCMP 算法对链路时延和可靠性约束的判断同时考虑模糊性 随机性和时变性, 既能够更真实地反映链路的实际特点, 又可以通过调整模糊数置信水平改变链路约束的强弱程度, 从而更好地满足不同 QoS 约束的路由.MCMP 算法在仿真时的性能指标与 WSN 路由算法 God 最为接近,God 路由 787 算法是在假设每个节点都知道链路时延和可靠性的精确信息的基础上进行路径选择的, 普遍认为 God 算法是最优路由算法的评价参照文献 [7]. 当置信水平 α 和 β 取 1 时, 则 FRMCMP 算法中的式 (19) 和 (38) 就转化为 MCMP 模型线性化的结果. 我们的仿真实验结果表明,FRMCMP 算法在最好情形下比 MCMP 算法在及时分组递交率和平均时延方面具有明显的优势, 而在最坏情形下二者比较接近. 因此, 可以认为 FRMCMP 算法具有更好的灵活性和自适应性, 与最优算法 God 的性能接近. 5 仿真结果及分析 5.1 仿真目标和仿真环境为了验证 FRMCMP 算法的有效性, 我们在满足端到端时延和可靠性约束的情形下, 分析 WSN 的平均及时分组递交率 平均时延和单个分组传输代价. 其中平均及时分组递交率是指 Sink 节点接收的满足端到端时延约束的分组数与源节点发送的分组数的比值 ; 平均时延是指 Sink 节点收到的满足端到端时延约束的所有分组的端到端时延的平均值 ; 单个分组传输代价是指单个分组的平均传输数. 主要目标包括 : (1)WSN 在链路时延和可靠性的随机性基础上引入模糊性后, 采用 FRMCMP 算法的平均及时分组递交率和平均时延与采用 MCMP 算法相比, 随着链路 QoS 的模糊感知, 是否具有较好的区间变化, 是否更符合 WSN 的实际情况. (2) 随着值为模糊数的链路时延和概率的置信水平的变化,WSN 的平均及时分组递交率和平均时延在不同端到端时延约束下是否符合某种变化趋势, 从而可方便地通过调整置信水平改变链路约束的强弱程度, 更好地适应不同的 WSN 应用场景. (3) 通过单个分组传输代价观察 FRMCMP 算法与 MCMP 算法相比, 节点能量消耗是否有明显变化. 仿真实验采用 NS2, 将传感器节点随机部署在矩形区域中,Sink 节点定位于仿真区域的右下角, 每次实验源节点在区域中随机产生, 实验结果为 5 次实验的平均数据, 仿真参数设置如表 1 所示. 本文讨论在链路时延约束同时具有模糊和随机变化的情形下, 采用 FRMCMP 算法的 WSN 在不同端到端时延要求下的平均及时分组递交率和平均时延, 同时选用仿真和建模常用的均匀分布 [7]. 端到端时延

10 87 计算机学报 201 年 要求在闭区间 [470,530]( 单位为 ms) 变化, 每隔 10ms 取一次值, 共有 7 个时延要求等级. 链路时延在闭区间 [1,40]( 单位为 ms) 随机变化, 链路时延上限分两种情况 : 明显小于给定时延 40ms 的三角模糊数 (36,36,40) 和略微大于给定时延 40ms 的三角模糊数 (40,40,42). 模糊概率也分两种情形 : 明显小于指定概率阈值 0.95 的三角模糊数 (0.85,0.85, 0.95) 和略微大于指定概率阈值 0.95 的三角模糊数 (0.95,0.95,0.9). 置信水平 α 在闭区间 [0,1] 取值, 间隔为 0.2, 共有 6 个等级水平. 链路可靠性在闭区间 [0.8,1] 内随机变化, 可靠性约束的概率阈值为 由于时延约束的线性化过程利用了切比雪夫不等式, 因此时延约束的概率阈值需通过乘以小于 1 的正数因子进行调节, 从而得到路由问题的可行解 [7]. 表 1 仿真参数的设置 参数值网络区域 50m 50m 传感器节点数 10 源节点数 Sink 节点数 1 传输半径 50m 分组大小 150bytes 分组发送速率 1packet/s MAC 协议 仿真时间 180s 5.2 仿真结果为了方便叙述,FRMCMP 算法在链路 QoS 约束和模糊概率变化较大, 即链路时延上限明显小于给定时延, 模糊概率明显小于指定概率阈值的情形用 case1 表示 ; 在链路 QoS 约束和模糊概率变化较小, 即链路时延上限略微大于给定时延, 模糊概率略微大于指定概率阈值的情形用 case2 表示. 图 1 和图 2 分别给出了 WSN 在链路 QoS 约束和模糊概率变化情形下, 当模糊数置信水平 α=0.8 时, 在不同端到端时延要求下, 采用 FRMCMP 算法的及时分组递交率和平均时延的变化情况, 并与采用 MCMP 算法的及时分组递交率和平均时延进行比较. 从图 1 可看出, 与采用 MCMP 算法相比, 采用 FRMCMP 算法的及时分组递交率随着链路 QoS 的模糊感知具有较好的区间变化, 尤其在 case1 情形下效果更为明显. 随着端到端时延要求的增大, 采用 FRMCMP 算法的及时分组递交率受满足时延约束的概率要求和链路时延模糊变化影响的程度逐渐减弱. 从图 2 可看出, 采用 FRMCMP 算法的平均时延在 65ms 附近的区间内变化, 较小幅度地扩展了 MCMP 算法的平均时延. 随着端到端时延要求的增大, 采用 FRMCMP 算法的平均时延受满足时延约束的概率要求和链路时延模糊变化影响的程度也逐渐减弱, 但与及时分组递交率相比, 变化幅度较小. 及时分组递交率和平均时延受端到端时延要求 满足时延约束的概率要求和链路时延变化三个因素的影响. 当端到端时延要求增大, 满足时延约束的概率要求降低, 则时延约束放松, 会有更多的分组被转发 ; 链路时延变化范围小, 意味着链路质量稳定, 于是及时分组递交率增大. 但更多分组会导致较多的冲突和排队等待, 分组的平均时延也会增加. 图 1 时延要求对及时分组递交率的影响 图 2 时延要求对平均时延的影响图 3 和图 4 分别给出了采用 FRMCMP 算法的 WSN 在 case1 情形下, 当 α 在 0 到 1 之间变化时, 在不同端到端时延要求下的及时分组递交率和平均时延的变化情况. 从图 3 可看出, 当 α 水平从 0 逐渐增大到 1 时, 采用 FRMCMP 算法的 WSN 在不同时延要求下的及时分组递交率逐渐增大. 当端到端时延要求为 470ms 时, 采用 FRMCMP 算法的及时分组递交率随着 α 的增大明显提高 ; 当端到端时延要求为 510ms 时, 采用 FRMCMP 算法的及时分组递交率则仅有细微变化. 从图 4 可看出, 当 α 水平从 0 逐渐

11 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 增大到 1 时, 采用 FRMCMP 算法的 WSN 在不同满足时延约束的概率要求和链路时延模糊变化影响时延要求下的平均时延逐渐增大. 当端到端时延要的程度, 但端到端时延要求为 470ms 是比较强的约求从 470ms 增大到 510ms 时, 采用 FRMCMP 算法束, 此时发送的数据分组有限, 而且满足时延约束的的平均时延在小区间内变化, 并随着 α 的增大而进概率要求和链路时延变化范围较小, 因此, 此时的及一步减小. 随着 α 的增大, 满足时延约束的概率要求时分组递交率受满足时延约束的概率要求和链路时降低, 链路时延变化范围缩小, 于是及时分组递交率延模糊变化的影响不大. 从图 6 可看出, 当 α 水平从就会提高, 但更多分组冲突和排队会增加平均时延. 0 逐渐增大到 1 时, 采用 FRMCMP 算法的 WSN 在随着端到端时延要求的增大, 时延约束放松, 则降低端到端时延要求为 490ms 和 510ms 下的平均时延了及时分组递交率和平均时延受满足时延约束的概逐渐增大. 但是, 当端到端时延要求为 470ms 时, 采率要求和链路时延模糊变化影响的程度. 用 FRMCMP 算法的平均时延在 α 为 0 和 0.2 时出现了异常波动. 实际上, 当 α 为 0 和 0.2 时, 由于端到端时延要求为 470ms 和 α 的取值导致时延约束的增强, 因此, 随机选择的个别源节点会无法发送分组或仅发送极少数分组到 Sink 节点, 前者导致统计结果上平均时延的减小, 后者由于 Sink 节点收到的极少数分组具有较大时延, 从而造成统计结果上平均时延的增大. 这也说明在满足不同 QoS 需求的应用时, 端到端时延要求和模糊数置信水平的调整需要综合考虑. 图 3 置信水平对及时分组递交率的影响 (FRMCMP:case1) 987 图 4 置信水平对平均时延的影响 (FRMCMP:case1) 图 5 和图 6 分别给出了采用 FRMCMP 算法的 WSN 在 case2 情形下, 当 α 在 0 到 1 之间变化时, 在不同端到端时延要求下的及时分组递交率和平均时延的变化情况. 从图 5 可看出, 当 α 水平从 0 逐渐增大到 1 时, 采用 FRMCMP 算法的 WSN 在不同时延要求下的及时分组递交率逐渐增大, 但低于 case1 情形的值. 当端到端时延要求为 510ms 和 470ms 时, 采用 FRMCMP 算法的及时分组递交率随着 α 的增大仅有略微提高 ; 当端到端时延要求为 490ms 时, 采用 FRMCMP 算法的及时分组递交率则明显提高. 虽然端到端时延要求的增大会降低及时分组递交率受 图 5 置信水平对及时分组递交率的影响 (FRMCMP:case2) 图 6 置信水平对平均时延的影响 (FRMCMP:case2) 表 2 给出了 FRMCMP 算法和 MCMP 算法的单个分组传输代价. 从表 2 可看出, 二者的单个分组平均传输数没有明显的变化, 因此传输一个分组的

12 097 计算机学报 201 年 能量消耗可认为在相同的水平. 表 2 算法的单个分组传输代价比较算法情形单个分组平均传输数 FRMCMP case1,α= case2,α= MCMP 结论本文在考虑 WSN 链路时延和可靠性的不确定性时, 区分链路 QoS 的模糊性 随机性和时变性, 引入模糊随机变量, 在 MCMP 模型的基础上给出具有双重不确定性的 FRMCMP 模型, 并设计了相应的路由算法. 考虑到 WSN 节点的能量和计算能力有限, 完成了模糊随机约束的线性化. 仿真实验结果验证了 FRMCMP 算法的有效性和实用性, 随着 QoS 约束的模糊感知, 其及时分组递交率和平均时延两个性能指标比 MCMP 算法具有更好的区间变化, 通过 α 置信水平的变化可在不同程度上调节及时分组递交率和平均时延, 从而更好地满足不同 WSN 应用场景的需要. 本文的工作初步验证了区分 WSN 链路 QoS 不确定性中模糊性与随机性的思路和方法的有效性与合理性. 在后续工作中, 我们将针对 WSN 链路间干扰同样存在模糊和随机双重不确定性的事实, 探索新的模型和方法, 分析区分模糊性和随机性的 WSN 链路间的相互干扰对多种性能指标带来的影响, 从而更好地满足不同的 WSN 应用. 致谢感谢本文审稿专家和编辑所提出的宝贵意见和建议! 参考文献 [1]WangGuang Yuan,ZhangYue.Thetheoryoffuzysto chasticproceses.fuzysetsandsystems,192,51(2): [2]Ben OthmanJ,yahyaB.EnergyeficientandQoSbased routingprotocolforwirelessensornetworks.journalof ParalelandDistributedComputing,2010,70(8): 犠犃犖犌犡犻犪狅 犕犻狀犵,bornin1964, Ph.D.,profesor,Ph.D.supervisor. Hisresearchinterestsincludewireles sensornetworksandsecuretechnology ofpervasivecomputing. [3]WenHao,LinChuang,RenFeng Yuan,ZhouJia,Zeng Rong Fei.QoSarchitectureinwirelessensornetwork. ChineseJournalofComputers,209,32(3):432 40(in Chinese) ( 文浩, 林闯, 任丰原, 周嘉, 曾荣飞. 无线传感器网络的 QoS 体系结构. 计算机学报,209,32(3):432 40) [4]LinChuang,LiYin,WanJian Xiong.Optimizationaproa chesforqosincomputernetworks:asurvey.chinesejour nalofcomputers,201,34(1):1 14(inChinese) ( 林闯, 李寅, 万剑雄. 计算机网络服务质量优化方法研究综述. 计算机学报,201,34(1):1 14) [5]ZengZhi Wen,ChenZhi Gang,LiuAn Feng.Energy Hole avoidanceforwsnbasedonadjustransmisionpower.chi nesejournalofcomputers,2010,3(1):12 2(inChinese) ( 曾志文, 陈志刚, 刘安丰. 无线传感器网络中基于可调发射功率的能量空洞避免. 计算机学报,2010,3(1):12 2) [6]KuipersF,VanMieghemP,KorkmazT,KrunzM.An overviewofconstraint basedpathselectionalgorithmsfor QoSrouting.IECommunicationsMagazine,202,40 (12):50 5 [7]HuangXiao Xia,FangYu Guang.MulticonstrainedQoS multipathroutinginwirelesensornetworks.wirelesnet works,208,14(4): [8]BuckleyJ,EslamiE.UncertainprobabilitiesI:thecontin uouscase.softcomputing,204,8(3): [9]NandaS,PandaG,DashJK.Anewsolutionmethodfor fuzychanceconstrainedprogrammingproblem.fuzyopti mizationanddecisionmaking,206,5(4): [10]MinhasMR,GopalakrishnanS,LeungVCM.Anonline multipathroutingalgorithmformaximizinglifetimeinwire lessensornetworks/procedingsofthe6thinternational ConferenceonInformationTechnology:NewGenerations (ITNG209).LasVegas,NV,USA,209: [1]WangXiao Ming,AnXiao Ming.Anenergyandlocation awareacobasedroutingalgorithmforwirelessensornet works.actaelectronicasinica,2010,38(8): (in Chinese) ( 王小明, 安小明. 具有能量和位置意识基于 ACO 的 WSN 路由算法. 电子学报,2010,38(8): ) [12]WangXiao Ming,JiangXiao Hong,YangTao,LiQiao Liang,LiYing Shu.Nodeagregationdegre awarerandom routingfornon uniformwirelessensornetworks.ieice TransactionsonCommunications,201,E94 B(1): [13]AbhinavBansal.Somenonlineararithmeticoperationson triangularfuzynumbers( 犿,α,β).AdvancesinFuzy Mathematics,2010,5(2): 犔犝犑狌狀 犔犻狀犵,bornin1972,Ph.D.candidate,lecturer. Hisresearchinterestsfocusonwirelesensornetworks. 犔犐犢犻狀犵 犛犺狌,bornin1978,Ph.D.,asociateprofes sor.heresearchinterestsincludewirelessensornetworks andcyber physicalsystems. 犎犃犗犓犲 犌犪狀犵,bornin1936,profesor,Ph.D.supervisor. Hisresearchinterestsincludecomputersoftwareandtheory.

13 5 期王小明等 : 模糊随机环境下的无线传感器网络多约束多路径路由 197 犅犪犮犽犵狉狅狌狀犱 Wirelesensornetworks(WSNs)havebenwidelyap lationresultsshowthat,comparedwiththemcmpalgo pliedinmanyfieldssuchasregionmonitoringandtarget rithm,theproposedalgorithmcanpreciselyreflectsthechar tracking.diferentaplicationsmayrequirediferentquality acteristicsofroutingforwsns,thatis,maketheon time ofservice(qos)ofdatatransmisionintermsofdelayand packetdeliveryratioandaveragedelayadjustedflexiblywith reliability.asthewsnsdeployedinuncertainenvironments fuzyawarenesoflinkdelayandreliability.therefore,it havelimitedresources,themulticonstrainedmultipathrou canmethenedsofdiferentaplicationsforqosbyadjus tingalgorithmfacesmorechalenges.thexistingalgorithms tingconfidencelevelofuzynumbertochangethestrength regarduncertaintyofroutingconstraintsasrandomnesor ofqosconstraints. fuzines,whichadoptsprobabilitytheoryorfuzymathe TheworkissuportedbytheNationalNaturalScience matics,respectively.however,themethodscannotdescribe FoundationofChina(Nos ,607324, ) bothrandomnesandfuzinesimultaneously. andtheprojectsponsoredbythescientificresearchfounda Thispaperfocusesontheabove mentionedtopicand tionforthereturnedoverseaschinesescholars,stateedu proposesafuzyrandommulticonstrainedmultipathrouting cationministry.theprojectsaimtodiscusthenovelscheme model.consideringrandomnes,fuzinesandtime varying ofdatatransmisionforwirelesmultimediasensornetworks propertyofdelayandreliabilityofwireleslinks,themodel intheuncertainenvironment.theteamhasbenworkingon achievestheunifiedmodelingoffuzyuncertainty,random theresearchofroutingforwsnsandhaspublishedsomepa uncertaintyandtime varyingpropertyofdelayandreliability persinrespectableinternationaljournalsandconferences. indatatransmisioninwsns.themcmpmodelandalgo Thispaperproposesanovelideaandmethodconsidering rithm,whicharethefamousmulticonstrainedmultipathrou fuzines,randomnesandtime varyingpropertysimultane tingmodelandalgorithm,areextendedbyintroducingfuzy ouslyandverifiestheexpectedresultsbysimulation. stochasticprocesandfuzystochasticprogramming.simu