（计算机软件与理论专业论文）基于复杂理论的mososo系统中路由关键问题研究.pdf

山东帅范人学硕i ：学位论义 基于复杂理论的m o s o s o 系统中路由关键问题研究 摘要 信息技术是一个快速更新和迅猛发展的领域，新技术和新思想层出不穷，系 统模式和系统架构日新月异，项目管理、软件工程和系统开发设计方法等也都不 断地推陈出新。随着互联网的兴起，知识生产全球化，信息技术的发展呈现出“自 催化”加速发展的念势。信息系统的复杂度与信息技术的发展密切相关，随着各 种技术的进步发展，信息系统不断地由低级到高级、由简单到复杂、由封闭孤立 到丌放协同地发展。 近年来，大量社会性软件拓展到移动平台，成为移动社会性软件，一些国际 知名i t 企业的研究中心在研究和设计一般社会性软件系统时开始应用一些系统 研究方法。如m i c r o s o f t 的复杂网络计算小组，结合网络虚拟社群、即时通讯交 流软件，研究社会关系网络的演化动力学；i b m 研究中心的协同用户体验设计 小组，研究多用户系统中的非线性协作问题、社会关系网络分析在知识管理中的 应用等；y a h o o 的激励网络( i n c e n t i v en e t w o r k ) 项目，研究社会网络中用户的 激励因素与复杂网络拓扑中的信息检索间的关系，等等。然而，这些机构的研究 多是针对一个具体的项目、关注某一个具体的方面、孤立地应用某一种系统理论 和方法解决一个具体的问题，并没有从整体上把社会性软件系统作为一个复杂系 统，更没有考虑移动性对社会网络演化的影响。 为了解决以上问题，本文在现有理论及研究的基础上，针对越来越复杂多样 化的社会性软件拓展到移动平台，和r 趋复杂的w e b 信息系统构建的互联网，在 信息系统的研究中全面引入系统科学和复杂性研究的相关理论和方法，把系统思 维、系统理论和系统方法与信息系统的思考、分析与架构设计结合起来，对典型 的移动社会型软件进行分析，给出移动社会性软件的定义。 移动社会性软件系统中需要研究的内容很多，例如移动社会性软件系统建 模，聚类和迁移算法设计，定位服务的研究，在软件工程方法和建模语言方面的 研究，研究个性化算法的优化设计。 本文的主要工作集中在以下几个方面： 第一，给出移动社会性软件的定义。对典型的移动社会性软件系统的系统特 征，拓扑结构的生成和演化及系统内各组分之间的动态作用机制进行分析，总结 出已有的移动社会性软件的特征，引入复杂系统理论，给出虽然并非全面、但符 合本研究语境的移动社会性软件的定义。 第二，提出一种基于复杂理论下的移动社会性软件系统模型。在了解移动社 山东师范人学硕：i ：学位论义 会性软件的本质的基础上，根据复杂系统理论，利用局域世界演化网络建模方法 构建移动社会性软件系统的模型，并对此进行特征分析。 第三，改进原有的一些迁移路由算法，给出一个适合移动社会性软件系统的 迁移路由算法。利用复杂网络的理论和现代优化算法，根据移动社会性软件系统 自己的特征，加入复杂系统的一些特征参数，改进原有的一些迁移路由算法，使 其符合移动社会性软件的需求。 最后，本文选择一个具体的移动社会性软件系统，并统计其复杂特性，然后 以这个具体的软件系统模型作为试验环境，对算法进行仿真试验。 关键词：移动社会性软件，迁移路由，蚁群算法，移动a g e n t ，复杂网络 中图分类号：t p 3 0 1 山东师池人学颂i ：学位论文 t h er e s e a r c ho fr o u t i n gk e yp r o b l e mf o rm o b i l es o c i a ls o f t w a r e s y s t e mb a s e do nc o m p l e xn e t w o r k st h e o r y a b s t r a c t i n f o r m a t i o nt e c h n o l o g yf i e l di saf a s t - u p d a t ea n dt h er a p i dd e v e l o p m e n tf i e l d ， w h i c hn e wt e c h n o l o g i e sa n dn e wi d e a se m e r g ei ne n d l e s s l y , t h es y s t e mm o d e la n dt h e s y s t e ma r c h i t e c t u r ec h a n g eq u i c k l y , p r o j e c tm a n a g e m e n t ，s o f t w a r ee n g i n e e r i n ga n d s y s t e m sd e v e l o p m e n ta n dd e s i g nm e t h o d sa r eg e tr i do ft h es t a l ea n db r i n gf o r t ht h e f r e s h w i t ht h er i s eo ft h ei n t e r n e t ，t h eg l o b a l i z a t i o no fk n o w l e d g e ，t h ed e v e l o p m e n t o fi n f o r m a t i o nt e c h n o l o g yt a k eo na n ”a u t o c a t a l y t i c ”s p e e du ps i t u a t i o n t h e c o m p l e x i t yo fi n f o r m a t i o ns y s t e m sa n dt h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y a r e c l o s e l y r e l a t e dw i t h e a c h o t h e r , w i t ht h ed e v e l o p m e n to ft e c h n o l o g i c a l ， i n f o r m a t i o ns y s t e m sc o n t i n u a l l yd e v e l o p m e n tf r o ml o w l e v e lt oa d v a n c e d ，f r o m s i m p l et oc o m p l e x ，f r o mi s o l a t e dt oc o l l a b o r a t i v e i nr e c e n ty e a r s ，ag r e a td e a lo fs o c i a ls o f t w a r ee x p a n d st ot h em o b i l ep l a t f o r m ， w h i c ht u r n si n t om o b i l es o c i a ls o f t w a r e an u m b e ro fi n t e r n a t i o n a l l yr e n o w n e di t c o m p a n i e sb e g i nt oa p p l yan u m b e ro fs y s t e m sr e s e a r c hm e t h o d sa tt h er e s e a r c ha n d d e s i g no fg e n e r a ls o c i a ls o f t w a r es y s t e m s s u c ha sm i c r o s o f tc o m p l e x i t yn e t w o r k c o m p u t i n gg r o u p ，c o m m u n i t yc o m b i n e d 、v i t hv i r t u a ln e t w o r k s ，s o f t w a r eo fr e a l - t i m e c o m m u n i c a t i o n ，d y n a m i c s t h a t s t u d y t h ee v o l u t i o no fs o c i a l n e t w o r k ；t h e c o l l a b o r a t i v eu s e re x p e r i e n c ed e s i g ng r o u po fi b mr e s e a r c hc e n t e r , w h i c hr e s e a r c h t h en o n - l i n e a rc o l l a b o r a t i o np r o b l e mo fm u l t i - u s e rs y s t e m ，a p p l i c a t i o n so ft h ea n a l y s i s o fs o c i a ln e t w o r ki nk n o w l e d g em a n a g e m e n t ；t h ep r o j e c to fy a h o oi n c e n t i v en e t w o r k ， w h i c hs t u d yt h er e l a t i o n s h i p sb e t w e e nu s e r si n c e n t i v ef a c t o ra n di n f o r m a t i o ns e a r c h e s i nc o m p l e xn e t w o r k st o p o l o g yo fs o c i a ln e t w o r k s ，a n ds oo n h o w e v e r m a n ys t u d i e s o ft h e s ei n s t i t u t i o na r ef o ras p e c i f i cp r o j e c t ，p a ya t t e n t i o nt oac e r t a i na s p e c t s ，a n d a p p l yc e r t a i nk i n do fs y s t e mt h e o r ya n dm e t h o d st os o l v eas p e c i f i cp r o b l e m ，a n dn o t o n l yd i dn o tr e g a r dt h es o c i a ls o f t w a r es y s t e ma sac o m p l e xs y s t e m ，b u ta l s od i dn o t c o n s i d e ri n f e c t i o no fm o b i l i t yf o rt h ee v o l u t i o no fs o c i a ln e t w o r k s t os o l v et h i sp r o b l e m ，i nt h i sp a p e r , o nt h eb a s i so ft h ee x i s t i n gt h e o r ya n d r e s e a r c h ，a n dt h ep h e n o m e n ao fm o r ea n dm o r ev a r i o u ss o c i a ls o f t w a r ee x p a n dt o m o b i l ep l a t f o r ma n dt h ec o m p l i c a t e dw e bi n f o r m a t i o ns y s t e m s ，w ei n t r o d u c et h e t h e o r ya n dm e t h o d so fs y s t e m i cs c i e n c ea n dc o m p l e x i t yr e s e a r c ht oi n f o r m a t i o n s y s t e m ss t u d y ,a n dc o m b i n es y s t e m i ct h o u g h t s ，s y s t e m i ct h e o r ya n ds y s t e m i c 山东师范人学硕i ：学位论文 a p p r o a c hw i t ha n a l y s i sa n da r c h i t e c t u r ed e s i g no fi n f o r m a t i o ns y s t e m b a s eo nt h e a b o v et h e o r y , w ea n a l y s et h et y p i c a lm o b i l es o c i a ls o f t w a r e ，a n dg i v et h ed e f i n i t i o no f m o b i l es o c i a l i t ys o f t w a r e t h e r ea r em o r ea s p e c t si nm o b i l es o c i a ls o f t w a r es y s t e mr e q u i r e dt os t u d y , s u c h a sc o n s t r u c t i n gt h em o d e lo fm o b i l es o c i a ls o f t w a r es y s t e m s ，d e s i g n i n gc l u s t e r i n ga n d t r a n s f e ra l g o r i t h m ，r e s e a r c h i n gl o c a t i o n - b a s e ds e r v i c e s ，s t u d y i n gs o f t w a r ee n g i n e e r i n g m e t h o d sa n dm o d e l i n gl a n g u a g e ，a n dd e s i g n i n gp e r s o n a l i z e do p t i m i z a t i o na l g o r i t h m t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ： f i r s t ，t h i sp a p e rg i v e st h ed e f i n i t i o no fm o b i l es o c i a ls o f t w a r e a n a l y z i n gt h e f o r m a t i o na n de v o l u t i o no ft o p o l o g ys t r u c t u r ea n dd y n a m i cm e c h a n i s mb e t w e e n s y s t e mc o m p o n e n t so ft y p i c a lm o b i l es o c i a ls o f t w a r es y s t e m s u m m e du pt h e c h a r a c t e r i s t i c so fe x i s t i n gm o b i l es o c i a ls o f t w a r e ，t h e ni n t r o d u c i n gt h ec o m p l e x s y s t e m st h e o r y , a n dg i v et h ed e f i n i t i o no fm o b i l es o c i a ls o f t w a r ew h i c hc o n s i s t e n t w i t ht h ec o n t e x to ft h i ss t u d y , b u tn o tc o m p r e h e n s i v e s e c o n d ，t h i sp a p e rb r i n g sam o b i l es o c i a ls o f t w a r es y s t e mm o d e lt h a tb a s e do n t h ec o m p l e xt h e o r y o nt h eb a s i so fu n d e r s t a n d i n gt h en a t u r eo fm o b i l es o c i a l s o f t w a r ea n dt h ec o m p l e xs y s t e m st h e o r y , u s i n gt h em o d e l i n gm e t h o do fl o c a l - w o r l d e v o l v i n gn e t w o r k ，t ob u i l dt h em o d e lo fm o b i l es o c i a ls o f t w a r es y s t e ma n da n a l y s e t h ef e a t u r eo ft h i sm o d e l t h i r d ，i m p r o v es o m eo r i g i n a lt r a n s f e rr o u t i n ga l g o r i t h m ，a n dg i v eat r a n s f e r r o u t i n ga l g o r i t h mt h a ts u i t a b l ef o rm o b i l es o c i a ls o f t w a r es y s t e m u s i n gc o m p l e x n e t w o r kt h e o r ya n dm o d e mo p t i m i z a t i o na l g o r i t h m s ，b a s e do nt h ef e a t u r e so fm o b i l e s o c i a ls o f t w a r es y s t e mo fi t so w n ，a n da d d i n gt h ec h a r a c t e r i s t i cp a r a m e t e r so f c o m p l e xs y s t e m ，t oi m p r o v es o m eo ft h eo r i g i n a lt r a n s f e rr o u t i n ga l g o r i t h mt h a t a c c o r dw i t ht h ed e m a n do fm o b i l es o c i a ls o f t w a r es y s t e m f i n a l l y , t h i sp a p e rs e l e c tas p e c i f i cm o b i l es o c i a ls o f t w a r es y s t e m s ，a n ds t a t i s t i c i t sc o m p l e xc h a r a c t e r i s t i c s ，a f t e r w a r d ，w eu s et h i ss p e c i f i cs y s t e m sm o d e l 硒at e s t e n v i r o n m e n tf o ra l g o r i t h ms i m u l a t i o n k e y w o r d ：m o b i l es o c i a ls o f t w a r e ；t r a n s f e rr o u t e r ；a n tc o l o n ya l g o r i t h m ；m o b i l e a g e n t ；c o m p l e xn e t w o r k s c l a s s i f i c a t i o n ：t p 3 0 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 导师签字：朝矽 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：嘏 导师签字： 签字日期：加7 年f 月r 81 7签- 7 日期：孔坳p 年j 一碉脚 ， 山东帅- 7 i u t - 人学硕i ：学位论文 1 1 研究背景 第一章绪论 随着信息技术的快速发展，信息系统也逐渐由低级到高级、由简单到复杂、由封闭孤 立到开放协同地发展：具体表现为系统组分的独立性越来越强、组分之间的耦合度越来越 低、组分之间组合交互的灵活度越来越高，信息系统也因此越来越具有复杂性系统的特征。 信息系统的复杂性在近年来兴起的社会性软件和w e b 2 0 中表现得尤其突出。 近年来大量社会性软件拓展到移动平台，成为移动社会性软件，移动社会性软件 ( m o b i l es o c i a ls o f t w a r e ，m o s o s o ) 是指通过无线通信网络和移动设备提供服务的软件系 统【，在使用过程中或能促进集体协作行为的形成，或能促进用户社会关系网络的创建与 发展，让系统内的信息组织与用户构成的社会组织一起按照社会原则同步进化。m o s o s o 是目前计算机科学、自动化科学、管理科学、数学、物理学等多学科领域关注与研究的新 兴热点问题之一【2 j 。 以前软件系统大多为基于c s 结构【3 】，是端到端封闭的体系结构，必须使用特定的客 户端。系统容易导致性能瓶颈和单点失败，因此在可扩展性、共享性、故障容错、可用性 等方面存在许多局限。 随着i n t e r n e t 技术的普及和发展，基于w e b 的b s 体系的软件系统受到业界重视【4 】。 客户端采用标准浏览器如i e 等，服务器端是为软件系统提供运行环境的w e b 应用服务器 以及关联的数据库服务器，利用w 曲页面驱动系统，具有客户端界面一致、简单易用、 支持异地办公等优点，既简化了客户端软件设计，也为软件系统带来了良好的可分布性。 虽然打破了对客户端的限制，但服务器端的集中控制体系仍然没有开放，功能或规模的扩 展依然受限制。 p 2 p 体系结构则把系统从集中控制的服务体系中解放出来，打破了服务器专有、专属 的限制，成为开放式分布的体系，所有的组成节点都可以是对等的，任何节点都可以自由 地加入和退出。传统的p 2 p 体系依赖于特定的协议和特定的服务类别，系统虽然是开放 的，但集成的节点依然限制为同质( h o m o g e n e o u s ) 的。 多智能主体系统m a s ( m u l t i 。a g e n ts y s t e m ) 通过智能主体间交互协议语言的标准化、 面向服务的架构s o a 通过w e b s e r v i c e s 间互操作标准的制订打破了这个限制【5 】，使开放 的异质节点( h e t e r o g e n e o u s ) 的集成体系成为可能。软件重用性较高，接口标准化，但系 统并非开放，w e b 服务的实现和升级控制在原开发者手中，由系统架构师或系统集成师 负责集成。 移动社会性软件比一般的社会性软件具有更灵活的主题参与式架构、动态的社会关系 网络、复杂的非线性协作机制、多层次的反馈循环机制和开放的系统问交互等，还要把人 山东师范人学硕f ：学位论文 的行为设计、社会关系、组织设计和人群协作机制、资源网络动力学演化机制纳入到系统 之内，而且还要解决移动网络环境下的新问题，如网络自主性、网络拓扑结构动态性、设 备能量有限、安全性的威胁等。 总之，移动社会性软件系统就是软件系统不断开放，不断社会化的产物，接口不仅标 准化且开放，与底层实现无关，系统具有生态多样性，功能细分为用户视角中的一个独立 任务，最终用户的操作行为决定其相互之间的操作与组合方式。由于采用了主体参与式架 构，更加具有自主性的“人件 【6 】引入系统，使系统发展成为社会技术混合系统，从 而具有了社会系统的复杂性。 1 2 国内外研究现现状 1 2 1 移动社会性软件研究进展 当今，移动社会性软件系统大量涌现【_ 丌，国外对移动社会性软件的研究主要是构建一 些针对特定应用场合的原型移动社会性软件系统，对现有移动社会性软件系统的分析和比 较，提出一些综合理论。文献 8 】给出一中移动社会性软件移动博客( m o b i l eb l o g s ， m o b l o g s ) 给用户提供了一种通过移动设备实现人人都能“自由叙事，随意表达的平台。 文献 9 中介绍了移动学习，即m 1 e a r n i n g ( m o b i l el e a r n i n g ) 的特性，支持用户在任何 时问、任何地点共享知识和协同学习；文献 7 归纳总结了很多人在m 1 e a r n i n g 领域移动 社会性软件系统的工作，提出一个移动社会性软件系统的参考模型。文献 1 0 】中y a o j c h a n g 从技术角度提出了一种移动社会网络服务系统的体系结构，该体系结构包括四个主 要组成部分：客户端设备、无线接入网络、互联网以及为系统提供数据库服务和应用服务 的服务器端。 国内针对社会性软件的研究刚刚起步，对移动社会性软件系统的研究却是一个崭新的 领域，研究并不多。文献 1 1 】从w e b 2 0 产生背景、概念形成、典型的技术和应用这些方 面作了描述，但是这篇论文没把复杂性系统研究的方法应用到w e b 2 0 的分析中。文献 1 2 】 在对信息系统的研究中全面引入系统科学和复杂性研究的相关理论和方法，但是在对多主 体建模方法的逻辑和原理的分析上没有作深入地描述，也没有考虑社会性软件的移动因 素。 另外，一些国际知名i t 企业的研究中心在研究和设计一般社会性软件系统时开始应 用一些系统研究方法【”】。如m i c r o s o i t 的复杂网络计算小组，结合网络虚拟社群、即时通 讯交流软件，研究社会关系网络的演化动力学；i b m 研究中心的协同用户体验设计小组， 研究多用户系统中的非线性协作问题、社会关系网络分析在知识管理中的应用等；y a h o o 的激励网络( i n c e n t i v en e t w o r k ) 项目，研究社会网络中用户的激励因素与复杂网络拓扑 中的信息检索间的关系，等等。然而，这些机构的研究多是针对一个具体的项目、关注某 一个具体的方面、孤立地应用某一种系统理论和方法解决一个具体的问题，并没有从整体 2 山东帅范人学砂ji ：学位论义 上把社会性软件系统作为一个复杂系统，更没有考虑移动性对社会网络演化的影响。 1 2 2 迁移路由算法的研究现状 路由的概念出现于本世纪7 0 年代，而路由技术的广泛应用是在8 0 年代，大规模的网 络结构出现以后。目前有很多路由算法，这些路由算法各有所长，但是因为在设计路由选 择算法时考虑的因素不同，所以不存在一种绝对的最佳路由算法，最佳只能是相对于某一 种特定要求下得出的较为合理地选择。路由动作包括了两项基本的内容即寻径和转发。本 文重点研究迁移路由算法。 m o i z u m l 在其博士论文 1 4 1 定义并研究了旅行a g e n t 问题，并从理论上证明了旅行 a g e n t 问题为n p 完全问题，其时间、空间复杂度极高。 文献 1 5 】中提出了局部位置最近优先( l c f ) 和全局最临近优先( g c f ) 两种使移动 a g e n t 迁移路线最优化启发式算法，但是这两种算法，随着网络规模的增长和传感器分类 的增加变得复杂化。文献【1 6 】中引入了遗传算法来解决上述问题，这种算法性能比局部位 置最近优先和全局最临近优先两种算法优越，但是时间复杂性高。 在文献 1 5 和 1 6 中忽略了节点自身的能量水平，因此文献【1 7 提出的多目标移动代理 路由，加上节点的能量水平，并在一定程度减少不必要的能源消耗，但它的计算过程非常 复杂，执行速度慢。文献 1 8 】提出了基于a g e n t 的能源意识路由算法，该文中有两种代理： 一个是固定a g e n t ，另一种是移动a g e n t ，考虑到节点的能量水平，以寻找合适的路线。 文献 1 9 】中结合了传感器节点能量来规划路由，充分考虑数据传输和数据融合的能 源，并提出了移动代理树路线数掘融合算法。该算法结合移动代理代码的多少和收集的数 据，考虑数据融合能源和传输能源，调整和适应移动代理数量和数据融合的时间，不仅降 低了能源消费，而且也增加了网络效率。 文献 2 0 】中将蚁群算法与遗传算法结合起来，进一步研究了旅行a g e n t 问题，但其算 法复杂度高，算法效率也有待进一步提高。文献 2 1 1 中用蚁群算法与q 学习算法相结合的 方法，提出了一种新颖的路由算法，但是，他们都没有应用复杂适应系统理论和方法。 文献 2 2 中采用复杂适应系统理论和方法分析路由算法中的悖论以及由此引起的后 效问题，但是，他只是说明复杂适应系统理论和方法在解决复杂网络系统的路由后效问题 上具有的潜力和推动作用，并没有深入分析后效作用问题和构造完善的估计预测路由算 法。 随着网络系统规模的扩大，系统的复杂性明显的提高，系统内部之间的协调控制 的重要性越来越突出。上述这些迁移路由算法的改进在其特定要求下得出了较为合理地选 择，但并不适合移动社会型软件系统中迁移路由的选择，因为没有考虑复杂移动社会性软 件系统中的关键因素。目前基于复杂系统理论迁移路由算法，或者将路由问题应用到复杂 网络中的研究比较少。本文针对以上几个方面的不足，做了进一步的研究。 山东师范人学硕一i ：学位论文 1 3 本文的研究内容 本研究的主要目的是，针对越来越复杂多样化的社会性软件拓展到移动平台，和同趋 复杂的w e b 信息系统构建的互联网，在信息系统的研究中全面引入系统科学和复杂性研 究的相关理论和方法，把系统思维、系统理论和系统方法与信息系统的思考、分析与架构 设计结合起来，对典型的移动社会型软件进行分析，在此基础上，基于移动智能主体构建 复杂移动社会性相应的动态模型，找到相对于这一种特定要求下得较为合理地迁移路由算 法。 本文的主要研究内容集中在以下几个方面： 第一，给出移动社会性软件的定义。对典型的移动社会性软件系统的系统特征，拓扑 结构的生成和演化及系统内各组分之间的动态作用机制进行分析，总结出已有的移动社会 性软件的特征，引入复杂系统理论，给出虽然并非全面、但符合本研究语境的移动社会性 软件的定义。 第二，提出一种基于复杂理论下的移动社会性软件系统模型。在了解移动社会性软件 的本质的基础上，根据复杂系统理论，利用局域世界演化网络建模方法构建移动社会性软 件系统的模型，并对此进行特征分析。 第三，改进原有的一些迁移路由算法，给出一个适合移动社会性软件系统的迁移路由 算法。利用复杂网络的理论和现代优化算法，根据移动社会性软件系统的自己的特征，加 入复杂系统的一些特征参数，改进原有的一些迁移路由算法，使其符合移动社会性软件的 需求。 第四，验证并仿真。本文选择一个具体的移动社会性软件系统，并统计其复杂特性， 然后以这个具体的软件系统模型作为试验环境，对算法进行仿真试验。 1 4 全文结构及主要研究内容梗概 本文的内容结构章节安排如下： 第一章为绪论。主要阐述了论文研究的背景、国内外移动社会性软件及迁移路由算法 的研究现状，以及本文的主要工作及内容组织结构。 第二章为研究基础。主要介绍了复杂理论、移动p 2 p 技术、移动a g e n t 技术、蚁群 算法等各自的概念和特点和路由算法的原理及分类，本文重点是在研究路由中的路径选 择。 第三章为移动社会性软件模型的提出。首先分析了现有典型的几类移动社会性软件， 然后根据社会性软件的特征，给出虽然并非全面、但符合本研究语境的移动社会性软件的 定义，移动社会性软件系统中的研究内容及主要问题，最后提出一种基于复杂理论下的移 动社会性软件系统模型的构造算法，并给出一个典型的系统的模型。 第四章为移动社会性软件系统模型中迁移路由算法的。提出一种基于复杂理论下的移 4 山东! j f i 地人学倾i ：学位论义 动社会性软件系统模型中迁移路由算法。利用复杂网络的理论和现代优化算法，根据移动 社会性软件系统的自己的特征，加入复杂系统的一些特征参数，改进原有的一些迁移路由 算法，使其符合移动社会性软件的需求。 第五章为试验背景的验证和算法的仿真。统计分析试验背景的复杂特性，然后在这个 背景下对改进的算法进行仿真分析。 第六章总结和展望。总结本文所作的工作，并指出下一步的研究方向。 5 山东师范人学硕i j 学位论文 2 1 复杂理论简介 第二章系统相关理论及技术 网络作为一门科学，公认的看法是从欧拉的图论学算起，第二个发展阶段开始于2 0 世 纪，由两位匈牙利数学家e r d 6 s 和r o n y i 建立的随机图理论，被公认为是数学上开创了复杂 网络理论的系统性研究，第三个阶段的进展是近年来在统计物理中出现的小世界网络和无 标度网络的研究i z 引。 复杂网络的研究是复杂理论研究的一部分，它的研究邻域已遍布多个学科邻域，如物 理学、生物学、经济学、计算机通信等。其结构复杂性、时空复杂性和动力学行为特性研 究是当今各个邻域科学家们所探讨的热点问题。复杂网络是大量真实复杂系统的抽象，它 能够刻画复杂系统内部的各种相互作用或关系。 2 1 1 复杂网络的特征度量 1 、平均路径长度( a v e r a g ep a t hl e n g t h ) 网络中任意两点之间的距离定义为连接两点的最短路径上的边数，网络中任意连个节 点之间的距离的最大值成为网络的直径，记为d 。网络的平均路径长度l 定义为任意两点之 间的距离的平均值。 2 、度与度分布( d e g r e e & d e g r e ed i s t r i b u t i o n ) 节点度是单个节点的属性中重要的概念，指的是与该点所连接的边数，度分布则表示 节点度的概率分布函数p ( 后) ，它指的是节点有k 条边连接的概率。度是描述网络局部特性 的基本参数；度分布函数则反映了网络系统的宏观统计特征。 3 、聚类系数( 或称集群系数，c l u s t e r i n gc o e f f i c i e n t ) 节点的聚类系数被定义为它所有相邻节点之间的实际连接数目占可能的最大连接边数 目的比例，网络的聚类系数c 则是所有节点簇系数的平均值。 4 、介数( d e t w e e n n e s s ) 节点的介数定义为【2 4 】网络中经过该点的最短路径的数目，反映了节点的影响力，各种 交通枢纽都是介数较大的节点，类似地，可以定义边的介数【2 5 1 ，即经过该边的最短路径的 数目，它反映了边的影响力，这对于在现实网络中发现和保护关键资源具有重要意义。 2 1 2 复杂网络拓扑基本模型及其性质 1 、规则网络 7 m 东师人掌联l 。学位论文 舰则网络是最简单的网络模型其特点足每个节点的近邻数目都相同如一维链、一 维晶格、完全图等。用的蛙多的是擐邻近耦台网络。规则网络具有较人的聚类系数和平均 路径长度。 2 、随机网络 与完全规则网络相反的是完全随机网络，其中一个典型的网络模型是e r d 6 s 和r 6 n 啊提 出的e r 随机图模型l 2 6 1 。e r d 6 s 和r 白i 一的奄要发现是e r 随机图具有涌现或相变性质。e r 随机 图的节点度服从泊松分布，它县有较小的平均路径长度和较小的聚类系数。 3 、小世界网络 实证研究表明许多现实网络大都表现出集群现象，由此引发人们对小世界网络的研 究，作为从完全规则州络向完全随机网络的过渡。w a t t s 和s 廿0 9 t z 于1 9 9 8 年引入了小世界网 络模型【卸，称为w s 小 廿界模型。w s d 、世界模型的构造是从规则图开始，以概率口随机化 重新连接网络中的每个边。小世界网络的节点度分服从指数分布，可以同时拥有较大的聚 类系数和较小的平均路径长度，这就是小世界特性。 号2 l8 7 t 寥 0 i j 孓! ，8，爵“” + i 1 务 ： 番 章导赣茹矿 4 、b a 无标度网络 e r 随机图和w s 小世界模型的度分布与许多现实网络都不相符，用它们来描述现实网 络具有很大的局限性，为了更好的描述现实网络，b a r a b a s i 和a l b e r t 考虑实际网络地增长特 性( g r o w t h ) 和优先连接( p r e f e r e n t i a la t t a c h m e n t ) 特性，提出了一个无标度网络模型，称 为b a 模型口”。b a 无标度模型节点的度服从幂率分布，具有较小的聚类系数和平均路径长 度。无标度模型对随机故障表现出良好的鲁棒性，但对蓄意攻击，就显得比较脆弱，这 都源于其存在集散节点。无标度网络的些理论可以用于预防交通堵塞。 图2 - 2 无标度璃绍拓扑结构幽 8 山东师范人学硕i j 学位论文 2 2 移动p 2 p 技术 移动p 2 p 具有重要的研究价值，其涉及理论比较广。由于移动p 2 p 是p 2 p 应用分支， 本小节首先介绍p 2 p 技术，随后对移动p 2 p 定义特点进行简单介绍，本文中移动社会性 软件的网络体系结构也是移动p 2 p 。 2 2 1p 2 p 技术 i n t e l 将p 2 p 定义为“通过系统间的直接交换所达成的计算机资源与信息的共享，这些资 源与服务包括信息交换、处理器时钟、缓存和磁盘空间等。 r o k u t e c h n o l o g i e s 公司将p 2 p 定义成“使个人与个人之间直接通信成为可能且更便捷的网络结构”。i b m 则给p 2 p 赋予更 广阔的定义，把它看成是由若干互联协作的计算机构成的系统并具备若干特性。电话以及 网上聊天系统是典型的p 2 p 通信系统【2 9 1 。 与其它网络结构相比较，p 2 p 具有非中心化、可扩展性较好、健壮性、较高的性价比、 隐私保护、负载均衡等特点，这些特点也是一些移动设备( 例如手机) 上信息服务选择p 2 p 的原因之一。 p 2 p 自1 9 9 9 年n a p s t e r 推出后迅速普及，自此之后，越来越多p 2 p 软件的发布和应用，一 步步验证了对等计算思想的成功，如g n u t e l l a 、f r e e n e t 、b i t t o r r e n t 、k a z a a 、s k y p e 等等。 互联网环境中对等计算应用已经超过w e b 应用，成为占用互联网带宽最多的网络应用。 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，结点之间的 拓扑结构一直是确定系统类型的重要依据。目前对p 2 p 网络模型没有统一区分定义，但根据 拓扑结构的关系可以将p 2 p 研究分为4 种形式：集中式拓扑，全分布式非结构化拓扑，全分 布式结构化拓扑( 也称作d h t 网络) 和混合式拓扑。这几种模型也代表了p 2 p 的发展过程。 四种结构的比较如表2 1 所示： 表2 1 各种网络结构特点比较 2 2 2 移动p 2 p 1 移动对等网络的定义及特征 移动对等网络又称移动p 2 p 网络( m o b i l ep e e r - t o - p e e rn e t w o r k ，简称m p 2 p ) ，为叠加 9 山东师范人学硕l ：学位论文 在移动网络环境中网络层之上的会话层覆盖网络，能够利用多种带宽和服务质量的底层接 入技术，其主要目的是以直接交换的方式来实现可移动终端设备之问数据资源的共享与服 务的协同。 移动p 2 p 不同于传统p 2 p 应用，其应用与无线网络，使用手或其他移动设备作为主 要节点，其具有以下特点【3 0 】： ( 1 ) 移动设备的限制。 手机存储空间较小。在移动系统中，终端节点由p d a ，手机，p o c k e tp c 等移动手机 设备来充当，数据存储空间受到严格的限制。 可用内存较小。虽然移动设备内存在不断增加，但是它的大小仍然远小于p c 。因此， 移动占用内存资源应该尽可能地减少。 屏幕及键盘有限。移动终端显示屏幕限制其应用系统用户界面设计。同样在设计移 动终端应用必须考虑界面设计尽量简洁，用户输入方便。 电池容量有限。移动终端处理器要求越来越快，屏幕越来越大，那么将消耗更多的 电能。 c p u 频率较低。移动设备c p u 处理能力有限，而且它拥有较小的内存。所以在设计 m o b i l e 的时候需要减少运算复杂性。 ( 2 ) 高度动态性。 整个移动p 2 p 系统的网络拓扑结构动态变化性。移动p 2 p 系统基于移动网络，网络中 的节点通常是移动设备，这些设备具有很强的移动性。它们在网络中的位置一般会频繁发 生变化，系统中所有的节点都处于随机运动的状态，整个系统的拓扑结构呈现杂乱无章的 剧烈变化。 节点的加入和退出频繁和随机性。在移动p 2 p 系统中，节点因为开机、关机、