（模式识别与智能系统专业论文）多机器人网络中资源公平分配算法的研究.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n g u n i v e r s i t yo f t e c h n o l o g yf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n gs c i e n c e t h er e s e a r c ho ff a i rr e s o u r c e sa l l o c a t i o ni nt h e m u l t i r o b o tn e t w o r k m a s t e rc a n d i d a t e ：z h o uy i n g s u p e r v i s o r ：p r o f l i uz h i j u n e2 0 1 0 f a c u l t yo fa u t o m a t i o n g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u , g u a n g d o n g ，p r c h i n a , 510 0 9 0 摘要 摘要 随着科学技术的不断成熟，多机器人特别是智能机器人，如：移动机器人等， 在越来越多的场合被寄予了替代人类自动执行各种具有危险性任务的厚望。它将会 给人们的日常生活带来越来越重要的影响。 当前关于多机器人的研究主要包括有系统通信、编队、协作与控制以及冲突解 决等。本论文将无线传感器网络和有线网络共同引入多机器人的研究中，并从调整 多机器人网络内部资源分配的角度出发，提出了一种基于该网络的有关资源公平分 配的新方法，提高整体的响应速率。因此，在资源及其有限的多机器人网络中，设 计一种强抗干扰能力，网络化的，高服务质量的有关资源公平分配算法具有重大的 理论意义和现实意义。 本文针对多机器人网络的动态变化环境，进行了有关资源公平分配算法的研 究，主要内容和创新点如下： 1 、资源及其有限是多机器人网络面临的重大挑战。为了高效使用各机器人所携 带的有限资源，延长网络和系统的使用寿命，本论文研究了一种基于自适应控制的 有关资源公平分配算法，通过控制器对参考模型值的在线搜索并取其平均值来获取， 大大降低了其获取难度，提高其实用性。 2 、多机器人网络对实时性要求非常高。为了提高系统的响应速率，本文设计了 一种基于自适应模糊控制的有关资源公平分配算法，在自适应控制方法的基础上， 采用模糊控制方法对其增益控制参数实施控制并使之随系统动态变化，无需知道系 统各参数的精确特性和数值。在保证系统可行性和稳定性的条件下，将该参数由一 个常数变成一个可供选择的区间值，提高系统响应速率。 3 、在实时变换的多机器人网络中存在各种不确定性，如随机不确定性和非随机 不确定性因素等，这容易导致系统的不稳定。为了提高系统的鲁棒性，在模糊控制 方法的基础上，本文引入有关概率的相关知识，设计了一种新的控制方法，即概率 模糊控制方法来达到设计目的。概率模糊逻辑是由概率理论与模糊理论共存的联合 框架，该系统中主要包括主隶属函数和次概率分布函数。在保证系统可行性，稳定 广东工业大学硕士学位论文 性及响应速率的前提下，该方法使得系统的鲁棒性能更强。 4 、构建了基于多机器人网络的资源分配实验组，进行了有关资源公平分配实验。 完成的资源公平分配实验结果表明，本论文研究的基于自适应模糊控制的算法提高 了系统的响应速率，服务质量得到提高。 关键词：多机器人网络；资源公平分配；服务质量( q o s ) u a b s t r a c t a bs t r a c t w i t ht h em a t u r i n go ft e c h n o l o g y , m u l t i - r o b o te s p e c i a l l yi n t e l l i g e n tr o b o tl i k et h e m o b i l er o b o te t ca r ed e e p l yh o p e dt oa u t o m a t i c a l l ye x c u t ed i f f e r e n tk i n d so f d a n g e r o u s t a s k si nm o r ea n dm o r es i t u a t i o n s i tw i l lt a k em o r ea n dm o r ei m p o r t a n ti n f l u e n c et o p e o p l e so r d i n a r yl i f e t h es t u d yo fm u l t i - r o b o ta tp r e s e n ta r em a i n l yi n c l u d es y s t e mc o m m u n i c a t i o n ， f o r m a t i o n ，c o o p e r a t i o na n dc o n t r o l ，c o n f l i c tr e s o l u t i o ne t c t h ep a p e ri n t r o d u c e sw i r e l e s s s e n s o rn e t w o r ka n dw i r e dn e t w o r k t o g e t h e rt ot h es t u d yo fm u l t i r o b o t ，a n ds t a r tf r o mt h e a d ju s t m e n to fr e s o u r c ea l l o c a t i o ni nt h em u l t i - r o b o tn e t w o r k ，p r o p o s e san e wm e t h o d a b o u tr e s o u r c ef a i ra l l o c a t i o nb a s e do nt h en e t w o r k ，w h i c hh a si m p r o v e dt h eo v e r a l l r e s p o n s er a t e t h e r e f o r e ，i th a sg r e a tt h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a ls i g n i f i c a n c et o d e s i g nar e s o u r c e sf a i ra l l o c a t i o na l g o r i t h mi nm u l t i r o b o tn e t w o r k ，w h i c hi sv e r yl i m i t e d i nr e s o u r c e s t h i sa l g o r i t h mh a ss e r v e a lc h a r a c t e r i s t i c s ，s u c ha ss t r o n ga n t i - i n t e r f e r e n c e c a p a b i l i t y , n e t w o r k ，a n dh i g hq u a l i t yo f s e r v i c ee t c a c c o r d i n gt ot h ed y n a m i ce n v i r o n m e n ti nt h em u l t i r o b o tn e t w o r k ，t h i sp a p e rh a s d os e v e r a lr e s e a r c hi nr e s o u r c ef a i ra l l o c a t i o na l g o r i t h m ，t h em a i nc o n t e n ta n di n n o v a t i o n a r ea sf o l l o w s ： f i r s t ，o n eo ft h em a j o rc h a l l e n g e si nm u l t i r o b o tn e t w o r ki st h a tt h er e s o u r c ei sv e r y l i m i t e d t oe f f i c i e n t l yu s et h el i m i t e dr e s o u r c e sc a r r i e db ye a c hr o b o t ，t oe x t e n dt h el i f e o ft h en e t w o r ka n ds y s t e m s ，t h i st h e s i ss t u d ya na l g o r i t h ma b o u tr e s o u r c ef a i ra l l o c a t i o n a l g o r i t h mb a s e do nt h ea d a p t i v ec o n t r o lm e t h o d i tt h r o u g ht h eo n l i n es e a r c ht h er e f e r e n c m o d e lp a r a m e t e r st oo b t a i nt h e i ra v e r a g ev a l u e i tg r e a t l yr e d u c e st h ed i f f i c u l t yo fi t s a c q u i s i t i o na n de n h a n c e si t sp r a c t i c a l i t ya sw e l l s e c o n d ，t h er e a l - t i m er e q u i r e m e n t sa r es os t r i c ti nm u l t i - r o b o t i no r d e rt oi m p r o v e t h er e s p o n s er a t e ，t h ep a p e rd e s i g n saa l g o r i t h ma b o u tr e s o u r c ef a i ra l l o c a t i o nb a s e do n t h ea d a p t i v ef u z z yc o n t r o lm e t h o d i tb a s e do nt h ea d a p t i v ec o n t r o lm e t h o d ，a d o p t sf u z z y c o n t r o lm e t h o dt oc o n t r o lt h eg a i nc o n t r o lp a r a m e t e r i nt h es i t u a t i o n ，t h eg a i np a r a m e t e r i sd y n a m i cw i t ht h es y s t e mw i t h o u tk n o w i n gp r e c i s ec h a r a c t e r i s t i c so ft h es y s t e m i i i i v 目录 目录 摘j i 瑟i a j ；s t r a c t i i i 第一章绪论l 1 1 课题的研究背景一1 1 2 研究目的及意义一2 1 3 国内外研究现状4 1 3 1 多机器人系统的研究现状4 1 3 2 网络资源分配的研究现状6 1 4 本文的工作及论文结构7 第二章网络资源分配及其模型设计：9 2 1 多机器人网络实时系统9 2 2 网络资源分配1 0 2 2 1 服务质量与网络资源分配1 0 2 2 2 网络资源分配的公平性准则1 1 2 2 3 效用函数1 4 2 2 4 实时系统的调度算法1 4 2 3 多机器人网络系统的资源分配模型1 6 2 3 1 网络资源和任务集1 6 2 3 2 资源消耗函数的定义1 6 2 3 3 多机器人网络系统的权重与公平性定义1 7 2 4 网络资源公平分配算法的控制目标1 8 2 5 本章小结19 第三章网络资源公平分配的自适应控制方法2 0 3 1 自适应控制方法的基本原理2 0 3 1 1 自适应控制2 0 3 1 2 基本参数说明2 1 v 广东工业大学硕士学位论文 3 2 自适应控制方法的工作过程2 3 3 2 1 多机器人网络中的工作环境2 3 3 2 2 网络资源公平分配流程2 4 3 3 多机器人网络系统的性能分析2 5 3 3 1 资源公平分配算法的可行性分析2 5 3 3 2 资源公平分配的稳定性分析2 6 3 4 本章小结。2 8 第四章模糊控制在多机器人网络资源分配中的应用3 0 4 1 前言3 0 4 2 模糊控制的原理3 1 4 2 1 模糊控制3 1 4 2 2 模糊控制的理论基础_ j 3 3 4 3 网络系统中模糊逻辑控制器的设计3 6 4 3 1 资源公平分配算法的相关参数模糊化3 7 4 3 2 多机器入网络模糊控制器的控制规则3 9 4 3 3 系统参数的去模糊化4 0 4 4 模糊控制在多机器人网络资源公平分配中的应用4 0 4 5 模糊控制在资源公平分配系统的限制因素4 4 4 6 本章小结4 5 第五章网络资源分配系统中概率模糊控制方法的设计4 6 5 1 引言4 6 5 2 概率模糊控制4 7 5 2 1 概率与模糊4 7 5 2 2 概率与不确定性建模4 8 5 3 多机器人网络中概率模糊控制器的设计4 9 5 3 1p f l s 的模糊化5 0 5 3 2 模糊推理5 5 5 3 3p f l s 的去模糊化5 6 5 4 概率模糊控制方法在网络系统中的应用5 8 v i 目录 5 5 本章小结6 2 第六章系统仿真及实验分析6 3 6 1 仿真平台简介6 3 6 1 1m a t l a b 简介1 5 8 - 6 0 】6 3 6 1 2n s 2 简介【6 1 6 3 1 6 4 6 2 仿真部分的模块设计6 6 6 2 1m a t l a b 仿真模块设计6 6 6 2 2n s 2 仿真模块设计6 7 6 3 实验结果及各算法分析比较一6 8 6 4 本章小结7 3 总结与展望7 4 参考文献7 6 攻读学位期间发表的论文8 1 独创性声明8 2 致谤| 8 3 v i i 广东工业大学硕士学位论文 目录 a b s t r a c t ( c h i n e s e ) i a b s t r a c t ( e n g l i s h ) 1 l i c h a p t e r le x t r o d i u m i i is t u d yb a c k g r o u n do ft h es u b j e c t 1 1 2t h eo b j e c t i v ea n dm e a n i n go fs t u d y i n g 2 1 3r e s e a r c hs t a t u sa th o m ea n da b o a r d 4 1 3 1t h er e s e a r c hs t a t u so fm u l t i r o b o t ss y s t e m 4 1 ：；2t h er e s e a r c hs t a t u so fr e s o u r c ea l l o c a t i o n 6 1 4t h ew o r k i n ga n ds t r u c t u r eo f t h i sp a p e r 7 c h a p t e r 2n e t w o r k r e s o u r c ea l l o c a t i o na n dm o d e ld e s i g n 9 2 1m u l t i r o b o t sn e t w o r kr e a l t i m es y s t e m 9 2 2n e t w o r kr e s o u r c e sa l l o c a t i o n 10 2 2 1q u a l i t yo fs e r v i c ea n dn e t w o r kr e s o u r c ea l l o c a t i o n 10 2 2 2f a i r n e s sc r i t e r i o ni nn e t w o r kr e s o u r c ea l l o c a t i o n 1 1 2 2 3u t i l i t yf u n c t i o n 1 4 2 2 4s c h e d u l i n ga l g o r i t h mi nr e a l t i m es y s t e m 1 4 2 3t h er e s o u r c ea l l o c a t i o nm o d e lo fm u l t i - r o b o tn e t w o r ks y s t e m 16 2 3 1n e t w o r kr e s o u r c ea n dt a s ks e t 1 6 ：! ：；2r e s o u r c ec o n s u m ef u n c t i o n 16 2 3 3t h ed e f i n i t i o no f w e i g h ta n df a i ri nm u l t i r o b o tn e t w o r ks y s t e m 1 7 2 4t h ec o n t r o lo b j e c t i v ei nn e t w o r kr e s o u r c ef a i ra l l o c a t i o na l g o r i t h m 18 2 5s u m m a r y 19 c h a p t e r 3a d a p t i v ec o n t r o li nn e t w o r kr e s o u r c ef a i ra l l o c a t i o nm e t h o d 2 0 ：；1b a s i c a lp r i n c i p l eo ft h ea d a p t i v em e t h o d 2 0 ：；1 1a d a p t i v ec o n t r o l 2 0 ：；1 2t h ee x p l a i no f b a s i cp a r a m e t e r s 2 1 c o n t e n t s 3 2t h ew o r k i n gp r o d u c eo fa d a p t i v ec o n t r o lm e t h o d 2 3 3 2 1w o r k i n ge n v i r o n m e n ti nt h em u l t i r o b o tn e t w o r k 2 3 3 2 2t h ef a i ra l l o c a t i o np r o c e d u r eo fn e t w o r kr e s o u r c e s 2 4 3 3t h ep e r f o r m a n c ea n a l y s i so fm u l t i r o b o tn e t w o r ks y s t e m 2 5 3 3 1f e a s i b i l i t ya n a l y s i so fr e s o u r c ef a i ra l l o c a t i o na l g o r i t h m 2 5 3 3 2s t a b i l i t ya n a l y s i so fr e s o u r c ef a i ra l l o c a t i o n 2 6 ：；4s u m m a r y 2 8 c h a p t e r 4f u z z yc o n t r o la p p l yi nm u l t i - r o b o tn e t w o r kr e s o u r c ea l l o c a t i o ns y s t e m 3 0 4 1f o r e w a r d 3 ( ) 4 2t h e p r i n c i p l eo ff u z z yc o n t r 0 1 31 4 2 1f u z z yc o n t r 0 1 3 1 4 2 2t h e o r e t i c a lb a s i so ff u z z yc o n t r 0 1 3 3 4 3t h ed e s i g no ff u z z yl o g i cc o n t r o l l e ri nn e t w o r ks y s t e m 3 6 4 3 1p a r a m e t e r sf u z z yi nt h er e s o u r c ef a i rr e s o u r c ea l l o c a t i o nm e t h o d 3 7 4 3 2c o n t r o lr u l e si nt h em u l t i - r o b o tn e t w o r kf u z z yc o n t r o l l e r 3 9 4 3 3d e - f u z z yo f t h es y s t e m p a r a m e t e r s 4 0 4 4t h ea p p l i c a t i o no ff u z z yc o n t r o lm e t h o di nm u l t i - r o b o ts y s t e m 4 0 4 5t h el i m i t i n gf a c t o ro ff u z z yc o n t r o li nr e s o u r c ef a i ra l l o c a t i o ns y s t e m 4 4 4 6s u m m a r y 4 5 c h a p t e r 5t h ed e s i g no fp r o b a b l i s t i cf u z z yc o n t r o li nt h en e t w o r kr e s o u r c ea l l o c a t i o n s y s t e m 4 6 5 1f o r e w a r d 4 6 5 2p r o b a b l i s t i cf u z z yc o n t r o l 4 7 5 2 1 p r o b a b l i t ya n df u z z y 4 7 5 2 2p r o b a b l i t ya n du n c e r t a i n t ym o d e l i n g 4 8 5 3t h e d e s i g no fp r o b a b l i s t i cf u z z yc o n t r o l l e ri nt h em u l t i r o b o tn e t w o r k 4 9 5 3 1f u z z yo ft h ep f l s 5 0 5 3 2f u z z yr e s e a s o n i n g 5 5 5 3 3d e - f u z z yo f t h ep f l s 5 6 i x 广东工业大学硕士学位论文 5 4p r o b a b l i s t i cf u z z yc o n t r o lm e t h o da p p l yi nt h en e t w o r ks y s t e m 5 8 5 5s u m m a r y 6 2 c h a p t e r 6s y s t e ms i m u l a t i o na n da n a l y s i so fe x p e r i m e n t s 6 3 6 1i n t r o d u c eo fs i m u l a t i o np l a t f o r m 6 3 6 1 1t h ei n t r o d u c eo fm a t l a b 5 8 6 0 】6 3 6 1 2t h ei n t r o d u c eo f n s 2 【6 1 6 3 】6 4 6 2m o d u l ed e s i g no f t h es i m u l a t i o np a r t 6 6 6 2 1t h es i m u l a t i o nm o d u l ed e s i g no fm a t l a b 6 6 6 2 2t h es i m u l a t i o nm o d u l ed e s i g no f n s 2 6 7 6 3t h ee x p e r i m e n tr e s u l ta n da n a l y s i s 6 8 6 4s u m m a r y 7 3 s u m m a r ya n de x p e r t a t i o n 7 4 r e f e r e n c e s 7 6 p u b l i s h e dp a p e r sd u r i n gs t u d i n gf o rm a s t e rd e g r e e 8 1 o r i g i n a ls t a t e m e n t 8 2 a c k n o w l e d g e m e n t s 8 3 x 第一章绪论 1 1 课题的研究背景 第一章绪论 第一台机器人于2 0 世纪6 0 年代初诞生，至今己有4 0 多年的历史。机器人 技术的出现和发展，不但使传统的工业生产面貌发生根本性的变化，而且对人类的 社会生活产生了深远的影响。特别是作为高级形态的智能机器人已经不仅是先进制 造业不可缺少的自动化装备，而且正以惊人的速度在各个领域内扩张渗透。通讯， 电子，传感，控制等技术的不断进步乜，机器人应用领域和范围不断扩展，机器人 技术和能力逐渐提升。目前机器人发展主要经历了三个阶段1 ：可编程、示教再现 型机器人；带有一定的传感功能的机器人；智能机器人。面对复杂和未知的工作环 境，繁重的工作任务，利用单个机器人在信息获取、处理和控制能力方面的局限性 日益突出。因此，多个机器人的应用需求越来越迫切。 多机器人系统不是多个单机器人的简单代数和，而是多个机器人的有机整合同 时其作用效果也不是单机器人作用的线性和，它具备单个机器人无可比拟的优势， 如：当多个机器人分布在广域的环境中时，各机器人通过大量的体内和体外传感器 感知自身及周围的环境，并通过共享其所获得的信息，扩大了机器人系统对环境的 感知区域。这样有利于多机器人系统更有效和精确地定位；同时各机器人可以负责 不同的工作，具备不同的功能特性；时空分布性等特点。因此它们在军事、航空航 天、工业制造、自然界探索、灾害预防与处理、以及服务业等领域的远大应用前景， 并吸引了大量的学者对多机器人系统的研究兴趣h 。5 3 。当前对它的研究主要包括系统 通信、编队、协作与控制以及冲突解决1 等。机器人体内外的各传感器组成的一个 网络系统能能快速而准确地将外部各种信息进行实时反馈，关系到整个系统正常运 作。如：移动式水下观测网络，该网络是一种特殊的移动传感网络，由多个携带观 测设备的水下机器人构成的可移动式系统，单个的水下机器人就可以看成是一个网 络节点，各节点之间依靠声通信进行无线链接。无线传感器网络与机器人的研究成 了当前的热点。 网络技术的迅猛发展使得人们对信息交换的依赖程度增加。它已经渗透到我们 日常生活中的各个领域。现有网络呈现资源相对稀缺、服务多样化、资源分布化和 广东工业大学硕士学位论文 应用商业化等4 大特点。这些特点使得网络运营者或是用户都对网络的研究和进一 步发展提出了更高的要求。计算技术和无线通信技术的进步，推动了低功耗多功能 传感器的快速发展。随机分布的集成有传感器、数据处理单元和通信模块的微小节 点通过自组织方式构成网络。无线传感器网络就是由部署在监测区域内大量的廉价 微型传感器节点组成，通过无线通信方式形成一个多跳自组织的网络系统，其目的 是协作地感知、采集和处理网络覆盖区域中感知对象信息，并发送给观察者。无线 传感器网络和有线网络共同组成了复杂的多机器人网络h 吲。 用户需要提供服务质量( q o s ) 保障，网络的服务质量是指用户的业务在网络传 输过程中所变现的各种性能，可以用一组参数对其进行描述。具体包括带宽、吞吐 量、丢失率、时延、安全性、可靠性等，它们共同构成q o s 参数集。不同的业务对 q o s 参数集的要求不同，而其最终所获得q o s 保障取决于实际占用的网络资源。网 络中最重要的资源是路由器的缓存容量和输出链路带宽。与网络用户的几何级数增 长比较，硬件设备的扩容和更新级数较为缓慢，带宽等网络资源相对匮乏，不能满 足日益增长的用户需求，必须设计一种高效的，合理的资源分配策略以充分利用资 源1 0 - u 1 。 目前的网络资源分配包括无线和有线网络资源的分配。带宽分配问题是近几年 资源分配研究的热点问题，有线网络的带宽分配已经比较成熟，而无线网络的技术 也得到飞速发展，但是由于信道容量有限，节点的移动性，并且无线节点不能同时 接收与发送数据，使得无线网络在资源分配和调度与有点网络相比有很大不同。因 此，无线网络的资源分配不能完全使用有线网络的分配策略。无线信道是共享资源， 许多用户之间竞争网络资源，这使得分配策略需要考虑公平性，尽可能地使每个用 户能够公平地得到网络资源，而无线网络资源是非常有限的，所以在考虑资源分配 公平性的同时也要兼顾资源利用的效率。现在无论是有线网络还是无线网络，都已 有大量公平调度和资源分配的研究成果。为提高无线网络和有线网络综合的q o s ， 公平性是当前资源分配的首要考虑目标，然而在现实生活中，绝对的完全的公平是 无法实现的，只能是将公平性与用户的满意程度综合来加以权衡。 1 2 研究目的及意义 至今，多机器人技术已经得到很大的发展，而多机器人所组成的网络在军事应 用、紧急救灾等恶劣环境下工作展现了其优越性。随着无线技术的发展，终端性能 2 第一章绪论 如能量、容量以及计算能力等的提升，多机器人网络能够提供除简单数据传输之外 的能力。随着多机器人系统商业化应用的需求，更进一步促进了这种趋势。缺乏集 中控制方式、自组织、动态拓扑以及资源受限的特性，为保证业务质量提出了严峻 的挑战。而资源的稀缺性，导致在多机器人网络中提供有效的q o s 支持以合理地分 配资源显得尤为重要n 羽。 多机器人网络中各单机器人之间的信息和资源共享。同时由于多机器人系统是 一个群体系统，各个机器人之间存在信息共享和互换，通信是必不可少的。在完成 某项指令的时候，多机器人系统为了实现协调合作，单机器人的传感器必须提供一 定的环境信息，同时还需提供其他机器人的部分相关信息。因此机器人的各个个体 之间或上层控制和下层之间的通信是必要的。多机器人系统在传输数据时对实时性 要求比较高，同时每个机器人资源又极其有限。因此，通信的时间，质量和效率关 系到整个系统的灵敏性、稳定性和适应性，而如何在多机器人网络资源有限的情况 下尽可能地提供公平高效的q o s 十分关键。 q o s 就是针对不同的要求提供不同的服务质量，如提供支持为用户提供专用带 宽，减少包丢失，避免和管理网络拥塞等n 3 。1 朝。各项服务的q o s 水平很大程度上随 资源分配的增多而提升，但因其存在的同时性，特别是将实时技术应用到多机器人 控制网络中时，处理器的处理能力和资源都非常有限，易发生负载和冲突现象。系 统有必要通过公平仲裁避免不公平服务或服务突然