（计算机软件与理论专业论文）无线网络中路由机制的设计.pdf

摘要 定义了影响无线网络q o s 的维度，描述了考虑q o s 进行路由决策的问题，介 绍了相应的背景知识，依据单跳多跳，单通道多通道和单路径多路径对尤线 网络进行了分类，阐述了每一类网络中不同应用下的考虑q o s 的路由机制列艟的 问题，给出了针对部分问题的解决思路并提出了一些丌放问题，以传感器川络为 例给出了网络路由机制的层次结构以及各个层次的关键算法和对应实现并分析 了路由机制的性能。 考虑传感器网络协议的节能性，本文研究了节点参与度模型。首先，我们细 分了无线传感器网络中的协议层次，将负责路由机制的网络层分为邻域发现，动 态参与度模型和路由协议。然后，具体化了邻域发现协议，引入随机参数重构了 参与度模型，给出了相应网络启动方式并使用数学分析、模拟程序验证了此模型。 为了把响应时间引入传感器网络中的路由机制，分析了响应时间模型，基于 二层架构的传感器网络制定了两种可行方案。新路由机制以现有节能路由算法为 基础，根据时间约束修j 下路由路径和增添带有响应时问约束的路出表。分析结果 表明，两种方案在计算复杂度和通讯功耗上存在一个平衡，两种方案在实际传感 器网络应用下是有效的。仿真试验表明在路由机制中引入响应时i 刊是必须的。 为了验证网络路由机制，由于p e t r i 网是形式化描述语言和模型验证的一种 重要工具且支持并行，本文使用p e t r i 网为传感器网络的信息传输过程建立模犁 并依据p e t r i 网的性质进行了验证。 关键字：无线网络，q o s ，路由机制，协议实现 a b s t r a c t t h i sp a p e rh a sd e f i n e dt h em a t r i xo ft h eq o so fw i r e l e s sn e t w o r k s d e s c r i b e dt i l e r o u t i n gd e c i s i o np r o b l e mc o n s i d e r i n gq o s ，s e p a r a t e d t h en e t w o r k sa c c o r d i n gt o s i n g l e m u l t ih o p s ，c h a n n e l sa n dp a t h s ，s e tf o r t ht h ec o r r e s p o n d i n gp r o b l e m so ft h e r o u t i n gm e c h a n i s mc o n s i d e r i n gq o su n d e rd i f f e r e n ta p p l i c a t i o nb a c k g r o u n df o re a c h k i n do fn e t w o r k ，o f f e r e dp r a c t i c a ls o l u t i o n sf o rp a r to fp r o b l e m sa n db r o u g h tf o r w a r d s o m eo p e np r o b l e m s ，p r o v i d e dt h en e t w o r ka r c h i t e c t u r ea n dr e l a t e dc r i t i c a la l g o r i t h m a n di m p l e m e n t a t i o no fe a c hl a y e rf o rt h er o u t i n gp r o b l e mi nw i r e l e s ss e n s o rn e t w o r k w h i c hi sas p e c i a lk i n do fw i r e l e s sn e t w o r ka n da n a l y z e di t sp e r f o r m a n c e t ob r i n go u tap r a c t i c a le n e r g y e f f i c i e n tp r o t o c o lo fw i r e l e s ss e n s o rn e t w o r k ( w s n ) ，t h i sp a p e rs t u d i e st h es e n s o rn o d e ( s n ) j o i n i n gm o d e l f i r s t ，w er e f i n ew s n l a y e r sa n dd i v i d et h en e t w o r kl a y e r , w h i c hi sr e s p o n s i b l ef o rr o u t i n gm e c h a n i s m i n t o n e i g h b o rd i s c o v e r i n g ( n d ) l a y e r , d y n a m i cj o i n i n gm o d e l ( d j m ) a n dr o u t i n gl a y e r m o r e o v e r , w ed i s c u s st h en dm e c h a n i s mi nd e t a i l ，r e c o n s t r u c tt h ed j m w i t hr a n d o m p a r a m e t e r s ，p r o v i d et h ec o r r e s p o n d i n gn e t w o r kb o o t i n gs t y l ea n dv e r i f yt h ew h o l e m o d e l a b o v eu s i n gm a t h e m a t i ca n a l y s e s ，s i m u l a t i o n sa n dar e a l i s t i ct e s tb e d t oi m p o r tt h er e s p o n s et i m ef a c t o ri n t ot h er o u t i n gm e c h a n i s mo fw i r e l e s ss e n s o r n e t w o r k s ，w eh a v ea n a l y z e dt h er e s p o n s et i m em o d e la n dp r o v i d e dt w of e a s i b l e s o l u t i o n sb a s e do nt w o t i e r e da r c h i t e c t u r e b a s e do nt h ee n e r g ye f f i c i e n tr o u t i n g a l g o r i t h m ，t h en e wr o u t i n gm e c h a n i s m sm o d i f yr o u t i n gp a t h sa n dd e c o r a t et h er o u t i n g t a b l e sa c c o r d i n gt or e s p o n s et i m er e s t r i c t i o n a st h ea n a l y z i n gr e s u l tc a ns h o w , b o t h t h es o l u t i o n s ，b e t w e e nw h i c ht h e r ei sab a l a n c eo fc o m p u t i n gc o m p l e x i t ya n d c o m m u n i c a t i n gp o w e rc o n s u m i n g ，a r ee f f i c i e n t t h ee m u l a t i n ge x p e r i m e n tv e r i f i e s t h en e c e s s i t yo fi m p o r t i n gt h er e s p o n s et i m e 1 1 1o r d e rt ov e r i f yt h en e t w o r kr o u t i n gm e c h a n i s m ，w eh a v ei m p o r t e dp e t r in e t a n ds e tu pat r a n s m i s s i o nm o d e lf o rw i r e l e s ss e n s o rn e t w o r k sa n dv e r i f i e dn e t w o r k m e c h a n i s ma c c o r d i n gt ot h ec h a r a c t e r so fp e t r in e t ，f o rp e t r in e ti sa ni m p o r t a n tt o o l f o rf o r m a ld e s c r i p t i o nl a n g u a g ea n dm o d e lv e r i f i c a t i o na n ds u p p o r tp a r a l l e l i z a t i o n k e y w o r d s ：w i r e l e s sn e t w o r k ，q o s ，r o u t i n gm e c h a n i s m ，p r o t o c o li m p l e m e n t a t i o n 图目录与表目录 幽iw s n 参考模掣 图2d j m 模型状态转换机3 l 幽3 与a s c e n t 协议耗能和负载平衡比较 3 6 幽4 一层架构的模型 3 7 幽5 模拟网络拓扑幽4 l 幽6 模拟数据幽 4 二 幽71 ，能路由算法羽i 考虑响应时间约采的1 ，能路由比较一4 7 幽8 信息收集流稚幽4 9 幽9 s p l i t - j o i n 消息传递方式4 9 幽l o 顺序路由与并行路由4 9 幽1 1 直接传送方式的组 j | 数据采集模刑5 1 图1 2 考虑路由的组内数据采集模刑5 2 幽1 31 f 并行路由的组问层数据传输模州5 2 幽1 4 考虑升行路由的组间数据采集模型雨i 辖体传感器网络数据采集模刑5 3 表1q o s 相关网络性能 7 表2n s 2 ，g l o m o s i m 乖o p e n n e t 物理层实现的比较 ! i 表3 扮点模型表! ! 表4 直接传送协议 3 s 表5 函数及意义3 9 表6 算法运行数据表4 表7 组内甘能路由算法4 4 第一章引言 随着计算机对人们生活影响的逐步深入，新的名洲和概念不断被抛。州五 计算即考虑人们可以随时随地进行计算现在已经成为研究热点【1j ，而i t 一人微 软也提出了类似的无缝计算的概念。在此发展过程中一个核心话题就足无线通叭 即无线网络中的通讯。 无线网络中的研究需要从定义出发：多个1 ，点无线通讯组成的结构。为增加 自身的易用性，网络具有自主性即在无人二t 二侦的情况f ，嘲络形成拓扑并一：限拓 扑上基于合理的网络协议运行。其中的研究j 以包括【2 】：拓扑自上，上成( 训始 网络拓扑的形成) ，拓扑的自主发现( 新放置节点发现当前网络拓扑) ，拓扑的自 主管理和维护( 出现新节点或者原有节点退出) ：m a c 层网络协议( 对应参数有 发送功率、发送频率、信道变化、发送机制，刈应现象有干扰、丢包，对j 衄小务 有信道容量、丢包率) ；考虑q o s 的动态源路山算法，数据调度算法( 流髓控制 算法、资源预留策略) ；安全性问题( 攻。i 千t - 段：信号1 j 扰、停，_ 伪装、m j 川j 获) 。 本文主要讨论路由算法和数掘调度算法。首先，我们做出以下假定： 网络的元素为节点( 可能为异构) 或者基站( 基站可以不存在) 构 成，其中基站在网络运行时是静态的( 町以移动，但移动状念下肇站巧il i f l ) ： 网络的拓扑可以自主生成，自主管理： 网络传输质量不对称： 网络传输方式为广播； 网络底层使用c d m ao v e rt d m a 协议【3 】【4 ： 然后，定义q o s 的维度为丢包率、吞吐量、资源占有量和网络q ! 命期。此 处，丢包率为在响应时j 、白j 内成功发送的数掘量与发送的总数掘量的比值：奋ij ：诖 为成功发送的原始数据量：资源占有量为实际i j ，用的网络资源数景：i 侧络牛命 为网络从丌始运行到最终网络死亡的时i 枷。 。些q o s 相关的概念解释及其影 因素如表1 所示。 表1q o s 相关网络性能 吞吐量 有效的吞吐嚣 丢包率、传送速率、蜒迟、带窀 资源利网络吞吐鼙与实际削络中继路由、传送速率、坝外外 = f l j 州率流餐的比率 网络生 考虑能嚣有限情况rn q 发送功率、地f ，i = 耗能，1 7 忭能、 命州网络远行时间衔! 外玎销( 引锋币通i “) 异常处理( 1 ，点火! 1 1 5 、二乜率、近拔h , jf n 川j 慨砭i i , 训、 健壮性 连接不稳定)恢复j f 亓的网络性能 1 ，点身份的伪造难度，1 y 点被捕 安全性信息的机密性 获引起的连锁反应 基于上述假设和定义，本文研究的问题本质j ：是联合优化问题，不同的无线 网络下主目标不同( w l a n 的主目标为吞吐晕，无线传感器网络的毛1 1 标为川 络生命期，2 g 网络的主目标是丢包率) ，涉及到的网络性质包括消，0 、f 0 送述 ：、 延迟( 信道约束、节点约束) 等。问题的确切描述如下： 已知网络的物理拓扑如节点数目，节点问距离，网络的信道复用机制平f m 点 的连通性( 衡量标准为信噪比或者误码率) 与节点性质如能量，带宽，发射功率 级别，通讯编码方式，处理能力和移动模型，需要构造一种逻辑拓扑以优化m 络 服务质量并提供逻辑拓扑的自主性( 拓扑，f i 成，1 变化，消亡无人参j _ j ) 。 本文的主要贡献有如下几点： 定义了影响无线网络q o s 的维度并解释了相关的网络概念： 介绍了研究考虑q o s 的路由机制所需要的背景知识； 提出了合理的假设，清晰地描述了路由机制决策的问题： 依据单跳多跳，单通道多通道和单路径多路径对无线网手符进i j 了分类； 阐述了每类网络下针对不同应用的路由机制对应的问题： 提供了针对部分问题的解决思路并提出了一些开放问题； 细分了无线传感器网络中的协议层次，将负责路由机制的网络层 分为邻域发现，动念参与度模型和路山协议； 具体化了邻域发现协议，引入随机参数重构了参与度模，儿给 了相应的网络启动方式并使用数学分析、模拟程序验证了此模掣： 分析了响应时间模型，将响应时间引入传感器网络中的蹄机 制，基于二层架构的传感器网络制定了掰种可行路山策略； 使用p e t r i 网验证了简单的传感器网络的信息传输过程。 第二章背景知识 本节介绍无线通讯一些背景知识币f i ：| f 究f j 到的相关理论k l i 以如随机过f 1 1 1 ， 有线网络协议，排队论等。之所以介绍这u b 背最知以，足为： 1 ) 网络拓扑表现出的统计特性值得我们关注； 2 ) 无线网络的路由机制所采用的想法很多借鉴与有线网络路l j i 机制： 3 ) 针对网络流量模型的建立和网络吞吐量性能的评估，排队论是种 强有力的工具： 4 ) 研究网络性能优化的一个重要办法足将问题抽象为规划题，然l i 使用规划问题去解决； 5 1 网络中经常会遇到一些复杂度比较高的问题，很难给出般解法。 为了说明其困难性，复杂度理论是一种有效的工具； 6 ) 网络协议的性质需要严密的逻辑推理来证明，形式化模型作为。种 研究多年的知识可以提供一定的便宜性： 7 ) 无线网络的研究需要一些无线通讯知识和现有无线刚宝 7 景知叫做 铺挚： 8 1 网络中的问题经常使用图论的指示来求解，因为网络可以看成一个 天然的图，而其中的流量，邻居树可以天然的使用图论中的知识来处理： 9 ) 网络协议性能难以通过手工进行计算，仿真程序或者模拟程序心运 而生。 2 1 随机过程 网络拓扑表现出的统计特性值得我们关注。其中一个代表是很多l 删络表现出 的s m a l lw o r l d 现象和s c a l ef r e e 网络概念的提出。s c a l ef r e e 网络是满足幂律分枷 的网络。所谓的幂律分布，是指将网络以某种规则映射为一个图( 顶点为网络r 扣 的节点或者构成元素，边为两个节点或者构成元素的某种交互) 的情况r ，f ， 具有某种度的顶点数目和节点度满足幂律分柿。比如p d a 网络中，在范i 刊比较 广的情况下，可以假设p d a 网络物理拓扑是一个s c a l ef l e e 网络( p d a 节j 量i h j 在某个时间段内交互映射为边) 。 在无线网络中，协议中会使用一些随机策略，此时网络性能指标为统汁值特 性。在特殊无线网络如无线传感器网络中，节点的投撒会满足币态分前，。m 堆j 。 理论上的优化算法所得结果满足的统汁特性也是值得关注的。这利，做法健使他川 路由机制的提出并可以佐证路由机制的实川性。 2 2 有线网络路由协议 无线网络的路由机制所采用的想法很多借鉴与有线网络路出机制。路山i 、议 需可行、简单、健壮、平等、最优，但是理论上的研究往往倒置这个需求，以最 优为主。路由协议按运行方式可以分为静态( 脱线) 、动念( 在线) ，按实现策略 分比较重要的两种为：距离矢量协议( d v ) 、链路状态协议。现有的协议r e 较 重要的有r i p 协议，o s p f 协议和b g p 协议。其中前防种是子i 叫内的仂，议，r i p 协议应用的是距离矢量协议，其中存在无穷计算的问题：o s p f 协议使用链蹄：i 犬 念协议，该协议中每个节点只是传送它的邻居链路信息，是当前有线网络路协 议中的标准。 2 3 排队论 针对网络流量模型的建立和网络吞吐量性能的评估，排队论是一种强有力的 工具。用排队论数学理论来解决计算机网络的描述问题是传统的分析方法，其数 学基础是马尔可夫过程。通过排队论模型以及相关数学理论来刻画网络的性能各 个性能指标和各个指标之间的关系。 随机服务系统由以下3 个部分组成： 输入过程。即顾客到达的规律。比如有定长输入、泊松输八、 埃尔朗输入、独立输入等。 排队规则。如有损失制、等待制、混合制等。 服务机构。包括服务台设置、服务方式及服务时问等。 排队论符号标准：x y z a b c ，其中，x ：顾客相继到达问隔时| 、廿j 的分自j ， y ：服务时| 1 | j 的分布，z ：服务台个数，a ：系统容量限制n ，b ：顾客渊i 数| 1m ， c ：服务规则，一般主要考察前三项，记做x y z 。 常用分布符号为：m ：负指数分布d ：确定分布g ：般服务时间分n j f 。： k 阶e r l a n g 分布。常用模型为m m i 模型，m m n 模j 钭和m g 1 谈 2 4 线性规划 研究网络性能优化的一个重要方法是将问题抽象为规划问题，然后使川舭珈 问题去解决。常用的规划知识为线性规划，黎形规划和非线性规划。 首先介绍线性规划。比较重要的几个 | 念是l p 松弛( 将不等式变为等- c ) 人工变量( 最优情况下人工变量取值为0 ，刈应有大m 法和两阶段浊) ，- 纯弘 法，改进单纯型法。其中，改进单纯型法便f 编制程序。简要叙述计算过羁1 ： i 建立模型； 2 标准化模型： m a xc x ； a 1a x = 6 ： x2 0 ： b ) 其中，b 为非负向量，a 中行向量线性无关。 c ) 假设a 为m 行n 列的矩阵，挑选出m 列作为a 的綦阵b 。 3 一a 变为( b ，n ) 。对应的x 分为x h 与x 。，c 分为c b 和c 。； 4 判定最优解的存在性并计算换入变餐：单纯型算子为1 3 。，= b + c ( b 为b 的逆) 令所有非基变量取0 ，得出可行解。计算对应的检验数，c ，b 。+ n 。 若所有检验数小于0 ，则得到最优解：否则，计算最大正检验数( 方式可以任 意制定，若有多个最大，选取下标最小者) ，对应的变量为换入变量x k 。若 换入变量x k 对应的列向量b + p k 为非正，则无最优解： 5 确定换出变量：使用0 规则( 0 = m i n 器旧。锄知 = 踹蝴帔量觚，删舭 b + p k 中第i ( i t k ) 个变量除以第k 个变量： 6 将a 中第l 列换出b ，将a 第k 列换入b ，返回3 。 线性规划中一个重要的知识为列生成( c o l u m ng e n e r a t i o n ) 。其基小心恕利 用改进单纯形法获得主子问题，而子问题是规划问题转换为背包问题( 此题为 n p c 问题，有伪多项式算法，在c p l e xq 有实现) 。l r 松弛的解决思路类似， 列生成，最终也是转换为背包问题。其做法是将一类条件放入目标函数叶，。 然后介绍整形规划问题。其中，伞整形规划中所有变啭都必须为i f ：债骼城， 混合规划中部分为非负整数。其中一种解法足使用线性规划进行求解，然厉将所 得值驭整。更加精确的做法是使用分支界限法，小过复杂度比较高，令部使川f | 0 话为指数级别复杂度。还有一种有效做法为平面分割算法，利用整数的性质增加 约束条件( 比如真分数不能大于1 ) 。 一种比较特殊的规划为0 一l 规划，它住例络资源分配的问题巾卜分常川。这 种问题的求解可以使用集合覆盖方法，将变醴转换为+ 些0 ，l 列向鞋。然| ；他 用列生成算法逐步寻找可行列。 另外一种规划是非线性规划，目前的一种做法是将最优值的寻找问题转化为 非线性函数鞍点的寻找。若鞍点可以寻找到，则存在最优值：若不存存擎安正i ，上 ；： 优值不确定。针对现有的很多难解问题，该思想提供了可行的解法。 目6 u 规划上重要的丌放问题有：c o l u m ng e n e r a t i o n 收敛性的汪明，二怍线1 j = ! l ! 划的更加有效的求解方法，规划解法收敛速度的评估和证明。细节问题有初始t j 行解的选举，规划模型的构造( c o l u m ng e n e r a t i o n 不代表某个n p c 问题可以彩 项式求解，目前来讲，只是可以针对某些问题迭代求解背包问题进行有效求解) 。 下面是列生成计算过程： 1 初始基可行列为口，其余为n t h e n i = ( 工h ，z ) ，a = 【b ，| v 】，c = ( ( r c ) ： 2 判定n 中列的增益，如果并非所有的都为非负，那么添加那个具有最人负 增益( 增益最小) 的列到基可行列： 3 更新b 和n ，重复上述步骤直至最优( 全为非负) ； 4 n ，增益的计算方法为：_ ，= c ，一c 。b n ，； 5 对应的子问题为：m i n = c ，一f b b n ，v n ，n 。 2 5 复杂度理论 网络中经常会遇到一些复杂度比较高的问题，很难给出一般解法。为了醴i 】 其困难性，复杂度理论是一种有效的工具。为了比较清晰地解释问题的复杂r i ：， 首先介绍计算模型。目前最常用的计算模型为图灵机( t u r i n gm a c h i n e t m ) 及 其变形。其构成元素为输入带，指示头，状念装换函数，初始状态和终州犬念， 基于非确定性图灵机，定义n p 问题如卜：埘应的e = x i 存在y ：l y l a 。若z ( 一分i 划人j ：) ，c 为鳅任边精心。 则存在t 页点u 满足引理2 条件，因此g 存n ：奇旧，与o 为_ 分i 鹳f j 7 1 。义f j 色数a ，命题得证。 定理3 ：g 为单图，要么z ( g ) = a ，婪么z 。( g ) = + 1 。 利用反征法。依掘z 。( g ) 将t 学网分为i 埘炎：丽扦为第类h ，肝齐为讹 类图。顶着色：定义与边着色类似，记做z ( o ) = k ，且称g 为k 色图。荇gn 勺 任一真子图h ，z ( 日) z ( g ) ，则称g 为色| i f 1 界图，z ( g ) = t 时成为k 色临7 i t l l r 定理4 ：z ( g ) 蔓- i - 1 。 证明：任取顶点v ，着以+ 1 中颜包之。：取无色顶点u ，着以u 十邻n j 顶点上颜色相异的一种，因为度数最大为，所以+ 1 罩面至少有。种町仃颜 色。因为节点数目有线，整个过程是可以在有限时间内完成的。 支配集：若任何顶点u 要么输入d ，要么与d 中某个顶点相邻，则dj , s 支 配集。若d 的任何真子集皆非支配集，则称为极小小支配集。基最小的极小支m 集成为最小支配集，其基数r ( g ) 为( ；的支配数。 独立集：i 中任两顶点不邻，则称i 为独立集；若任意添加一点，i4 i i i 址 独立集，则称i 是极大独立集；基最大的独市集是最大独立集，记做( g ) 。 引理：v 是g 的顶点覆盖，v v 是( ；的独立集，v v 为g 的补图g 中的 团。独立集为极大独立集当且仅当它是支配集。k 为极小覆盖，当且仅当v k 为极大独立集。极大独立集必为极小分配集。 支配数、覆盖数币i 独立数：逻辑运算及性质( 交换率、结合率、分配率车吸收率j 。微 小分配集公式为( 其中n 为1 y 点邻居) 妒( v 。，v 。，v ) = 兀( v + ) ：极小覆羔臻公 式为：缈( v ，v 2 ，v ，) = 兀( 一+ n “) 。 # - i e f ”) 2 9 模拟程序 网络协议性能难以通过手工进行计算，仿真程序或者模拟1 7 序心延i n 川。 针对一个想法的评估有三种基本方式：直观推断，理论论证，实验方法。对j + h 多想法，由于是改进的细枝木节，做了很微小的改动，而这个改动不会带来特别 大的连带影响，这么改进之后的方案出于之河的方案是显然的，这时候适合川筇 一种方式。如果是核心算法的改进或者某u 弋荣誉模块的删除，比如i f i 保i i l f i ；粜1 、 变的情形下减少了计算复杂度或通讯复杂j 叟，那么这种东西在理沦分析卜”j 以 ! 出确定的结论，这种情况适合第二利，方式。血果提m 了利一伞新的厅案，听陔， 案和现有默认方案从两种不同的角度去解决旧+ 个问题，那么此时需要 个个，j 。 面的性能比较，这时候第三利，方式比较多。ij 二缺乏实验平台或抒实验、卜f 、1 、绀 合实验规模，第三种方式通常表现为模拟仿真程序。 现有无线网络中常用的三个模拟器足n s 2 ，( ；】o m o s i m 和o p e n n e t 。 二杯 都有一定的用户群，n s 2 是开源软件，( i o m o s i m 是学生范围内 源的软什， 0 p e n n e r 是商务软件。针对无线网络的现状术讲，三个软件中关j i 物理层的模拟 实现失真度都比较高，这直接影响了实验结粜的有效性。n s 2 初始是针埘仃线州 络进行模拟，g 1 0 m o s i m 是u c l a 丌发的针对无线网络的模拟器。就其内部实现， 效率而言+ ，三者各有千秋，物理层实现的比较如表2 ： 表2n s 2 ，g l o m o s i m 和o p e n n e t 物理层实现的比较 模拟器g l o m o s m n s 2 o p e n n e l 信噪比计算累计信号比较累计 基于信噪比误码 信号接收基于信噪比门限基于误码率f j 限 率门限 悟道最洛 瑞森瑞利 不包含不包含 f r e es p a c e ， f r e es p a c e ， 路径损耗 t w o r a yg r o u n d t w o r a yg r o u n d f r e es p a c e r e f l e c t i o n 等r e f l e c t i o n 现有的一些工作是编写物理层模拟模块以降低失真度。关于h 层朗、泌如 m a c 层的8 0 2 1 1 ，s e n s o r m a c 等协议都有相应的丌源实现。然而，盯r 1 卜胺f n 失真性导致了模拟结果说服力不足。 现在模拟程序实现最重要的两个问题是： 数学模型不够合理。信道干扰模型，传感器节点的感性模型，能髓损 l 模型都和实际相差比较大。关r 这种差异性的研究目前也是个热l i 模拟程序运行效率低，要求运行时问特别长。 因此，在添加仿真模块时应该特别注意这蚺点，每个模型都需要商f ! 典。 第三章各类无线网络的路由机制分析 3 1 问题描述 网络的基本元素之一是节点，为清晰拙述问题，表3 列出了节l i 的腻r i 。n 先，无线网络的节点可能是能量受限的。”j 然，如果按现住人们使川儿仃尤线川 卡的笔记本的方式，能量的问题变得0 i 足琊么承篮。然而，若足尤人位。- ) ：的化，出 器网络，能量问题就成为了限制其应用的核心问题。如果是针对监摔应_ h ，或柯 其它位置敏感的应用，位置信息是必须的。如果只针对单纯的数掘交硼逦川 p d a 网络，那么位置信息就是不必要的。尤线网络区别于有线网络的个- n 世 表现就在于邻居集，其邻居集的采集由于无线网络的不对称性和可能的移动。阽m 变得较有线网络复杂。 表3 节点模型表 属性 对应变量蜕1 9 j 能量 e 记录能量淌i e 周期性测量( 利 统 位置 p 计特性或者利用坩b 铺 节点) 由于无线传输的小 对称性，邻居为节点，j “ 邻居集 n c 接到达的节点集合m l i 是可以到达节点的1 ，点 集合 时问t本地时钟 网络中节点个数为n ，网络的用途i ! 】j 。能为数掘汇集或者节点m 通m 。j ) h 并m 例子比如无线传感器网络。该种网络下存存“一聚节点，而且为了控制简币制叫络 性能的考虑，经常人为地引入异构节点。后者的网络如p d ai 叫络，| x x j 络的| 1 的 是提供节点持有者之问交互的媒介。从表现形式来讲，后者网络经常是稀疏的， 移动的，对网络的抗干扰性要求较之数捌扩集网络要小一些。那么，本文埘f 究n 勺 问题是在已知网络目的的情况下提出q o s 更好的路山机制。对于不问的州络， 针对q o s 优化的主目标是不同的，在传感； ! i 删络中是节能性，在，j 三线j j 域i 是吞吐量等等。 问题的假定如引言中所述。为研究考虑q o s 的路协议，将m 络。质板蟛 三元组分类 。在每炎f t 分别讨论考虑q o s 的跚 ik ；ij l j 。 下一节介绍相关工作。 3 2 相关工作 关于考虑q o s 的路由，多路径路i 是经常被学者提m 的概念。【5 一资源m 留问题使用多路径路由。考虑节点的移动性，节点问的通讯情况不断变化，n ：假 设资源预留时问远大于连接时间的情况f ，多路径预留可以缩短平均预留连接i i , j 间。这是一种典型的丌销换性能的策略，适合用于突发大数据量请求的情况如传 感器网络。 6 】中考虑移动性使用多路径路由提高可靠性，使用短的路为主路， 其他路作备份。具体策略是主路传送有效数据，其他链路做轻量级传送。【6 川r 还讨论了并发传送的好处即多路同时传递既柏+ 叮靠性又有效书。【7 川，学啦f 止 两条路，一条最短，一条最稳定。稳定度的评估使用本地测量数据的统汁。1 8 i 中考虑q o s 的多路径路由的论文。该论文假设和本文基本相同，不过它的1 】5 陵 要强很多。假定考虑的q o s 就是带宽，m a c 层使用c d m a o v e r t d m a ，时l ij j ” 信息已知。由于不考虑延迟，数掘包不存在过期，一个自然的结果就是时f t 月j 片数 就是带宽数。其基本想法就是得到所有的路径，判断有没有一条可行的路；如粜 没有，选择一条多路( 其中体现了在带宽限制卜，单路径路由小是最优的) 。1 9 i 中提出具有较少通讯复杂度的动态源路由距离矢量协议。【1 0 中讨论了闩私搏汪、 有多坏。文中延迟是基于流量的，目标函数是最小延迟。当延迟与流量成线队天 系时，上界的延迟是最优延迟的4 3 ；当延迟与流量成非负、不减函数时，l ：外 为流量2 倍的情形。【1 1 】中考虑多路径路山的有用性最大化，提出了收敛的鳕 上 并提出了基于测量变量的算法，具有启发意义。其钊对有线网络1 ，似设多川、 多路径( 路径是对应用户的) 。每台电腑刈应多类应用，每台电脑对j 垣多跚似 定到达速率，增益、耗损应该都是与用户仃关的量，所提算法# 要时1 i l ；嵌艟止 新和主变量更新组成。 另外一种常用的假定方式为假设时mj 1 已经分配，路i h 如何定以及棚火的圳 节问题和分布式机制。c d m a o v e r t d m a 机制f 的码元分配舀! 3 1 1 4 】仃定的h 论，这是一个典型的资源分配问题。考虑健壮性的路山机制s p i r a l p a t hn ：f 5 l 中提出。浚论文提出了p k 的概念：通过额外、不交的链路连接k 一邻i ，i ： ! i i ； 路和所有支路总称p k 。 1 2 】定义了分支淞一l 、超级甘点( 即h - 7 i 集合) 、分戈，皤 级节点的概念。提出了b e a c o n 的概念，为二儿组l ( 集合使用一个向量数组描述) 。其中的路j i 策略为两跳广播。钊刈州n j 分配的n p c 问题【6 ，文中给出一个启发式算法。该算法分为：路m 发现阶段、 路由回应阶段( 若存在，应用最大最优先原则) ，先分支节点运行，然后分支超 级节点，迭代直至得到结果，以增大j f 销的代价提高了路由建立的成功率平| 证 的利用率。 3 3 问题分析 3 3 1 网络 此种网络下，节点交互仅发生在相邻节点| 1 j _ | 而h 节点只能接收路数w 当前p d a 网络，红外传送网络都输入这种嘲络。通常节点行为是相互通t i l q1 ) 点人为的移动到通讯距离内，之后在相对静止的情况下完成数据传输。 3 3 2 网络 此种网络下，一个节点可以并发的和多个节点通讯，之所以是并发m 4 i 是j i 行。因为多通道对应的复用机制是t d m a ，c d m a 而不是f d m a 。为f d m a 本身在技术上会存在较大的干扰性，而且频带本身是稀缺资源，每种网络 i 能，i 用某个有限的频段。陔种网络的概念是蜂窝网络，现有的g s m 网络使刷的足 t d m a ，而现有支持c d m a 的手机支持的是窄带c d m a 。此种情况下的数抛“ 集网络的机制较为简单，直接的想法是节点可以按需的获得资源，然后在其所。! i 有的资源内进行数据传送。对于节点交互l 叫络，【f 于网络不支持多跳，) l j 么h 络 的路由已知，此时的路由q o s 成为一个单纯的吞吐量问题。 在目前的应用中，除了b e l l m a n f o r d 这种每个节点都维持伞局逻辑拓扑信 息的分命式算法，其它算法都难以达到个j l ；j 最优。任小节以及厉续旧节m ，屯 考虑集中式的情形，之后考虑分布式的情彤。 1 ) 集中式考虑 假设存在某个或者某几个管理节点保持叫络拓扑信息，节点拓扑的决策m i 维 护在管理节点上进行，管理节点向普通节点发送控制信息柬控制逻辑拓扑j i ! 三成。 假定网络中的节点满足时钟同步以保试 c d m a 或者t d m a 的无左爿 延仃，j l lj c d m a 的网络需要解决的是码元分配问题，m 鉴ft d m a 的嘲络解决的址u f 片分配问题。t d m a 相对于c d m a 的好处相j1 二町以灵活时间片的个数，技术。丈 现上抗干扰性比较强，但是需要确定时问”的长短。在当前类别f ，此问题i j 以 描述如下：已知网络拓扑情况下给出码元数日最少的码元分配方案，类似1 i 无向 图的顶点着色问题。直接的做法是删除没有出边的节点及关联的边，然后进i r 劁 的深度优先遍历，每遍历到一个节点，染j ：和当前邻居不l 司的颜色，遍j j j 究。# j i 码元分配方案也就确定了。 2 ) 分布式考虑 分布式情况下问题的难度有所增加，我们无法依据全局信息占获得染巴，j 案。此时，唯一可以依据的是节点本身属性和节点邻居信息。分自i 式算法足多个 周期的迭代过程，对时钟同步有较高要求。一个直接的染色方案就足使用j ；j i f 机博 法去染色( 不考虑出度为零的节点，所使用的颜色数为最大的节点入度j j l i ) ， 运行足够多轮以避免冲突( 如果出现冲突，则有冲突的节点在可选颜色返| l i i 内逆 行一次随机) 。解决此问题的方法有两种：设