AD HOC网络中的资源定位

ad hoc网络中的资源位置弗朗索瓦丝·赛汉引用此版本：弗朗索瓦丝·赛汉。ad hoc网络中的资源定位。计算机科学[CS]。皮埃尔和玛丽·居里大学-巴黎第六大学，2005年。法语。NNT：电话：00469420HAL ID：电话：00469420https://theses.hal.science/tel-004694202010年4月1日提交HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire论文标题：AD HOC论文呈现在巴黎第六大学前以获得学位：巴黎第六大学博士提及：计算机PAR弗朗索瓦丝·赛兰主办团队博士学院：计算机科学、电信和电子大学组成部分：LIP6在审查委员会面前Pierre Sens，主席EricFleury，报告员David Simplot-Ryl，报告员TitosSaridakis，审查员ValérieIssarny，论文订单号ii.我谢谢你我要感谢皮埃尔和玛丽·居里大学的皮埃尔·森斯教授，感谢他荣幸地接受了评审团主席的职位。我还要感谢CNRS/INRIA研究总监David Simplot-Ryl和INSA教授EricFleury接受我的报告员职位，并感谢他们对我的论文发表的相关评论;感谢诺基亚研究员Titos Saridakis出席我的答辩。出于多种原因，我想向我的论文导师Valérie Issarny表示衷心的感谢。首先，我很感激他指导了我的研究，同时让我自由地探索我认为合适的途径。此外，我感谢她在整个论文过程中的明智建议，以及她的出席和激励。最后，除了和他一起工作是一次非常丰富的经历之外，还能说什么呢感谢整个阿尔勒团队的热情欢迎和良好的幽默感。我特别感谢Agnès、Sonya和Jean Luc积极参与我的论文的校对工作，感谢Rafic在原型实施过程中提供的帮助，感谢Emmanuelle的管理专业知识和可用性。我祝愿目前的博士生Ferda、JinShen、David和Sonya，以及他们的继任者（你们将得到很好的照顾）继续取得成功。最后，我想特别感谢Ferda，他是我在阿尔勒团队工作多年的同事。我们长时间的讨论，他的善良，他的耐心，对我来说是一个真正的财富。我感谢我的第二个家庭，也就是我的朋友和我一路上遇到的每一个人，感谢他们给了我最好的。我衷心感谢玛丽昂，她是我早期的朋友，我和她一起度过了加拿大的几个极地冬天，也感谢查尔斯和塞巴斯蒂安在写这篇论文时在伦敦受到的欢迎我不会忘记向Onar致敬，我忠实的电脑，它受到了严峻的考验，有一天早上，当我没有做所有的备份时，它最终爆炸了（部分是一样的）。谢谢你，马修，你扑灭了火。现在，我想从心底里感谢信徒中的信徒：我的家人，我的父母，我的兄弟让·莫里斯和我的双胞胎妹妹弗洛伦斯。感谢他们坚定不移的爱。最后，正如魁北克人所说的那样，我祝愿所有直接或间接出席并参与这篇论文的人都有一个良好的开端。ii.iii致我的父母，我的哥哥让·莫里斯和我的双胞胎妹妹弗洛伦斯。ivv阿加索斯。 知识不是直觉的东西，即使在这里也不是。至于智慧，要满怀信心地祈求天使赐给你。Oinos.但在这最后的存在，我曾梦想，我将获得所有的知识在一个单一的打击，并在同一时间绝对幸福。阿加索斯。啊!幸福不在于科学，而在于获得科学。永远知道是永恒的幸福;但知道一切将是魔鬼的诅咒。Oinos.但是，既然我们的知识每时每刻都在增长，那么，我们最终不一定会知道所有的事情吗？阿加索斯。把你的目光投向遥远的深渊!让你的眼睛努力穿透这些无数的星星的前景。在这里，我们被揭示出，这种无限物质的唯一目的是提供无限的源泉，灵魂可以在其中满足对知识的渴望，这种渴望是永远无法熄灭的，因为熄灭这种渴望对灵魂来说就是自我毁灭来吧! 我们将离开昴宿星的辉煌和谐，远离人群，进入猎户座之外的星空草原，在那里，我们将发现三层太阳和三色太阳，而不是思想、紫罗兰和狂野的思想。埃德加·坡的《话语的力量》vivii摘要终端（PDA、膝上型计算机、电话）数量的增加和无线网络（GSM、GPRS、UMTS、WLAN、蓝牙）的扩展证明了用户对随时随地访问诸如数据或应用服务之类的资源的日益增长的需求。在这种情况下，ad hoc网络可以发挥重要作用，因为它们不需要基础设施来通信，它们也可以在基础设施部署昂贵或不必要的情况下使用，或者它们可以用于增加基于基础设施的网络的覆盖范围。此外，这些ad hoc网络可以独立运行或连接到其他类型的网络，以便为用户提供对更大的资源集的访问。在基于基础设施的有线或无线网络中，所提出的定位资源的解决方案主要基于集中网络资源信息的目录。由于缺乏连接，特别是由网络拓扑的变化和电池能量储备的耗尽引起的连接，这些解决方案在ad hoc网络中是不可用的。为ad hoc网络提出的解决方案依赖于在带宽方面昂贵的广播技术，并且导致网络过载。现有解决方案的这种低效率仍然是开发用于集成adhoc网络的无线网络的应用的主要障碍之一。 本论文的目标是提供一个有效的资源定位，以保证在一个集成的ad hoc网络环境中对可用资源的透明访问。首先，本文介绍了在ad hoc网络中终端和资源定位的研究工作。然后，我们介绍了我们提出的用于执行适应于ad hoc网络的特征的资源定位的技术（例如，节点密度、网络面积），并且这是为了限制由该位置产生的流量。特别是，这导致我们在小型和大型自组织网络中分别处理资源定位问题。我们提出的第一种方法是完全分布式的。终端一起协作以定位网络上的资源。此外，该协议还包括缓存和预加载技术，以提高定位和访问资源时的性能。为了在大规模adhoc网络中实现有效的资源定位，我们引入了一种半分布式viii基于在ad hoc（或可能的混合）网络上动态部署的一组目录的分布式网络。这些贡献得到了性能评估的补充，包括基于模拟和实验的理论和实践研究。最后，我们介绍了我们的资源定位协议在Web服务上下文中的实现。此中间件基于对环境中存在的Web服务实例的动态发现来支持对移动Web服务的无处不在的访问。ix摘要无线技术的最新进展，加上随之而来的便携式设备的丰富，为无线网络的未来带来了令人兴奋的机遇。在这种情况下，移动自组织网络（MANET）可以发挥重要作用，因为它们是自主的，不需要任何预先存在的基础设施用于通信目的，可以方便地部署在构建网络基础设施昂贵或笨重的位置，并且有可能增加基于基础设施的网络的可达性。此外，ad hoc网络可以以独立的方式彼此操作，或者连接到其它类型的网络以向用户提供对各种资源的访问。然而，MANET是高度动态的，并且由于设备是移动的并且以低电池功率操作的事实而遭受网络拓扑中的频繁和不可预测的变化。考虑到这些特定特征，很明显，大多数设计用于在有线网络中操作的现有方法不能用于在普遍计算环境中定位和提供对资源的访问。然而，这些方法大多是集中式的，因此不适用于无基础设施的网络。这种低效率，再加上节点的低连接性和移动性，仍然是开发用于集成Manets的无线环境的应用的主要障碍。具体地说，普及计算环境中的资源定位已经成为无线和/或移动环境中的一个有吸引力的研究领域。然而，所提出的解决方案是基于广播的，并且导致受限网络过载。因此，它们无法解决可扩展性、移动性或适应性的问题。因此，本论文所解决的问题是在将ad hoc网络与其他互连网络（可能基于基础设施）集成的普适计算环境中提供自动和高效的资源定位以及对可用资源的无处不在的访问。本文首先研究了在无基础设施环境中提出的技术和策略。然后，它引入了一个概念架构，以实现无处不在的资源定位和访问，在非基础设施的普遍性环境。该体系结构适应于ad hoc网络的特征（例如，节点密度、网络区域）。它使我们能够在小型或可扩展的ad hoc网络中解决资源本地化的分离路径问题。资源本地化的第一种方法是合作和完全分布式的，并对其进行平衡。x通过适当平衡设备之间的通信负载，实现性能与成本的平衡。该协议包括一些能量感知缓存和预取策略，以提高资源定位的总体性能。为了在可扩展的ad hoc网络中支持高效的资源本地化，我们引入了一个半分布式解决方案，该解决方案基于在ad hoc（或可能的混合）网络上动态部署的一组目录。为了提高所提出的解决方案的性能，我们引入了几个跨层优化。资源发现协议的设计进一步补充了广泛的性能评估，包括基于模拟和实现的理论和/或实践研究。最后，我们介绍了我们的可扩展资源发现协议在基于Web服务技术的中间件中的集成。该中间件允许在动态普适计算环境中基于自动发现无处不在地访问移动Web服务。xi目录感谢我总结七摘要九第1章一般介绍11.1 动机和问题31.2 ad hoc网络中的有效资源定位 5第2章ad hoc网络 92.1 导言............................................................................................................... 92.2 临时环境中的资源本地化102.2.1 用于终端定位的路由协议112.2.2 资源本地化272.3 通信引起的能源消耗372.3.1 访问通道382.3.2 信息传输过程中的优化432.4 合成..............................................................................................................502.4.1 执行的背景522.4.2 小规模网络中的资源定位542.4.3 大规模网络中的资源位置56第3章小规模ad hoc网络的分布式位置593.1 导言593.2 本地化协议613.3 硬件和用户配置文件633.3.1 用户配置文件的定义643.3.2 配置文件管理653.3.3 配置文件交换663.3.4 在合作过程中使用概况673.4 集成用户缓存733.5 预加载技术的集成763.6 评估823.6.1 通信中消耗的能量823.7 结论88第4章大规模4.1 导言914.2 本地化原则924.2.1 协议94的配置4.2.2 系统配置的动态管理1044.3 在N-邻中的位置1064.3.1 保持可见性1074.3.2 资源注册1074.3.3 本地缓存管理1084.3.4 第109章第一次见面4.4 在ad hoc网络中的位置 110xii4.4.1 目录配置文件1114.4.2 半分布式位置1134.4.3 协作管理1154.5 在混合网络中的位置1164.6 评估1184.7 结论124第5章实现服务发现的半分布式定位1275.1 导言............................................................................................................1275.2 Web服务体系结构1305.2.1 Web服务描述语言1315.2.2 SOAP 132协议5.3 Ariadne：用于大规模ad hoc网络的中间件1335.3.1 Web服务的本地化服务........................................................................................1335.3.2 Web服务实例的位置1345.4 阿里阿德涅138的原型5.4.1 CSOAP容器 1395.4.2 本地化服务1425.4.3 本地化服务的结构1435.4.4 定位服务的部署和使用1455.4 评估............................................................................................................1485.4.1 评估对Web服务的访问1485.4.2 定位服务的评估1525.5 结论............................................................................................................156第六章结论159参考书目165xiii图表图1-1基于基础设施的模型2图2-1 OLSR 13协议图2-2选择要插入到部分树中的节点14图2-3资源的分配和获取36图2-4 EC-MAC协议的传输阶段41图2-5混合电网54图3-1资源位置62图3-2用户配置文件65图3-3值分布71图3-4分配函数Q 72图3-5 1级依赖关系图78图3-6 2级依赖关系图79图3-7发送方和接收方传输范围内的终端84图3-8产生的能源消耗85图3-9扩散引起的能量消耗86图3-10内容物汇回导致的能耗87图4-1本地化体系结构93图4-2选举流程101图4-3本地目录和用户行为的建模110图4-4 m 112图4-5使用MD5算法生成Bloom大小滤波器112图4-6本地化流程113图4-7本地114目录图4-8用户行为114图4-9根据节点密度生成的流量119图4-10分散式和拉动式方法的比较120图4-11根据目录覆盖率生成的流量121图4-12平均等待时间的比较122图4-13正的............................................................................................................................. 概率123图5-1 WDS 131文档图5-2：Ariadne 138原型图5-3 SOAP 140图5-4 CSOAP容器140图5-5 Web服务本地化体系结构142图5-6定位服务的结构143图5-7大型数组的CSOAP响应时间149图5-8小表的CSOAP响应时间149图5-9 CSOAP与AXIS 150的比较图5-10 CSOAP与Java RMI 151图5-11本地和非本地位置的响应时间152图5-12 PC和笔记本电脑之间定位响应时间的比较。153图5-13使用PDA定位时的响应时间154图5-14响应时间与可用服务实例数量的函数关系。155图5-15 Ariadne定位时的响应时间与UPDATE156xivxv图片列表表2-1路由协议的属性26表2-2与点对点通信相关的能耗41表3-1 TTL度量和跳数73表3-2预加载算法81表3-3与通信相关的能耗83表3-4发送方和接收方的能耗84表3-5基于网络中节点密度的能耗87表4-1目录选择算法99表4-2评级汇总103表5-1 WDS 132xvi1第一章一般最近已经提出了各种无线技术（例如，蓝牙[12]、IEEE 802.11 [43]、HomeRF [57]1、HiperLAN [83]2），其目的是用无线电波代替有线传输。这些技术适应于特定的使用环境，并且特别地产生了两种类型的网络：无线个人区域网络（PAN）和无线局域网（WLAN）。无线个人网络主要由属于同一用户且相距几米的设备组成。由于蓝牙终端的有限传输范围和它定义的通信模型，蓝牙标准提供了适用于PAN的技术的最佳示例。例如，基本蓝牙（或微微网）网络最多支持八个终端，其中一个终端被指定为主终端，其余八个终端被指定为从终端。无线局域网覆盖局域网的边界，对应于公共空间或企业的边界。IEEE 802.11、HiperLAN和HomeRF技术的使用与这种类型的网络相关，因为它们的传输范围在几百米的数量级上。这些技术使用两种不同的方法来管理用户的移动性。一些网络，我们称之为基于基础设施的网络，只支持终端的移动，而网络的核心保持固定。如图1-1所示，网络基础设施由基站组成，这些基站管理与位于地理上有限的区域（称为小区）内的终端的通信。1http://www.homerf.org2http://portal.etsi.org/。