（计算机科学与技术专业论文）面向移动自组网环境的副本放置算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 数据复制技术被广泛应用于数据库系统、文件系统、操作系统和分布式系统中。在移 动自组网( m o b i l e a d h o e n e t w o r k ，m a n e t ) 环境中，无线通信带宽非常有限，网络容易出 现链路失效、节点失效和网络分割。数据复制技术成为提高移动自组网系统可靠性和系统 性能的重要手段。但由于移动自组网的特点( 移动自组性、移动通信设备的电能有限性等1 ， 给数据复制技术带来了新的问题和挑战，为此本文利用动态自适应的思想分别提出了四种 适应移动自组网环境的副本放置算法，以解决这些问题和挑战。 在移动自组网环境中节点的移动性使得网络拓扑结构不断发生变化，为此本文提出了 基于通信开销的动态自适应副本放置算法( d a r a m ) 。d a r a m 算法以数据访问的通信开销 作为目标函数，每个副本节点从其邻居节点收集读写请求的局部信息，决定是否扩展副本 到邻居节点或交换副本或放弃副本，动态地调整副本放置方案，以适应数据访问请求和网 络拓扑的变化，目的是减少数据访问的通信开销，提高系统的性能。模拟实验表明，在移 动自组网环境中d a r a m 算法有效地减少了数据访问的通信开销，提高了数据访问的效率。 在移动自组网环境中节点的移动具有不确定性，快速在副本节点通信范围内通过的节 点可能会引起副本放置方案的振荡，为此本文提出了基于移动预测的动态自适应副本放置 算法( d a r a m - m p ) 。d a r a m m p 算法使用移动预测的方法动态确定副本节点的稳定邻居 节点集，将副本扩展到相对稳定的邻居节点上，目的是减小由于移动节点间的边缘移动给 副本放置带来的不稳定性。模拟实验表明，在移动自组网环境中d a r a m m p 算法有效地 减少了副本放置方案的振荡，减少了放置副本的通信开销。 在移动自组网环境中节点的电能非常有限，为此本文提出了基于能量控制的动态自适 应副本放置算法( p d a r a m ) 。p d a r a m 算法利用无线电的空间传播特性，采用相应的能量 控制方法动态确定节点的中继邻居节点集，以数据访问的能量开销作为目标函数，副本节 点通过从邻居节点收集读写请求的局部信息，计算相应的测试条件，动态地调整副本放置 方案，以达到减少数据访问能匿开销的目的。模拟实验表明，在移动自组网环境中p d a r a m 算法有效地减少了数据访问的能量消耗。 最后考虑由于数据访问集中予副本节点，大量的数据发送会引起副本节点的能耗迅 速，从而导致副本节点的失效和网络分割可能性的增加，为此本文提出了基于最大网络生 存时间的动态自适应副本放置算法( m d a r a m ) 。m d a r a m 算法考虑网络节点能量消耗的 公平性，对不同节点( 依据节点的剩余能量) 产生的数据访问请求采取不同的加权值，来计 算相应的测试条件，将副本尽量放置在剩余能量较多的节点上，动态地调整副本放置方案， 目的是使网络生存时间最大。模拟实验表明，在移动自组网环境中m d a r a m 算法有效地 延长了网络的生存时间。 美键词：移动自组网，副本放置，通信开销，移动预测，能量控制，网络生存时间 + 本文得到高等学校全国优秀博士学位论文作者专项资金项目( 2 0 0 1 4 1 ) 、国家9 7 3 重大基础研究计划 堕垦! 垫! 垄堕! ! ! ! 旦：塑垦窒旦鉴型堂基垒塑星i ! ! ! 塑! 垫：! ! ! ! 垫! 尘童墅： i 国防科学技术大学研究生院学位论文 a b s t r a c t d a t ar e p l i c a t i o ni sa ni m p o r t a n tw a yt oi m p r o v et h es y s t e mp e r f o r m a n c ea n dr e l i a b i l i t y , w h i c hi sb r o a d l yu s e di nd a t a b a s es y s t e m ，f i l e ss y s t e m ，o p e r a t i o ns y s t e m ，a n dd i s t r i b u t e ds y s t e m i nm o b i l ea dh o en e t w o r k s ( m a n e t ) ，w i r e l e s sc o m m u n i c a t i o nb a n d w i d t hi sl i m i t 1 i n kf a i l u r e a n dn o d ef a i l u r eo f t e nh a p p e na n de v e nn e t w o r ki sp a r t i t i o n e d d a t ar e p l i c a t i o ni ns u c ha d y n a m i cr e s o u r c e l i m i t e de n v i r o n m e n ti sas i g n i f i c a n tc h a u e n g e i nt h i st h e s i s ，i no r d e rt o i m p r o v et h es y s t e mp e r f o r m a n c e ，f o u rr e p l i c aa l l o c a t i o na l g o r i t h m sf o rm a n e te n v i r o n m e n ta r e p r o p o s e d f i r s t l y , n o d e sm o v ef r e e l ya n dt h ed i s t r i b u t i o no fa c c e s sr c q u e s t sc h a n g e sd y n a m i c a l l yi n m a n e t s ，ad y n a m i ca d a p t i v er e p l i c aa l l o c a t i o na l g o r i t h mf d a r a m ) t h a tc a na d a p tt ot h e n o d e sm o t i o ni sp r o p o s e dt om i n i m i z et h ec o r n m u n i c a t i o nc o s to fo b j e c ta c c e s s w h e nc h a n g e s o c c u ri nt h ea c c e s sr e q u e s t so ft h eo b j e c to rt h en e t w o r kt o p o l o g y , e a c hr e p l i c an o d ec o l l e c t s a c c e s sr e q u e s t sf r o mi t sn e i g h b o r sa n dm a k e sd e c i s i o n s1 0 c a l l yt oe x p a n dr e p l i c at on e i g h b o r so r s w i t c ht h er e p l i c aw i t hn e i g h b o r so rt oc o n t r a c tt h er e p l i c a t h ea l g o r i t h md y n a m i c a l l yc h a n g e s t h er e p l i c aa l l o c a t i o ns c h e m et o w a r d sat o t a lo p t i m a o p e c s i m u l a 土i o nr c s u r ss h o wt h a td a r a m a l g o r i t h me m e i e n t l yr e d u c e st h ec o m m u n i c a t i o nc o s to f o b j c o ta c c e s si nm a n e t s s e c o n d l y , t h ed a r a ma l g o r i t h mb a s e do nt h em o b i l i t yp r e d i c t i o n ( d a r a m m p ) i s p r o p o s e dt or e d u c et h eo s c i l l a t i o no fr e p l i c aa l l o c a t i o nb yr e a s o no fn o d e sm o v eq u i c k l y t h e m o b i l i t yp r e d i c t i o nm e t h o db a s e do nl i n ke x p i r a t i o nt i m ei su t i l i z e dt oc h o o s es t a b l en e i g h b o r s a n dt oe x p a n dt h er e p l i c at or e l a l i v e l ys t a b l en o d e s ，o u rs i m u l a t i o n ss h o wt h a td a r a m m p a l g o r i t h me f f i c i e n t l yr e d u c e s t h e o s c i l l a t i o n o f r e p l i c a a l l o c a t i o n i n m a n e t s n i r d l v t h eb a t t e r yc a p a c i t yo fn o d e si sl i m i t e di nm a n e t s t h er e p l i c aa l l o c a t i o ns h o u l d c o n s i d e rt h ee n e r g yc o s tt h a ti n f l u e n c e st h es y s t e mp e r f o r m a n c ee v i d e n t l y ap o w e r a w a r e d y n a m i ca d a p t i v er e p l i c aa l l o c a t i o na l g o r i t h m ( p d a r a m ) t h a tu s e dap o w e rc o n t r o lm e t h o di s p r o p o s e dt om i n i m i z et h ee n e r g yc o s to f n e t w o r k e a c hr e p l i c an o d ec o l l e c t sa c c e s sr e q u e s t sw i t h e n e r g yi n f o r m a t i o nf r o mi t sn e i g h b o r sa n dm a k e sd e c i s i o n sl o c a l l yt oa l l o c a t er e p l i c at on o d e s s i m u l a t i o nr e s u l t ss h o wt h a tp d a r a m a l g o r i t h me m c i e n t l yr e d u c e st h ee n e r g yc o s to fn e t w o r k i nm a n f r s f i n a l l y , i no r d e rt ob a l a n c et h ec o n s u m e de n e r g yo fn o d e s ，ad y n a m i ca d a p t i v er e p l i c a a l l o c a t i o na l g o r i t h mb a s e do nt h em a x i m u mn e t w o r kl i f c t i m e ( m d a r a m ) i sp r o p o s e d e a c h r e p l i c an o d eu t i l i z e saw e i g h t e dm e t h o db a s e do nr e m n a n te n e r g yt oc o m p u t ec o n d i t i o na n d m a k e sd e c i s i o n sl o c a l l yt oa l l o c a t er e p l i c at on o d e s 也a th a v em o r er e m n a n te n e r g y , t h er e s u l t s o fs i m u l a t i o ns h o wt h a tm d a r a ma l g o r i t h m se 伍c i e n t l yp r o l o n gt h el i f e t i m eo fn e t w o r ki n m a n e t s k e y w o r d s ：m o b i l ea dh o en e t w o r k ，r e p l i c aa l l o c a t i o n ，c o m m u n i c a t i o nc o s t ， m o b i l i t yp r e d i c t i o n ，p o w e rc o n t r o l ，n e t w o r kl i f e t i m e i i 国防科学技术大学研究生院学位论文 国防科学技术大学研究生院学位论文 国防科学技术大学研究生院学位论文 表目录 袁2 1 模拟实验网络环境参数3 0 表2 2 移动自组网环境中移动预测对算法的影响3 4 表3 1 通信系统能量消耗数据对照表3 7 表3 , 2 模拟实验网络环境参数4 7 v 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 亘自整盘蜜塑圆强缝鲤割查熬置簋洼亟窥 学位论文作者签名：蝗垫日期：, z o o g - 年1 , 8 月七6 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可讼保留并囱国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：重囱整型宣塑圆丕拖鲮墅垄兹量篡洼丑盔 学位论文作者签名：塑! 墨 日期：2 争年t , 8 月2 6 日 4 作者指导教师签名：圭! 壁：兰日期：之o o 乎年胞月2 6 日 国防科学技术大学研究生院学位论文 第一章绪论 随着蜂窝通信、无线局域网和卫星数据服务豹发展，移动计算的出现使人们随时随地 获取信息的理想成为可能。而随着移动计算技术的进一步发展，以及如战场、救灾等特殊 环境对移动计算的需求，迫切需要能够快速搭建并可自由移动的局域通信网络，于是“移动 自组网”这一新型的网络构架便由此应运而生。随后与之相应的高速无线通信技术、路由技 术、传输服务技术、数据管理技术便成为新兴的热点研究领域。数据复制技术作为数据管 理技术中一种提高系统可靠性积系统性能的重要手段，在移动自组网环境中的应用尤其重 要，而移动自组网的诸多特性，如动态变化的网络拓扑结构以及移动通信设备的电能有限 性等，都给数据复制技术带来了新的问题和挑战。对这些问题的研究既具有挑战性，又具 有重要的研究价值和应用前景。 1 1 1 移动自组网概论 1 1 移动自组网技术 传统移动无线通信网络( w i r e l e s sc o m m u n i c a t i o nn e t w o r k ) 通常是以蜂窝移动通信网络 或无线局域网方式出现的，它们都需要类似于基站a s es t a t i o n ) 或移动支持节点( m o b i l e s u p p o r ts t a t i o n ) 这样的网络支持设备i l 】，其示意图如图1 - l 所示。而自组网( a dh o cn e t w o r k l 是一种在没有骨干网络的条件下，由系统中的通信节点通过分布式互连协议组织起来的多 跳的网络系统，相应的移动自组网( m o b i l e a d h o c n e t w o r k ，m a n e t ) 贝j j 是支持通信节点移 动的自组网络闭，其示意图如图1 2 所示。 图1 1 传统移动无线通信网络示意图图1 2 移动自组网示意图 移动自组网技术的研究起初是为了满足军事领域应用的需求，它的研究起源于2 0 世 纪7 0 年代美国国防部d a r p a 资助的在战场环境下采用分组无线网进行数据通信的 p r n e t ( p a c k e t r a d i o n e t w o r k ) 项目。其后d a r p a 又于1 9 8 3 年和1 9 9 4 年分别进行了抗毁可 第1 页 国防科学技术大学研究生院学位论文 适应网络s u r a n ( s u r v i v a b l ea d a p t i v en e t w o r k ) 项目和全球移动信息系统g l o m o ( g l o b a l i n f o r m a t i o ns y s t e m s ) 项目的研究，旨在对能够满足军事应用需要的、可快速展开的、高抗 毁性的移动信息系统进行全面而深入的研究。最终i e e e 8 0 2 1 1 标准委员会采纳了“a dh o c n e t w o r k 一词来描述这种特殊的自组织对等式多跳移动通信网络，“移动自组网”就此诞生。 “a dh o c ”的词源为拉丁语汇，其意思是“f o rt h i s ”引申为“f o rt h i sp u r p o s eo n l y ”，说明移 动自组网是一种有特殊用途的网络，它是由一组带有无线收发装置的移动节点组成的一个 多跳的临时性自治系统闭。也就是说移动自组网是：网络节点都是可移动的，并允许节 点自由的加入和退出；无需任何网络基础设施和管理支持就可以动态地创建网络；移 动节点间的通信通常是由多个跳步组成，每个节点兼具路由器和主机两种功能；网络节 点的移动会导致路由的动态改变的网络系统。 作为一种网络构架，与移动自组网技术相关的研究涉及到了网络的每一层，图1 3 为 移动自组网的网络参考模型( n e t w o r kr e f e r e n c em o d e l ) 圜。 a p p l i c a t i o n t r a n s p o r t 。 n e t w o r k d a t ai i n k p h y s i c a l 弓 z m 譬 3 o 覆一 r a d i o 1 1 2 移动自组网的特点 ! ! 唑竺一：i 吾 ；t r a n s p o r t：蚕 菩一 r a d i o 图1 3 移动自组网的网络参考模型 a p p l i c a t i o n t r a n s p o r t n e t w o r k d a t al i n k p h v s i c a l c o d 町 z j 凸 一 它 o z j 与固定网络及传统移动通信网络相比，移动自组网主要具有以下特点【2 1 1 3 1 【4 1 ： q 移动自组性：在移动自组网中各移动节点通过分布互连协议自组成网，不必设置通 信控制中心，也不依赖于固定的网络通信设备。每个网络节点兼具路由器和主机两种功能： 作为主机，节点需要运行面向用户的应用程序，而作为路由器，节点需要运行相应的路由 协议，并根据路由策略和路由表完成数据分组的转发和相应的路由维护。此外移动自组网 允许节点自由的加入和退出，使得即使在单个或部分节点故障的情况下，其余节点重组后 仍可通信，因而网络具有很强的鲁棒性和抗毁性。 d 动态变化的网络拓扑结构：由于移动自组网允许节点的自由加入和退出，包括链接 的增加和减少、节点的增加和减少( 包括由于地形等环境因素的影响造成节点暂时被隐藏) 、 节点群的分离与合并等，这既是移动自组网的显著优点，但同时也导致了网络拓扑结构的 不断变化给网络的诸多问题增加了难度。此外网络拓扑结构的变化还受节点的移动模式 国防科学技术大学研究生院学位论文 的影响，而在移动自组网的不同应用环境中节点的移动模式可能有较大的不同。这些都导 致了移动自组网的网络拓扑结构的频繁变化和不规律性。 珏动态变化的无线链路特性：由于移动自组网采用无线传输技术作为底层通信手段， 而无线信道所能提供的网络带宽相对有线信道要低得多。同时由于无线信号更易受到干扰， 导致无线链路的传输可靠性比有线链路差，数据包丢失率高。此外在移动自组网中采用的 广播方式可能在网络中引起较大的访问冲突和拥塞。这些均使得移动网络用户只能获得较 理论带宽值低得多的且动态改变的有限通信带宽。 口多跳的节点通信：由于移动节点的无线通信范围有限，对于两个无法直接通信的移 动节点可以通过多个中继节点的数据分组的转发来实现通信。 口存在单向的通信链路：由于移动自组网采用无线信道通信，受地形环境和发射功率 等因素的影响，有可能存在单向的通信链路；而在常规通信网络中，节点间通常是双向的 通信链路。 口移动通信设备的资源局限性：接入移动自组网的移动通信设备通常以p d a 、掌上型 电脑或手持式电脑为主要形式，这些设备均依赖于本机电池为其提供能量，并且内存较小、 c p u 性能较低，这满足了人们轻便移动的需求，但却给移动自组网环境下的应用设计开发 带来了一定的难度。 1 2 有限的通信安全：由于无线通信的开放性，加之移动自组网采用的分布式控制协议， 使得系统更容易受到窃听、主动入侵、拒绝服务、剥夺“睡眠”( 移动节点无法进入睡眠模式) 、 伪造等各种网络恶意攻击。此外移动通信设备由于其便携性和工作环境，也带来潜在的不 安全因素，例如电磁干扰、数据遗失、设备失窃等。 1 1 3 移动自组网的应用 从应用的角度来看由于移动自组网自身所具有的独特特点，使得其在军事及其他领 域有着巨大的应用价值，其应用领域主要表现在以下几个方面1 2 】【4 】： a 军事领域的应用：正如移动自组网的研究初衷一样，移动自组网最有价值的应用领 域就是军事领域。其一，它不依赖于固定网络通信设施，因而能满足部队移动通信系统快 速部署的要求，可以在没有可用通信网络的地方( 如野外、敌方战场、受战术打击的城市等) 迅速建立起己方的通信网络，保证部队作战任务的顺利完成；其二，由于在移动自组网络 中没有基站并采用分布式协议，使得网络具有较强的抗毁性，这满足了部队移动通信系统 对抗毁性的要求；其兰，由于网络中通信设备的移动性，为部队提供了较强的机动能力， 可以实现火力的快速机动，为新的作战样式提供了使用保证。这些都使得移动自组网在军 事领域具有巨大的应用价值。 口灾难搜救通信系统：对于如抗洪抢险、灾难搜救、森林救火等特殊应用环境，原来 搭建的网络通信设施有可能已全部毁坏或根本就没有建立，但救援人员之间的信息交流和 协同工作又是必需的，此时利用移动自组网技术就能快速搭建可使用的通信网络系统，满 第3 页 国防科学技术大学研究生院学位论文 足救援人员之间互相通信的需求，这都是传统网络系统无法满足的应用领域。 口环境监测灾难预警系统：传感器网络( s e n s o rn e t w o r k s ) 是移动自组网技术应用的一 种特殊形式。对于很多人员不能前往的特殊危险场合( 例如：林场、矿场、核试验场、化学 有害物质现场) ，可以使用布撤的传感器构建一个监测网络，通过传感器上的位置指示器、 热敏探头、压敏探头等装置收集环境状态信息。传感器将状态信息通过其他传感器的中继 发往现场以外的控制中心，使得环境状态可以得到人为的有效监控，遇有状态异常可提前 采取有效的控制措施。因而有效降低了灾难的可能性，同时大大降低了人员进场的危险性 并减少了人员工作量，这使得传感器网络具有非常广阔的应用前景。 口民用领域的应用：对于类似于会议信息交换系统、足球场裁判系统、出租车通信系 统、手持远程教育系统等应用，由于加入系统的节点均为移动通信设备，且应用状态多为 i f 缶时性的系统，则利用移动自组网技术就能实现网络的快速搭建、拆除和信息交换，这些 都是传统网络系统难以满足的应用领域。 1 , 1 4 移动自组网移动模型 为了全面地评估移动自组网技术，对移动模型的研究是非常重要的【5 i 6 1 【_ ”，因为移动自 组网的一个显著的特点是移动自组性，而移动性本身导致了网络拓扑的变化。移动模型刻 画了节点的移动模式，对网络拓扑的改变趋势的影响是显而易见的，因此我们对现有的移 动模型进行了研究，从而对移动模型做出相应的选择。 移动模型( m o b i l i t ym o d e l ) 的目的是模仿并刻画实际网络中节点的移动状况及特征，为 研究提供合理的环境。这要求移动模型中移动节点的速度和方向的改变应发生在合理的时 间点以尽量接近真实网络的节点移动【5 j 。现阶段用于网络模拟的移动模型有两种：路径模 型( t r a c e sm o d e l ) 和混合模型( s y n t h e t i cm o d e l ) 。路径模型主要是通过非常详细而精确的节点 轨迹信息来刻画节点的移动，非常适合刻画真实生命系统中目标的移动，特别是在有大量 的参与者和较长的观测时间的情况下。而混合模型主要是对节点的移动模式进行约束但并 不记录详细的移动轨迹。因为移动自组网环境中节点的轨迹信息因其移动的不规则性而并 不容易得到，因此对于移动自组网环境来说更适合采用混合模型。 而现有的混合模型主要分为两类：个体移动模型和群组移动模型。 个体移动模型( s i n g l em o b i l i t ym o d e l ) 亥1 画单个节点的移动，主要有以下几种 雹随机运动移动模型( r a n d o mw a l km o b i l i t ym o d e l ) 随机运动移动模型刻画的节点运动规律是：网络节点随机均匀分布在运动区域中，其 后每个节点独立地在给定的速度 m i n s p e e d - m a x s p e e d _ 乖1 1 方向范 0 - 2 r e 】内随机选择 一确定的速度和方向，在一固定间隔( 固定时间间隔t 或固定距离d ) 后进行速度和方向的重 新选择，周而复始。其示意图如图1 4 所示。 第4 页 国防科学技术大学研究生院学位论文 此模型主要的缺点是：移动节点会在初始点附近运动。会出现突然变速，突然改变方 向等不切合实际的现象。并且短时间内会出现邻居节点大量变化的情况，当移动时间较长 后，变化节点的比率趋向稳定。 此模型主要应用于对分子运动、热运动、布朗运动的刻画。 图1 4 随机运动移动模型示意图图1 5 随机路点移动模型示意图 臣随机路点移动模型( r a n d o mw a y p o i n tm o b i l i t ym o d e l ) 随机路点移动模型刻画的节点运动规律是：网络节点随机均匀分布在运动区域中，其 后每个节点独立地在给定的速度范 m i n s p e e d m a x s p e e d 内随机选择一确定的速度和在 运动区域内随机选择一确定的目标点，到达目标点后等待一随机选择的暂停时间( p a u s e t i m e ) ，此后进行速度和目标点的重新选择，周而复始。其中当暂停时间为o s 时，模型类 似于随机运动移动模型( r a n d o m w a l k m o b i l i t y m o d e l ) 。其示意图如图1 5 所示。 此模型主要的缺点是：节点移动主要集中于运动区域的中部，节点穿越中部的概率非 常大，导致出现节点聚集现象( 聚集于运动区域中部) 。 此模型主要应用于对随机运动的刻画。 固随机方向移动模型( r a n d o md i m a i o nm o b i l i t ym o d e l ) 随机方向移动模型刻画的节点运动规律是：网络节点随机均匀分布在运动区域中，其 后每个节点独立地在给定的速度范围【m i n s p e e “m a x s p e e d 】和方向范围 0 2 n 内随机选择 一确定的速度和方向，当节点移动到运动区域边界后等待一随机选择的暂停时i 司( p a u s e t i m e ) ，此后进行速度和方向o - - 的重新选择，周而复始。其示意图如图1 6 所示。 此模型主要的优点是：节点移动均匀分布于运动区域内，缓解了节点聚集现象。 此模型主要的缺点是：移动节点间的通信平均跳步数比其他移动模型多狰】，以及出现 网络分割的概率比其他移动模型高1 5 l 。 第5 页 国防科学技术大学研究生院学位论文 口t 1 j 蛳啪 图1 6 随机方向移动模型示意图图1 7 随机高斯马尔科夫移动模型示意图 瞳随机高斯马尔科夫移动模型( r a n d o mg a u s s ，m a r k o vm o b i l i t ym o d e l ) 随机高斯- 马尔科夫移动模型刻画的节点运动规律是：网络节点随机均匀分布在运动区 域中，其后每个节点独立地在给定的速度范 m i n s p e e d - m a x s p e e d 和方向范围【0 2 兀 内随 机选择一确定的速度和方向，在固定时间间隔t 后进行速度和方向的重新选择( 但速度和方 向均与上一时间间隔的速度和方向相关，如下面的公式所示，其中口为变化参数) ，周而复 始。其示意图如图1 7 所示。 一r ：一 速度：k = 口k l + ( 1 一a ) v + ( 1 一口2 ) 。，( 口：0 o f 1 ) 一r ：一 方向：幺= 口已一1 + ( 1 一a ) e + ( 1 一口2 ) ，( o f 0 口1 ) 其中：只、k 是服从高斯分布的随机变量： a ：变化参数( o 7 5 ) ；a = o 随机运动；口= 1 直线运动； 矿：平均速度；p ：平均角度： 位置：= x + 圪一l c o s b ly 。= y n 一1 + 圪一ls i n 铱一l 此模型主要的优点是；通过网络节点移动的前后速度相关性，消除突然变速、改变方 向等不切合实际的现象。 瞳城区移动模型( c i t ys e c t i o nm o b i l i t ym o d e l ) 城区移动模型刻画的节点运动规律是：网络节点在给定的运动区域中的给定线路上移 动，其移动的速度和方向受给定路线参数的限制。其示意图如图1 8 所示。 此模型主要的优点是：较真实的刻画了城区街道的交通和路线状况。 此模型主要的缺点是：必须事先给定设计好的带有路线参数限制的运动区域图。 此模型主要应用于对城区交通的刻画。 第6 页 国防科学技术大学研究生院学位论文 。& _ _ 图1 8 城区移动模型示意图图1 9 概率随机运动移动模型示意图 嗣概率随机运动移动模型( p m b a b i l i s t i cv e r s i o no f r a n d o mw a l km o b i l i t ym o d e l ) 概率随机运动移动模型刻画的节点运动规律是：网络节点随机均匀分布在运动区域 中，其后节点利用一给定的概率矩阵及对应的状态迁移模式决定下一目标点的坐标，周而 复始。使用如下的概率矩阵p 和状态迁移模式而获得的单节点移动轨迹的概率随机运动移 动模型如图1 9 所示。 o 3 0 5 概率矩阵：p = 00 5o 5 0 3 0 70 o - 30o 7 【x ，y ：当前节点位置坐标 x ，y ：下一节点位置坐标 此模型主要的优点是：不会出现突然变速，突然改变方向等不切合实际的现象。 此模型主要应用于对个人行为、任务路线和公路交通的刻画。 群组移动模型( g r o u pm o b i l i t ym o d e l ) 刻画一组节点的移动，主要有以下几种 回指数相关随机移动模型( e x p o n e n t i a lc o r r e l a t e dr a n d o mm o b i l i t ym o d e l ) 指数相关随机移动模型刻画的节点运动规律是：在节点运动区域内，给定节点或组的 t 时刻位置b ( t ) ，则其什1 时刻位置b ( t + 1 ) g q 下式给出。其中f 为变化参数，其值越小则节 点或组的位置变化越大。 ，厂。= - 、 6 0 + 1 ) = 6 ( f ) 8 一v 7 + l 盯1 一( e - n 7 ) 2i， 其中：r 变化参数：盯、，是服从高斯分布的随机变量： 此模型主要的缺点是：物理意义并不明确，很难选定合适的参数的值。 第7 页 | | 一 。一 一 ， 、一 一 。 一 一 一 一 国防科学技术大学研究生院学位论文 图1 1 0 纵队移动模型示意图 图1 h 参考点组移动模型示意图 置纵队移动模型( c o l u m nm o b i l i t ym o d e l ) 纵队移动模型刻画的节点运动规律是：在节点运动区域内，为组内的每一节点指定一 参考点( 参考点之间在小范围内呈直线或曲线分布) ，其后节点相对其指定参考点作符合个 体移动模型( 随机运动移动模型、随机路点移动模型等) 的移动，而参考点作指定的运动( 直 线运动或绕腿点旋转等) ，周而复始。其示意图如图1 1 0 所示。 此模型主要应用于对灾难搜救、队列行进的刻画。 圄参考点组移动模型( r e f e r e n c ep o i n tg r o u pm o b i l i t ym o d e l ，r p g m ) 参考点组移动模型刻画的节点运动规律是：在节点运动区域内，为一组节点指定一逻 辑中心( l o 西c a lc e n t e r ) ，其后节点相对于这一逻辑中心作符合个体移动模型( 随机运动移动 模型、随机路点移动模型等) 的移动，而逻辑中心作指定的运动( 直线运动或给定路线运动 等1 ，周而复始。其中节点的实际坐标为逻辑中心坐标与节点相对于逻辑中心偏移量的矢量 和。单组的参考点组移动模型其示意图如图1 1 1 所示。 此模型主要应用于对组、队列行进的刻画。 移动模型( m o b i l i t ym o d e l ) 的目的是模仿并刻画实际网络中节点的移动状况，为研究提 供合理的环境。现阶段关于移动模型的研究结论e 删【7 j 主要有：不同的移动模式将会对移 动自组网的协议的性能产生显著的影响；同样的移动模式，但采用不同的参数，也会对 移动自组网的协议的性能产生显著的影响；选择移动模式时，应关注数据的传输模式， 因为它对移动自组网的协议的性能产生显著的影响：对移动自组网的性能进行评估时， 应尽量接近实际应用环境；假如实际应用环境是未知的，则应该进行综合的考虑。 医此本文根据我们研究的课题内容选择了有代表性的三种移动模式：随机路点移动模 型( r a n d o mw a y p o i n tm o b i l i t ym o d e l ) 、随机高斯马尔科夫移动模型( r a n d o mg a u s s m a r k o v m o b i l i t ym o d e l ) 以及参考点组移动模型( r e f e r e n c ep o i n tg r o u pm o b i l i t ym o d e l ，r p g m ) 作为 以后评价我们提出的副本放置算法性能的移动模型。 第8 页 国防科学技术大学研究生院学位论文 1 2 数据复制技术研究 作为一种网络构架，与移动自组网相关的技术涉及到了网络的每一层。应用层以下各 层提供可靠的传输，但对用户本身蔗言，它们并不进行任何实际的应用工作，要完成用户 数据查询和数据更新的任务，就必须有上层的数据管理技术的支持，而数据复制技术是数 据管理技术中提高数据可用性、系统可靠性和系统性能的重要手段。 在移动自组网环境中，数据复制技术是提高系统可靠性和系统性能的重要技术，原因 在于：其。一，由于无线通信带宽的有限性，数据复制可以提高网络容量，有效利用有限的 网络带宽：其二，由于在移动自组网环境中网络更容易出现链路失效、站点失效以及网络 分割，数据复制能提高系统整体的可靠性；其三，由于移动节点通过无线信道发送接收数 据会耗费大量电能，数据复制能通过减少跳步数，减少网络整体能量消耗，延长网络生存 时间；其四，由于在移动自组网环境中大部分应用实时性要求高，数据复制通过减少数据 访问的响应时间，保证应用系统的高实时性要求。 因此研究移动自组网环境中的数据复制技术具有重要的研究价值和意义。本节将围绕 数据复制技术来讨论数据复制算法所研究的问题、数据复制的研究现状及其不足、以及移 动自组网环境中数据复制算法所应该具有的特征等。 1 2 1 数据复制问题分析 1 - 2 1 1 复制算法研究的问题 数据复制技术被广泛应用于数据库系统、文件系统、操作系统和分布式系统中1 8 】【9 】。 根据不同的应用环境，数据复制所关心的问题并不尽相同。本文研究的数据复制技术是指 将同一内容的数据对象的副本分别存储在不同的网络节点上，主要目的是提高系统性能。 数据复制算法( d a t ar e p l i c a t i o na l g o r i t h m ) 是决定网络系统中的数据对象( d a t ao b j e c t ) 的放置数目( r e p l i c a t i o nl e v e l ) 和放置位置( r e p l i c a t i o np l a c e m e n t ) 愀 1 。其基本思想是 根据给定的性能评价模型，设法在数据访问开销与数据更新开销之闻取彳导一个最佳的平衡， 从而合理地放置副本，减少数据访问时间或降低网络通信开销或减少网络整体能量消耗， 达到提高系统性能的目的。因此数据复制算法也被称为副本放置算法( r e p l i c aa l l o c a t i o n a l g o r i t h m ) 或复制调度算法( r e p l i c a t i o ns c h e d u l ea l g o r i t h m ) 或副本调度算法( r e p l i c a s c h e d u l e a l g o r i t h m ) 。本文在以后的讨论中如无特殊说明则对数据复制算法、复制调度算法、 副本调度算法和副本放置算法这四个术语不予区别。 从算法功能逻辑角度看，数据复制算法可以看作是一黑盒决策系统，通过不同的输入， 给出确定的合理的副本放置方案或操作。图1 1 2 给出了数据复制算法的功能逻辑图。 第9 页 国防科学技术大学研究生院学位论文 图1 1 2 数据复制算法功能逻辑图 田性能评价模型：决定副本放置算法的决策评价标准。主要的评价标准有通信开销、 i o 开销、存贮开销、能量开销等。对于不同的应用条件和约束条件，性能评价的标准可 能并不相同，因此并不存在统一的且唯一正确的性能评价模型。 啊读写模式：即数据访问模式，描述了网络系统中节点对数据对象读写操作的时间、 数量和请求分布。 墨全局漏部信息：决定副本放置算法决策时的信息拥有量。副本放置问题是n p 完全 问趔1 1 】【1 2 】，因而从理论上来说信息的拥有量越大，算法产生的副本放置方案越接近于最优 副本放置方案。 圈副本一致性协议：决定副本放置算法采取的副本更新一致性的策略。副本一致性必 须确保系统对副本数据的操作的并发执行等同于对主本数据的正确执行( 又被称为单一拷 贝可串行性，o n ec o p ys e r i a l i z a b i l i t y ) ，并保证一个数据对象的不同拷贝是相互一致的，使 用户能得到数据对象的相同视图嘲【比】。 囹用户应用需求：用户应用系统对副本放置算法的特殊要求。例如实时性要求、算法 消息复杂度( m e s s a g ec o m p l e x i t y ) 瞵】要求等。 圄副本放置方案：决定每个数据对象的副本数目以及这些副本的放置位置。副本的数 量必须保持合适，对于只读或读请求占多数的数据对象，希望副本数多，相反对于写请求 多的数据对象，希望副本数尽量少，因为必须考虑维护数据副本一致性的开销。副本放置 位置的选择既要保证数据的可用性，同时也要使访问开销尽量小。 1 2 1 2 数据复制算法的分类 数据复制算法根据不同角度可做如下分类【8 】i l o 】【1 3 1 。 根据是否知道全局信息和是否进行集中控制可将复带4 算法分为以下两种： 口集中式数据复制算法( c e n t r a l i z e dr e p l i c a t i o na l g o r i t h m ) ：集中式数据复制算法根据 获得的网络全局信息，采用相应策略针对每个数据对象决定副本数目及副本在网络中的 放置位