基于无线移动的Ad Hoc网格研究

黑龙江工业学院电气与信息工程系 张 妍 刘 锋 郭维威

1 Ad Hoc网络概述[1][2]

2018年1月31日中国互联网络信息中心关于《中国互联网络发展统计报告》显示：截止到2017年12月，中国网民规模达到7.72亿，普及率达到55.8%，超过全球平均水平4.1个百分点，超过亚洲平均水平9.1个百分点，全年新增网民4074万，增长率为5.6%，手机网民规模达到7.53亿。由此可见人们的学习、工作、生活等方方面面越来越多地依赖于无线网络，对无线网络信号质量和速度的要求也越来越高。目前，大部分移动通信网络还是建立在固定基站等有线基础设施基础上的，为了在无固定基站的特殊环境下有效通信，1991年IEEE802.11标准委员会运用"Ad hoc网络"来描述具有特殊自组织对等式多跳移动通信网络，Ad Hoc网络技术正式诞生了。

Ad Hoc源自于拉丁语，是"for this"的意思，通常引申为"for this purpose only"，可以理解成Ad Hoc网络是一种有特殊用途的网络，也被称为Multi Hop Wireless Network、或者Self Organized Network、或者Infrastructureless Network。Ad Hoc网络的前身是Packet Radio Network，主要针对军事领域通信的需要而研究的，已经持续发展了近40年。

Ad Hoc网络是由一组带有自动收发功能和路由选择功能的移动终端组成，网络通信过程中所有节点的地位相同，除了具有普通移动终端功能外，还具有报文转发功能，节点与节点中间的通信联系可以由其他多个节点参与进来（也被称为多跳），通过分层网络协议和分布式算法，构成任意的网络拓扑，实现了网络的独立工作。

Ad Hoc网络既具备计算机网络的特点又具备移动通信的特点，例如无中心特性：Ad hoc网络中没有绝对意义上的控制中心，每一个节点的地位一样，并且各个节点可以任意地随时加入进来或随时选择离开；自组织特性：无需基础硬件设施的支持，在任何地方、任何时间组建独立通信网络；动态的网络拓扑特性：由于移动终端的个数、速度和位置可以任意改变，网络拓扑也随时发生变化。

Ad Hoc网络自身自动快速组网的能力和设备相对低廉的价格提供了广泛的应用价值，例如：军事领域的应用：Ad Hoc网络主要应用在军事领域，适合车载、单兵、指挥所等场所，是数字化战场的核心技术，可以大大提高军队的战备水平；抢险救灾领域的应用：当发生自然灾害后，原有的通信设施可能被摧毁，而紧急救援工作需要立即展开，因其无需架设硬件网络设施而能够快速展开工作的Ad Hoc网络非常适合在这样恶劣的环境下提供通信保障；团队通信领域：不仅适用于手机、PDA、笔记本等电子设备之间的通信，还适用于会议、庆典、虚拟教室、移动医疗系统等临时场所的通信。

2 AdHoc网格概念[3]

网格（Grid）是一种刚刚兴起的技术，能够将网络上的计算资源、数据资源、存储资源和信息资源等各种丰富资源有机地组合在一起，按照某种规则有序地协同工作，充分实现资源共享，为广大网络用户服务，可以应用在科研领域、生物领域、教育领域、医疗领域、航空航天领域等等，标志着计算领域进入了高性能阶段。

为了适应不断变化的网络环境、动态的网格参与、自组快速的移动连接而提出的移动通信与网格有机结合起来形成的Ad Hoe网格，透明、安全、无缝、有效地支持移动用户和资源，非常适用于现阶段大量涌现的低功耗存储移动设备。Ad Hoe网格是一种异构可移动的无固定结构的通信和计算系统，获得安全、高效的网络服务，广泛应用于军事领域、商用领域和民用领域。

3 任务调度算法[2]

Ad Hoe网格是无线技术和网格计算的融合，资源管理和任务调度是它的两个重要组成部分。资源管理是根据用户请求，找到合适资源，但资源发现的查全率和效率直接影响后面的调度问题【4】；任务调度是满足用户需求和优先约束关系为前提，根据相应的分配策略将下一步执行的任务确定出执行顺序，并合理地分配到各节点上有序地执行，达到总体执行时间(makespan)最短的效果。Ad Hoe网格拓扑频繁变化、资源丰富，合理高效的调度算法不但可以提高资源的利用率，还可以减少任务的总体执行时间。

概况地说，Ad Hoe网格调度算法以提高网格总体效率为目的，根据用户需求和网格即时资源情况而完成最优化调度。其实调度问题就是NP-完成问题，国内外的研究学者提出了许多不同的算法，根据算法不同的基本思想，调度算法的分类方式有很多，典型的分类方式有：静态调度算法、动态调度算法和混合调度算法（静态调度算法和动态调度算法结合在一起使用）。

OLB随机负载均衡算法：是静态调度算法中最简单的一种，不考虑执行时间随机将某个任务分配给某资源。优点是算法简单、易实现，缺点是利用该调度算法可能会得到一个比较差的makespan。

Min-Min算法：是动态调度算法的一种，主要完成独立任务调度问题，该算法的思想是将尽可能多的把任务分配给用时最短的设备上，所以算法自身执行时间短，具有很好的makespan，许多典型的DAG建模都是建立在Min-Min算法基础上的。

GS算法：是动态调度算法的一种，主要完成异构分布计算系统的任务调度问题，将整体任务转换成若干个子任务集合，根据依赖性逐步地找出互不相干的子任务进行调度，直到所以子任务调度完成。过滤的次数直接决定了makespan，因此减少过滤的次数有利于改进调度算法，该算法具有简单、易实现的特点。

评价调度系统的两个基本指标是调度质量和调度算法效率，调度质量是指优化调度的性能，调度算法效率是指任务完成时间的复杂性。对于一个整体任务来说，通过优化调度以后用时越短越好，而如果多个调度算法完成相同的调度质量，那么调度算法越简单越好。

图1 DAG图

图2 makespan实验数据比较图

4 实例模型分析[2][4]

在一个临时场所举办会议，假设临时用笔记本电脑、智能手机和PDA组建一个移动网格来协助会议的顺利召开。模拟实验在Windows 2017环境下运行，利用随机生成算法产生DAG图，如图1所示，设定参数后列出EEC矩阵和ETC矩阵，对模拟任务集进行OLB算法和GS算法，分别比较α在0、0.2、0.4、0.6、0.8、1情况下的数据实验，实验60次，结果取平均值，实验makespan的比较结果如图2所示。

5 结束语

随着人们摆脱有线网络的束缚，对无线网络要求的提升，使得移动计算技术、网格技术、无线技术与数据库技术融合得更加紧密，因此，对Ad Hoc网格技术的研究具有重要的社会意义和经济价值。