（通信与信息系统专业论文）基于自然计算的无线多跳网络qos路由研究.pdf

直塞鳗壹态堂盟班塞生堂焦论塞基王自然让篡故玉绔奎爨围络鲤墨堕由班宜 摘要 无线多跳网络是由系统中的通信结点通过分布式协议互连或组织起来 的网络系统。因为其不需要任何固定设施支持，且能够提供特别灵活的通 信，所以无线多跳网络在很多地方都能发挥作用，但也带来很大的挑战， 其中之一就是q o s 路由。现有的传统的q o s 路由协议都是为传统的有线网 提出来的，并不适用于无线多跳网络。 在无线多跳网络中要提供q o s 服务，q o s 路由起着重要的作用。一般 说来，q o s 路由的目标有两个：选择符合q o s 约束的路由；充分利用网络 全局资源，自适应地处理可能的网络拥塞。因此，q o s 路由对于无线多跳 网络的推广应用有着至关重要的作用。 自然计算是一个新兴的研究领域。受自然界和其他一些物理现象的启 发，我们提出一些新的策略来解决当前无线多跳网络中的q o s 路由问题， 我们所做的工作主要包括以下几个方面： l 、结合群集智能和链路不相交多径路由提出基于蚁群的多径路由协 议。协议通过建立和利用多重链路不相交路由来同时发送数据分组，并通 过信息素来分散通信量，因此更能适应无线自组网络的动态变化和更好的 支持q o s 。仿真结果表明算法具有较好的性能。 2 、提出基于模拟退火的算法来解决a dh o e 网络中的多重q o s 路由问 题。该方法首先运用能量函数，把多个q o s 权转换成一个新的复合度量，然 后通过模拟退火找到可行的路由。 3 、结合均场退火的特点，我们提出基于均场退火的路由算法m f ar a 来解决无线网状网中多重约束的q o s 寻路问题。由于在均场退火中采用了 一组确定性的等式来取代模拟退火中的随机更新过程，并且在计算平衡态 平稳概率分布时采用鞍点近似，算法的收敛时间比基于模拟退火的算法的 要大为减少。 4 、提出了一个改进的f s r 协议c o f s r 。c o f s r 继承了f s r 简单， 高效和扩展性强的优点，并综合考虑了m a c 层和网络层状态，运用跨层技 术来提高网络的性能。在c o f s r 中，负载重的结点，即使其位于源宿之 i 间的最短路由上，也不会被选为中间结点来转发数据分组。仿真结果表明 c o f s r 可以减少平均端到端时延，提高网络吞吐量。因此c o f s r 特别适 用于解决大规模a dh o c 网络的路由问题。 关键词：无线多跳网络，无线a dh o e 网络，无线网状网，蚁群优化算法， 模拟退火，均场退火，鱼眼技术，跨层技术，q o s 路由。 v i a b s t r a c t w i r e l e s s m u l t i - h o p n e t w o r k sh a v e e m e 唱e d a s a n e w i n f o r m a t i o n - t r a n s m i s s i o np a r a d i g mb a s e do nc o l l a b o r a t i v ee f f o r t so fm u l t i p l e s e l f - o r g a n i z e dm o b i l en o d e s w i t h o u tt h es u p p o r tf r o ma n yf i x e di n f r a s t r u c t u r e ， t h i st y p eo fn e t w o r kp r o v i d e sa ne x t r e m e l yf l e x i b l em e t h o df o re s t a b l i s h i n g c o m m u n i c a t i o n si ns i t u a t i o n sw h e r eg e o g r a p h i c a lo rt e r r e s t r i a lc o n s t r a i n t s d e m a n dt o t a l l yd i s t r i b u t e dn e t w o r ks y s t e m w h i l et h ei n h e r e n tc h a r a c t e r i s t i c so f aw i r e l e s sm u l t i - h o pn e t w o r km a k ei tu s e f u lf o rm a n ya p p l i c a t i o n s ，t h e ya l s o b r i n gi nal o to fr e s e a r c hc h a l l e n g e s o n eo f t h ei m p o r t a n ti s s u e si sq o sr o u t i n g ， s i n c ec o n v e n t i o n a lr o u t i n gp r o t o c o l sa d o p t e df o rt r a d i t i o n a ln e t w o r k sa r en o t d i r e c t l ya p p l i c a b l et ow i r e l e s sm u l t i - h o pn e t w o r k s q o sr o u t i n gp l a y sa ni m p o r t a n tr o l ef o rp r o v i d i n gq o s i nw i r e l e s sm u l t i _ h o p n e t w o r k s t h eg o a l so fq o sr o u t i n ga r ei ng e n e r a lt w o f o l d ：s e l e c t i n gr o u t e sw i t h s a t i s f i e dq o sr e q u i r e m e n t ( s ) ，a n da c h i e v i n gg l o b a le f f i c i e n c yi nr e s o u r c e u t i l i z a t i o nw h i l ep r o c e s s i n gt h ep o s s i b l ec o n g e s t i o ns e l f - a d a p t i v e l y q o sr o u t i n g i sc r i t i c a lt ot h ed e v e l o p m e n to fa n yr e a la p p l i c a t i o no fw i r e l e s sm u l t i - h o p n e t w o r k s n a t u r a lc o m p u t a t i o ni saf i e l do fr e s e a r c ht h a ti sc o n c e r n e dw i t hb o t ht h eu s e o fb i o l o g ya si n s p i r a t i o nf o rs o l v i n gc o m p u t a t i o n a lp r o b l e m sa n dt h eu s eo ft h e n a t u r a lw o r l di t s e l ft os o l v ep r o b l e m s i n s p i r e df r o ma n tc o l o n y , a n n e a l i n g p r o c e s sa n df l s h e y et e c h n o l o g y , w ep r o p o s e ds o m e n e wa l g o r i t h m st os o l v eq o s r o u t i n gp r o b l e m i nw i r e l e s sm u l t i - h o pn e t w o r k s t h em a j o ra c h i e v e m e n to ft h i s d i s s e r t a t i o nc a nb eo u t l i n e da sf o l l o w s ： 1 c o m b i n i n gs w a r mi n t e l l i g e n c ea n dl i n kd i s j o i n tm u l t i - p a t hr o u t i n g ，an o v e l a p p r o a c hi sp r o p o s e di nc h a p t e r3 。i te s t a b l i s h e sa n du t i l i z e sm u l t i p l er o u t e so f l i n kd i s j o i n tp a t ht os e n dd a t ap a c k e t sc o n c u r r e n t l ya n da d o p t sp h e r o m o n et o d i s p e r s ec o m m u n i c a t i o nt r a f f i c ，t h u si tc a na d a p tt ot h ed y n a m i cc h a n g e s o ft h e n e t w o r ka n ds u p p o r tq o sb e t t e r t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e d i x a p p r o a c h e so u t p e r f o r mo t h e rp e r t i n e n ta l g o r i t h m s 2 an o v e lq o s r o u t i n ga l g o r i t h mb a s e d o ns i m u l a t e da n n e a l i n g ( s ar a ) i s p r o p o s e di nc h a p t e r4t os o l v et h em u l t i - c o n s t r a i n t sq o sr o u t i n gp r o b l e mi n w i r e l e s s a dh o cn e t w o r k s t h i sa l g o r i t h mf i r s tu s e sa ne n e r g yf u n c t i o nt o t r a n s l a t em u l t i p l eq o sw e i g h t si n t oas i n g l em i x e dm e t r i ca n dt h e ns e e k st of i n d af e a s i b l ep a t hb ys i m u l a t e da n n e a l i n g 3 an o v e lm u l t i c o n s t r a i n e dr o u t i n gs c h e m eb a s e do nm e a nf i e l d a n n e a l i n g ( m f a _ r a ) i sp r o p o s e dt os e a r c h i n gf o rt h eo p t i m a lr o u t et h a tc a n s a t i s f ym o r et h a no n eq o sp a r a m e t e r ss i m u l t a n e o u s l yi nw i r e l e s sm e s h n e t w o r k s m e a nf i e l da n n e a l i n g ，w h i c ha d o p t ss a d d l ep o i n ta p p r o x i m a t i o n ，u s e s as e to fd e t e r m i n i s t i ce q u a t i o n st or e p l a c et h es t o c h a s t i cp r o c e s si ns a ，t h u si ti s m o r ee f f i c i e n tt h a ns a 4 a ne n h a n c e df s rn a m e dc o - f s ri sp r o p o s e di nc h a p t e r6 c o f s r i n h e r i t st h em e r i to ff s rs u c ha ss i m p l e ，e f f i c i e n ta n ds c a l a b l ee t e ，a n di t s y n t h e t i c a l l yc o n s i d e r st h es t a t eo fm a c a n dn e t w o r kl a y e r ，a d o p t sc r o s s l a y e r t e c h n o l o g yt oa c h i e v eb e t t e rn e t w o r kp e r f o r m a n c e i nc o - f s r , t h en o d et h a t h a sw o r s et r a f f i cl o a ds t a t ew i l ln o tb es e l e c t e dt of o r w a r dd a t ap a c k e t se v e n t h o u g hi ti so nt h es h o r t e s t ( t h a ti s ，t h en u m b e ro fh o p si st h es m a l l e s t ) p a t h b e t w e e ns o u r c e - - d e s t i n a t i o np a i r s i m u l a t i o nr e s u l t ss h o w sc o - - f s rc a nd e c r e a s e a v e r a g ee n d - t o e n dd e l a ya n di n c r e a s et h r o u g h p u te s p e c i a l l yw h e nt h en e t w o r k h a sm o r eo f f e r e dl o a d t h u sc o f s rp r o v e st ob eam o r ee f f i c i e n ts o l u t i o nt o t h er o u t i n gp r o b l e mi nl a r g es c a l ea dh o en e t w o r k s k e y w o r d ：w i r e l e s sm u l t i h o pn e t w o r k s ，w i r e l e s sa dh o cn e t w o r k s ，w i r e l e s s m e s hn e t w o r k s ，a n tc o l o n yo p t i m i z a t i o n ，s i m u l a t e da n n e a l i n g ，m e a nf i e l d a n n e a l i n g ，f i s h e y et e c h n o l o g y ，c r o s s - l a y e rt e c h n o l o g y ，q o sr o u t i n g x 直塞鲤皇太堂簋班塞生堂焦途塞基王自然让簋酸玉绔垒鞋圈络鲤墨醯由受塞 缩略语 绁 a o d v a r a a c o a d r a a l m r b e b f s c s m a c d c d c t c b r c t s c o f s r c e d a r d s d v d s r d c f d a f s r g e a r g a m a n g p s a l l t l s l a r m e m s m f a m a b r m f ar a 接入点 a dh o c 网络按需距 离向量路由协议 基于蚁群的路由算 法 蚁群优化算法 基于蚂蚁的分布式 路由算法 基于蚁群的链路不 相交多径路由 尽最大努力 广度优先搜索 载波监听多路访问 冲突检测 收敛时间 恒定比特率 清除发送 跨层优化鱼眼状态 路由 核心提取分布式a d h o c 路由 目的结点序列距离 向量路由 动态源路由协议 分布式协调功能 目的结点地址 鱼眼状态路由 基于地理位置节省 能量的路由 基于遗传算法的路 由算法 g p s 类蚂蚁路由算 法 最新时间戳 链路状态 位置辅助路由 微电子机械系统 均场退火 基于移动代理路由 基于均场退火路由 算法 a c c e s sp o i n t a d h o co n - d e m a n dd i s t a n c ev e c t o r r o u t i n g a n t - c o l o n yb a s e dr o u t i n ga l g o r i t h m a n tc o l o n yo p t i m i z a t i o n a n t b a s e dd i s t r i b u t e dr o u t i n ga l g o r i t h m a n tc o l o n yb a s e dl i n k - d i s j o i n tm u l t i p a t h r o u t i n g b e s t e 筋n b r e a d t hf i r s ts e a r c h c a r r i e rs e n s em u l t i p l ea c c e s sw i 廿l c o l l i s i o nd e t e c t i o n c o n v e r g e n c et i m e c o n s t a n tb i tr a t e c l e a r - t o s e n d c r o s s - l a y e ro p t i m i z e df i s h e y e s t a t e r o u t i n g c o r e e x t r a c t i o nd i s t r i b u t e da dh o e r o u t i n g d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r r o u t i n g d y n a m i cs o u r c er o u t i n g d i s t r i b u t e dc o o r d i n a t i o nf u n c t i o n d e s t i n a t i o na d d r e s s f i s h e y es t a t er o u t i n g g e o g r a p h i c a la n de n e r g ya w a r er o u t i n g g e n e t i ca l g o r i t h mb a s e dr o u t i n gm e t h o d f o ra d h o cn e t w o r k s g p s a n t - l i k er o u t i n ga l g o r i t h m l a t e s tt i m e s t a m p l i n ks t a t e l o c a t i o na i d e dr o u t i n g m i c r oe l e c t r om e c h a n i c a ls y s t e m s m e a nf i e l da n n e a l i n g m o b i l ea g e n t sb a s e dr o u t i n g m e a nf i e l da n n e a l i n gb a s e dr o u t i n g a i g o r i t h m s m f n n h a n h d n n l s o c n d o l s r q o s q o s r r i p r t s s ar a s a s r s t a r s m r s t p s t b f t o r a t t w i f i w c e t t 凡a n 俸嗄n w s n z i 冲 均场网 下一跳地址 下一跳距离 邻居结点链路状态 最优普通结点分解 优化链路状态路由 协议 服务质量 q o s 路由 路由信息协议 请求发送 基于模拟退火路由 模拟退火 成功比率 源树自适应路由 分裂多径路由 源传输能量选择 基于轨线转发 临时需求路由算法 拓扑表 无线保真 加权累积期望传输 时间 无线局域网 无线网状网 无线传感器网络 区域路由协议 m e a nf i e l dn e t w o r k s n e x th o pa d d r e s s n e x th o pd i s t a n c e n e i g h b o rn o d el i n ks t a t e o p t i m a lc o m m o nn o d ed e c o m p o s i t i o n o p t i m i z e dl i n ks t a t er o u t i n gp r o t o c o l q u a l i t yo fs e r v i c e q o sr o u t i n g r o u t i n gi n f o r m a t i o np r o t o c o i r e q u e s t - t o s e n d s i m u l a t e d a n n e a l i n g b a s e d r o u t i n g a l g o r i t h m s i m u l a t e da n n e a l i n g s u c c e s sr a t i o s o u r c et r e ea d a p t i v er o u t i n g s p l i tm u l t i p a t hr o u t i n g s o u r c et r a n s m i tp o w e rs e l e c t i o n t r a j e c t o r yb a s e df o r w a r d i n g t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m t o p o l o g y1 a b l e w i r e l e s sf i d e l i t y w e i g h t e d c u m u l a t i v e e x p e c t e d t r a n s m i s s i o nt i m e w i r e l e s sl o c a la r e an e t w o r k s w i r e l e s sm e s hn e t w o r k s w i r e l e s ss e n s o rn e t w o r k z o n er o u t i n gp r o t o c o l i 蛊宝整虫盔堂煎班巍垒堂焦监塞 基王自然让篡艘玉绔垒丛匾络鲤墨睦由班红 图表 f i g1 1 无线网络5 f i g1 2 无线a dh o c 网络。6 f i g1 3 无线网状网络7 f i g1 4 无线传感器网络8 f i g3 1 蚂蚁是如何发现食物源和巢穴之间的最短路由的3 3 f i g3 2 分组格式3 5 f i g3 3 路由发现阶段3 8 f i g3 4 由一个流网络构造两条不相交路径3 9 f i g3 5 分组成功投递率4 2 f i g3 6 平均端到端时延。4 3 f i g3 7 路由负载4 4 f i g4 1a dh o c 网络中多约束q o s r 举例5 5 f i g4 2 具有双向无限链路的一个a dh o c 网络举例5 6 f i g4 3 可能生成树5 6 f i g4 4 移动a dh o c 网络中的q o s r 5 7 f i g4 5 不同马尔可夫链长度下的收敛时间5 9 f i g4 6 收敛时间和初始化温度的关系( 2 0 个结点( 7 2 5 条路由) ) 6 0 f i g4 7s ar a 和g a m a n 的成功率比较6 0 f i g4 8s a r a 和g 从a n 收敛时间比较6 l f 逛5 1m f n 程序流程图6 9 f i g5 2 一个简单的w m n 示意图7 1 f i g5 3 不同退火进度表下的算法收敛时间7 3 f i g5 4 不同退火进度表下算法的成功率7 4 f i g5 5 收敛时间和结点数的关系( q = 0 9 0 ) 7 4 f i g5 6 肝a _ r a 和基于s a 的算法的成功率( q = o 9 0 ) 7 5 f i g6 1 鱼眼范围8 0 f i g6 2 邻居结点链路状态列表a ，拓扑表b 和路由表c 示意图8 i f i g6 3 网络层和m a c 层之间的相互作用8 3 f i g6 4 算法的平均端到端时延8 5 f i g6 5 算法的吞吐量8 6 4 南京邮电大学学位论文独创性声明 本入声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：导师签名：日期： 窟塞整皇太堂簋班窭生堂位淦塞筮= 童曼i 直 第一章引言 1 1 无线多跳网络概览 最近无线多跳网络已经作为种新的无线网络形式出现。因其具有易 部署，自组织和不需要任何固定设施或接入点的支持等特点，故无线多跳 网络是一种充满希望的无线技术，将对我们的日常生活带来巨大影响【1 】【2 】。 无线多跳网络的应用场合包括：军事跟踪，探险，侦察，宽带室内联网以 及即时会议等等。无线多跳网络近来受到越来越多的关注。无线多跳网络 包括无线a dh o e 网络 3 】，无线传感器网络【4 】以及无线网状网络【5 】。本论文 的研究集中在无线a dh o c 网络和无线网状网络中的q o s 路由问题方面。 f i g1 1 无线网络 1 1 1 移动a dh o c 网络 无线蜂窝网( 见图1 1 ) 已经从二十世纪八十年代就开始投入应用了， 期间经历了第一代、第二代和第三代无线系统的演变。这种类型的系统依 赖于基站( 接入点) 的支持。接入点帮助从一个地方移动到另一个地方的 无线用户与无线系统保持连接。 固定支持架构的存在限制了无线系统的适应性。换句话说，当没有固 5 定设施支持的时候，该技术将不能有效工作。未来的无线系统要求简单快 速布置，但当前的无线系统架构并不能达到要求。 f i 9 12 无线a dh o c 刚络 最近，随着蓝牙技术的发展，种新型的无线系统一无线a dh o c 网络( 见 图11 7 1 1 12 ) 应运而生。无线a dh o c 网络不需要固定设施的支持，非常适用 于需要快速和简单网络部署的场合。a dh o c 起源于拉丁语，意思是“仅为 这个”。无线a dh o c 叫络是一个自治系统网络中的结点用无线信道连接， 每一卜结点作为一个终端，兼有路由器的功能。 无线a dh o c 碍络中的结点可以自由移动和以任意方式组织起来。每一个 结点在与其他结点通信的过程中，可以任意地移动。每一对结点之间可以 有多跳链路连接。 在没有接入点的时候，流行的i e e e 8 0 21 1 “w i - - f i ”协议叫以在较低 的水平提供无线a dh o c 网络的功能。但是在这种场合，结点被限制只能收发 信息，不能经过网络转发信息。无线a dh o e q 络可卧独立组网，或者与更加 大型的网络一i n k m 吐相连。 无线a dh o c 习络能够实现“在任意地点和任意时间”通信的梦想，故其 被广泛应用于灾难救助或者军事行动上。由于不局限于特定的位置，这种 网络同样可以在其他地方显示较好的性能。比如一组带有膝上型电脑的人 们，在一个不能提供网络服务的地方开商务会议，他们可以很容易的组建 个a dh o c 网络来互相通信。这仅仅是这种网络的很多可能的运用范例中的 种。 f i 9 1 3 无线网状网络 、毒o 。女 4 j 。- - - - - - ， 1 1 2 无线网状网络 w l a n 在接入领域的发展有目共睹，但是由于其基站覆盖范围的限制 使得用其建设公众宽带网成本很大，并且一直存在可伸缩性低和健壮性差 等诸多问题。最近发展起来的无线嘲状网( w m n ) 7 8 ( 见圈l3 ) 技术 有望给无线宽带领域带来重大变革。实际上w i r e l e s s m e s h 可以看作是 a dh o e 技术的简化版本和无线版、缩微版的互联网。a dh o c 网络仍然处于研 究阶段，而无线网状网络已经获得了初步应用。 在传统的无线局域网( w l a i 0 中，每个客户端均通过一条与接入点 ( a p ) 相连的无线链路来访问网络用户之间如果要进行相互通信的话， 必须首先访问一个固定的接入点( a p l ，这种网络结构被称为单跳网络。而 在无线网状网络巾，任何无线设备结点都可以同时作为a p 和路由器，网络 中的每个结点都可以发送和接收信号，每个结点都可以与一个或者多个对 等结点进行直接通信。这种结构的最大好处在于：如果最近的a p 由于流量 过大而导致拥塞的话，那么数据可以自动重新路由到一个通信流量较小的 邻近结点进行传输。依此类推数据包还可以根据网络的情况继续路由 到与之最近的下一个结点进行传输，直到到达最终目的地为止。这样的访 问方式就是多跳访问。 在无线网状网络中，有一些专用结点，这些结点和结点之间不仅可以 互相通信，而且还为用户结点与用户结点之间或者用户结点与接入点之间 产生的数据提供无线传输服务( 这里的接入点是一种专门的无线路由器， 与i n t e m e t 主干网采用宽带连接) 。在这种网络中，业务流主要是流向网关 而非发生在网络内部的结点之间。要使得w m n 得到更好的应用，还有很多 问题需要得到解决。其中包括互操作性不强( 无线m e s h 网络现在还没有统 一的技术标准，面临各个厂家各种不同类型的嵌入式无线设备接口的问 题) ，安全性不高( 无线m e s h 网络的多跳机制决定了用户通信要经过非常 多的节点。而数据通信经过的节点越多，安全问题就越变得不容忽视) ， 通信延迟大和较难提供q o s ( 随着无线m e s h 网络规模的扩大，跳接越多， 系统越复杂，积累的总延迟就会越大，提供q o s 保障将变得比较困难，一些 对q o s 要求高的应用，如话音或流媒体应用等，可能面临质量无法接受的问 题) 。 u s e r s e n s o rf i e l d s e n s o rn o d e s f i g1 4 无线传感器网络 1 1 3 无线传感器网络 随着基于微电子机械系统( m e m s ) 的传感器技术，低功耗模拟数字 电子技术和低功率射频设计等方面的发展，传感器网络【4 】越来越引起人们 的兴趣( 见图1 4 ) 。传感结点是微小的设备，能够感知物理参数，处理收 集到的数据，并且能与监控基站通过网络进行通信。无线传感器网络是由 一组通过无线方法执行分布式感应任务的结点组成的，其与移动a dh o c 网络 【3 】的区别主要表现在以下五个方面： 8 i ) 传感器网络中的结点数目要比a dh o e 网络中的大得多。 i i ) 在许多应用场合，传感结点一旦放置，其位置将不会再改变。 i i i ) 传感结点布置得很稠密并且容易失效。 i v ) 传感结点具有能量，计算能力和存储容量受限的特点，因此如何延长传 感器结点的寿命是一个研究热门。 v ) 由于负载较大和结点数目较多，传感结点可能不具有全局i d 。 1 2 无线多跳网络中的q o s 路由问题 当前的无线多跳网络具有脆弱，刚性和难配置以及维护的特点，网络 规模的加大和拓扑结构的剧烈改变，更加加大了网络配置和维护的难度。 无线网络的不需要固定设施支持的特点已经在学术界引起了较大的关注。 一些在有线网络中推出的服务，比如视频会议，在线电影以及即时短信等 等同样在无线多跳网络中也有迫切需求。要得到无线多跳联网所带来的便 利，还有许多问题需要解决，比如高效的路由算法，媒体( 信道) 接入技 术，移动性管理，能量管理，安全以及这里将要讨论的q o s 路由等等。 由于无线多跳网络具有以上介绍的一些弱点，所以如何在无线多跳网 络中进行高效的q o s 路由就成为一个迫切需要解决的关键问题和研究的热 点。虽然在有线网络中已经提出了一些行之有效的方法，但都不能直接应 用在无线多跳网络中。 另一方面，多约束的q o s r 问题，特别是在无线多跳网络中的多约束的 q o s r 问题是一个尚待解决的n p 全问题。在传统的有线网络中，为解决该问 题，一些具有多项式或者伪多项式时间复杂度的启发式算法已经被提出来。 但是，大部分该类算法存在计算复杂度高、收敛时间过长、性能较差的情 况，因此并不适用于无线多跳网络。 1 3 自然计算领域相关进展 自然计算是指以自然界，特别是生物体的功能、特点和作用机理为基 础，研究其中所蕴含的丰富的信息处理机制，抽取出相应的计算模型，设 计出相应的算法并应用于各个领域。自然计算包含了进化计算、神经计算、 生态计算、量子计算和复杂白适应系统等在内的众多以自然界机理为算法 9 设计基础的研究领域，具有模仿自然界的特点，通常是一类具有自适应、 自组织、自学习能力的算法，能够解决传统计算方法难于解决的各种复杂 问题，在大规模复杂系统的最优化设计、优化控制、计算机网络安全、创 造性设计等领域具有很好的用途。从学科发展的角度来看，自然计算的研 究是各类自然科学( 特别是生命科学) 和计算机科学相交叉而产生的研究 领域，它的发展完全顺应于当前多交叉学科不断产生和发展的潮流，这些 研究领域均为国际前沿研究领域，对促进国家国民经济的发展和科学技术 的进步均具有十分重要的意义。 群集智能是一种新的方法，被用来解决分布式的问题。该方法起源于 生物界。社会昆虫和群集脊椎动物( 比如蚂蚁，白蚁，黄蜂等) 在生活中 需要解决许多问题，比如需要发现新的食物源，成员之间需要进行工作分 工，需要构造复杂的巢穴，需要进行成千上万英里的迁徙，需要对等地在 一个狭小空间里运动，以及需要适应随时变化的状况。典型的群集智能系 统由一群简单的主体构成，每个主体和其它主体以及它们的环境作局部的 交互。尽管通常没有一套集中的控制机制来指示这些主体如何协作，但这 些简单的局部交互行为通常能涌现出复杂的全局行为，而且看起来整个系 统的能力要比单个个体的能力要强。 群集智能中有许多问题，比如自组织，分布式，并行以及相对简单的 个体之间本地通信机制的利用等等都有待研究。我们受蚁群的启发，应用 群集智能于无线a dh o c 网络的路由研究中，以提高无线a dh o c 网络的性能。 模拟退火是m o n t ec a r l o 演算方法的推广，被用来检验”体系统的状态和 冷却状态方程【9 】，其概念是建立在退火过程中液体凝固或者金属结晶的方 式之上的。在退火过程中，熔化物被初始化一个很高的温度，并且被打乱 序列，然后慢慢冷却以使得系统在任何时刻均近似于热动力学平衡状态。 随着降温的进行，系统内的分子序列更加有序，最后达至u t - - o 的基态。整 个过程可以认为是绝热趋近于最低能量状态。如果系统的初始温度不高， 或者冷却过程不是足够的慢，那么系统可能变成淬火或者变成亚稳态。 根据m e t r o p o l i s 准则，系统在能量e 和温度t 下处于一个初始化状态，保 持t 不变，初始构形被扰动，随后计算b e 。如果内能的改变量为负，则新 1 0 得到的构形被采用，如果内能的改变量为正，则系统以由b o l t z m a n n 因子e x p ( a e r r ) 给出的概率接收新的构形。这个过程要重复足够多的次数以得到当 前温度下较好的取样统计，然后温度缓慢下降，重复刚才过程，直到系统 达n t = 0 。 通过类推，m o n t ec a r l o 方法可以直接运用到组合问题中 1 0 1 1 1 1 。热动 力系统的当前状态与组合问题的当前解类似，热动力系统的能量方程与目 标函数类似，系统的基态与全局最小值类似。算法应用的主要困难之处在 于这里没有明显的与温度t 相类比的组合问题自由参数，而且局部最小值的 避免是建立在退火进度表，初始温度的选择，每个温度的迭代次数以及退 火过程中温度的下降值之上的。 均场退火，采用鞍点近似和利用一组确定性方程来代替s a 中的随机过 程，给出了另一种解决组合优化问题的新方法。 鱼1 1 1 曼 1 2 具有这样的特点，即在其焦点处所捕获的图像具有很高的像 素，而离焦点越远的地方，图像像素越低。当运用在路由当中时，该方法 转变成维护精确的关于邻居结点的距离和状态信息，当距该结点越远，这 些信息就越不精确。 1 4 本文的贡献 我们将这些方法应用到无线多跳网络的q o s 路由研究当中。 以下是我们所作的一些工作： 1 、a dh o e 网络中基于蚁群的路由协议已经被广泛地研究，但其中的大 部分本质上都属于单径路由协议，使得源宿之间最短路由上的结点负担加 重。另一方面，由于引入了蚂蚁的正反馈机制，使得协议本身比较差的鲁棒 性受到进一步的削弱。多径路由能够更好地支持q o s 。我们将群集智能和链 路不相交的多径路由结合起来以解决上述问题。新提出的基于蚁群的多径 q o s 路由方法建立和利用多条链路不相交路由来并发发送数据，并且采用 信息素来分散通信流量，因此能够适应网络的动态变化和更好的支持q o s 。 仿真结果表明该方法要优于其他相关的算法。 2 、多重约束的q o s 寻路，其目的是为了找出同时满足多重约束条件的 可行路由，在网络拓扑结构动态改变的移动自组网中更是一个具有挑战性 的课题。该问题已经被证明是n p 全问题。对此，人们提出了多项式时间和伪 多项式时间启发式算法。但这些算法都是针对有线网提出来的，计算复杂度 高或者性能差，并不适合无线移动自组网。本文针对该问题提出了一种新的 基于模拟退火的q o s 路由算法( s ar a ) 。该方法首先运用能量函数，把多 个q o s 权转换成一个新的复合度量，然后通过模拟退火找到可行的路由。文 中首先概述了模拟退火算法的基本原理，然后分析了在移动自组网中运用 模拟退火算法来进行q o s 选路时所遇到的问题。理论分析和试验结果表明所 提出的新算法相对于相关算法具有较好的性能，是一个有效的算法，能在 多项式时间内找到全局( 近似) 最优解。 3 、多约束最优路由选择作为一个n p 全问题，在无线网状网中也是个 重大