摘 要：提出了基于网格可预测的位置服务算法(GPLS)。网络划分成网格，通过HASH函数对网格进行分组，通信的源节点通过与目的节点所在分组内的位置服务节点通信，获得目的节点的准确或预测的位置信息。在不增加网络带宽的前提下，提高了位置服务效率，节约了网络的能源和带宽。
关键词：位置服务；可预测；网格；MANET

移动Ad Hoc网络MANET(Mobile Ad hoc Networks) 是一种无基础设施、自组织和自配置的多跳无线网络，网络结构根据节点的移动动态地改变。网络节点通过协作来传输信息，通常节点既作为主机又作为路由器。节点的移动性使得网络中拓扑变化频繁且事先无法预测，所以在MANET中发现和维护路由是一个至关重要的问题，一直是研究的热点和难点问题。
近年来，利用地理位置信息的路由协议在MANET中得到了很大发展。随着全球定位技术(GPS)的普遍应用，节点可以获得自身准确的位置信息。利用这些信息进行路由可以降低路由协议的控制开销、适应动态变化的网络拓扑以及提高路由协议的可扩展性。然而在基于位置信息的路由协议中，在发送路由包之前，源节点需要知道目的节点的具体位置，主要的问题是基于位置服务的路由协议中需要位置服务来确定目的节点的位置，并返回目的节点的位置信息。
本文从稳定高效的角度对基于位置服务算法进行研究，提出了基于网格可预测的位置服务GPLS(Grid-based Predictive Location Service)算法。该算法把整个网络划分成平面网格以避免洪泛操作。通过HASH方法对网格进行分组，节点可以与组内任意网格通信，减少了位置更新和查找的步骤和复杂性，节约了MANET中的能源和带宽。根据同组网格内任意位置服务节点提供的目的节点的位置，预测出目的节点的位置，提高MANET中位置服务的效率，避免洪泛操作。
1 相关算法
GLS(Grid Location Service)[1]将整个网络划分为网格，节点把它的位置信息分布地存放在网络中的一个或多个位置服务器中。通过位置服务节点可随时查询网络中其他节点的位置，各节点间采用地理路由转发进行分组传输。HNS(Helping Node Selection)[2]根据位置服务器中记录节点移动的速度和记录的时间来预判节点的位置，通过其他移动节点把数据包直接携带到预判的位置，再把数据包传输给目的节点。这样既提高了数据包的投递率，又有效地解决了移动自组网络中节点动态移动和空洞问题。PLS(Predictive Location Service)[3]是一个可预测、自适应的平面位置服务。节点定期向周围节点发送缓存中的位置信息。节点在整个网络中洪泛查找目的节点，接收到信息的节点根据缓存中目的节点的位置信息预测出当前目的节点的位置。HBLS(Hashing-Based Location Service)[4]是一个基于HASH集合和平面结构的位置服务算法。在当前服务器消失之前选择一个新的服务器，以提高服务的可靠性和服务的时间。整个网络区域划分为多个不重叠的区域。在伸缩性和可靠性两个方面权衡HBLS都是一个很好的算法。
2 算法描述
2.1 系统模型和假设
系统考虑n个节点在整个网络中自由移动，节点通过无线技术彼此进行通信，但是没有提供固定的网络基础设施。假设所有节点功能相当，都有一个统一的传输范围。每个节点配备GPS接收装置，能确定节点自己的位置，所有在传输范围内的节点都被认为是邻节点。节点既是源，又转发数据，因此形成了MANET。每个节点有一个唯一的身份标识节点ID。网络结构的改变是不可预测的。
2.2 网络划分和网格分组
在地理路由中，通常把网络划分成多个小网格，每个网格分配一个编号，在每个网格内选择一个合适的节点作为位置服务节点(黑点为位置服务节点)，整个网络划分成25个网格，如图1所示。

通过网格ID，建立一个HASH函数f(Gi)=Gi%G0，其中，G0为常数，Gi为网格的ID。把f(Gi)相同的分到一组，把一个网格G1内的节点位置信息映射到其他网格G2、G3……Gn，映射到的网格被分到一组(G1、G2、G3……Gn)，位置服务节点定时向同组内其他位置服务节点传输本网格内节点的位置信息。同组的网格尽量均匀分布到整个网络中。如图1所示，G0=7，f(1)=1%7=1，f(8)=8%7=1，f(15)=15%7=1，f(22)=22%7=1。把网格1，8，15，22分到组1中。依次类推组2、组3、组4、组5、组6、组0。
节点被分配到网格中，每个节点根据节点产生时所在的网格来分配节点ID。根据节点的ID，可以计算节点所在的网格及网格所在的分组，通过组内网格的位置，服务节点获得节点的位置信息。如果同一个网格内的节点都可以相互直接通信，只需要一个网格内最远的距离小于或等于节点的通信的传输半径即可，即×a，如图2所示。其中，R为节点传输半径，a为网格的大小。

2.3 位置服务器选择
每个网格内有位置服务节点，选择离网格中心物理距离最近的节点作为位置服务节点。当位置服务节点离开网格或停止服务以后，网格内的节点需要重新选择位置服务器。
物理距离计算公式：

式中，(x1，y1)、(x2，y2)为网格中心和节点的坐标。
网格服务器节点保存同组网格区域产生的节点信息。源节点要查找目的节点信息，源节点可通过贪心算法向目的节点所在同一分组内某个特定的网格发送查找信息。
2.4 位置的更新
节点根据最初产生时所在的网格获得节点ID。节点把自己的位置信息登记到所在网格的位置服务节点中(位置信息包括节点ID、位置、移动的速度、信息更新的时刻)，节点定时Thello向邻居节点发送hello数据包，报告自己的存在。节点定时Tstart从节点产生时所在分组的网格中选择离现在物理距离最近的网格，并通过贪心算法向该网格报告自己的位置。位置服务节点定时Tserver通过贪心算法向同组其他网格位置服务节点单播本网格产生的节点的位置信息。
节点位置信息更新规则：
(1)节点定时Thello向周围邻居节点发送hello数据包，报告自己的存在。
(2)当节点离开当前网格时，向当前网格位置服务器发送离开请求，位置服务器对节点进行相应的登记。
(3)节点离开节点本身产生时所在网格后，根据移动的距离S0通过贪心算法向产生时所在网格分组最近位置服务节点发送位置更新信息，更新时间的间隔为Tstart。如果移动的距离小于S0，时间间隔到了Tstart，也需要向初始网格服务器发送自己的位置信息。
(4)当节点加入一个新的网格，节点向周围一跳的节点广播hello数据包，获得新的位置服务节点。
(5)位置服务节点定时Tserver向同组内其他网格的服务节点通过贪心算法转发本网格产生节点的位置信息。
(6)网格服务器记录路过节点的位置信息，记录的时间Tnode大于本网格或映射到本网格节点的位置信息的时间Tserver。
位置更新的例子如图3所示。节点9在网格1产生，所以节点9所在的网格分组(1，8，15，22)，当节点移动到网格4时，网格组内网格的中心距离节点9物理距离最近的网格是网格8，所以节点9向网格8报告自己的位置；当节点移动到网格10时，网格内网格的中心距离节点9物理距离最近的网格是15，所以节点9向网格15报告自己的位置，由于移动的距离和时间间隔都还没到，所以当节点移动到网格5时，不会向网格组报告自己的位置，但是网格10的位置服务器会保存节点9离开时的位置信息。网格15定时向网格1、网格8、网格15、网格22报告节点9的位置信息。传输方式全部采用贪心算法。

2.5 位置的查找
当源节点S需要和目的节点D通信时，源节点S需要查找目的节点D的位置，源节点S通过目的节点D的ID计算出目的节点所在的网格组，根据目的节点D产生时所在的网格组内网格(G1、G2、G3……Gn)距离源节点S物理距离，选择距离源节点最近的网格Gi，源节点向最近的网格Gi的位置服务节点查找目的节点D的位置信息，并利用预测公式预测目的节点D的位置。预测公式：

根据Sprediction预测目的节点D所在的网格G′，通过贪心算法向目的节点所在的网格G′发送查找信息。如果目的节点D在查找包到达的网格G′内，则位置已经找到；如果不在，但网格G′有目的节点D离开时的记录，则根据预测函数和离开时的位置信息记录预测网格G″，通过贪心算法向预测的网格G″发送查找信息；如果网格G′没有目的节点D的位置信息，则目的节点D未到达网格G′，则要进行折半查找，即向查找获得的目的节点D的位置与预测的目的节点D的位置的中点所在的网格G?苁进行查找。中点计算公式：

如果网格G?苁有目的节点D的位置信息，则可根据这一位置信息预测目的节点D的位置与网格，并通过贪心算法转发到目的节点D预测的网格；如果没有，则认为目的节点D未到达网格G?苁，再进行折半查找；循环执行，直到预测的网格中心与提供目的节点位置信息网格中心小于S0或目的节点D时停止。
查找步骤如下：
(1)当源节点S需要与目的节点D通信时，本地的位置信息表中没有目的节点D的位置信息。
(2)源节点S首先向本地网格服务器查找是否有目的节点D的位置信息，如果有，则停止查找；如果没有，则发起目的节点D的位置查找。
(3)源节点S需要查找目的节点D，源节点S根据目的节点D的ID计算出目的节点D所属的产生时所在的网格G1，利用HASH函数计算同组网格G2、G3……Gn，从G1~Gn中选择一个离当前源节点物理距离最近的网格Gi，并通过贪心算法向其发送节点查找信息。
(4)根据网格Gi的服务器提供的目的节点D的信息，通过预测函数计算目的节点D所在的网格G′。
(5)通过贪心算法向预测的目的节点所在的网格G′转发查找信息，如果查找包转发过程中发现有新的目的节点的位置信息，则进行更新并及时调整转发策略。
(6)如果目的节点D在路由查找包到达的网格G′内，则位置已经找到；如果不在，但有离开时的记录，则根据离开时的记录和预测函数预测目的节点在网格G″内，向预测的网格G″查找，执行第5步；如果G′中没有目的节点D的信息，则认为目的节点D未到达网格G′，执行第7步。
(7)进行折半查找，向中点网格查找是否有该目的节点D的位置信息，如果有，执行第4步；如果没有，则说明二种可能：(1)初始服务器的节点D信息失效，这时应该删除；(2)节点异常离开网络，停止查找。
目的节点D接收到查找请求包时，则通过贪心算法返回包括目的节点D的位置的信息包到源节点S。源节点S缓存目的节点D的位置信息，这样位置服务实现了目的节点D的查找。
位置查找的例子如图4所示。节点123要与节点9通信，首先节点123计算出节点9在网格1产生，计算出网格1，网格8、网格15、网格22在同一分组。网格组内网格的中心距离节点123物理距离最近的是网格8，网格8提供节点9的位置信息是在网格10；向网格10查找节点9，到了网格10以后没有找到节点9，但有节点9离开时的位置信息，根据位置信息预测出节点9在网格5；向网格5查找节点9，网格5也没有节点9，但是有节点9的位置信息，再次根据预测函数，预测出节点9在网格3；向网格3查找节点9，在网格3查找到节点9，节点9通过贪心算法向节点123回复自己的位置信息，节点123收到节点9的位置信息，这个时候位置查找成功。这里转发方式全部采用贪心算法。

3 位置服务算法比较
表1为几种有关位置服务算法的比较。比较规则如下：(1)局部信息指位置服务有无提供除本节点位置信息以外的其他局部节点的信息，记录局部信息对于移动网络的无状态通信非常有优势；(2)健壮性指网络中个别节点失败影响到节点通信的规模。健壮性越高，影响节点的数量越少；(3)复杂性指位置服务执行操作的复杂程度。复杂性越低，位置服务越简单，服务效率越高；(4)位置服务器是位置服务选择的依据(有基于位置、基于节点和网格ID)和位置服务器主要节点位置信息的管理；(5)区域划分指网络是否根据区域划分成小的网络.区域划分能减少网络总体能源和带宽，对于能源和带宽有限的MANET非常有意义；(6)更新和查找策略指更新和查找过程中位置服务的策略，有单播、广播、洪泛、树形(按照树行的方式有规则的传播)。因MANET的能量和带宽非常有限，应尽量避免洪泛操作，按一定规则方式建立起来的树形传播方式，则方便了链路的建立。

本文结合MANET中网格位置服务、可预测的位置服务和HASH分组的方法提出了基于网格可预测的位置服务算法，该算法使用网格来划分网络，并使用HASH方法对网格进行分组，通过建立预测模型的方法查找目的节点位置，提高目的节点位置查找的准确性。算法中源节点根据目的节点所在的网格分组，通过贪心算法向该分组中的网格发送查找目的节点的信息，根据目的节点的历史位置信息来预测目的节点的位置。把网格和预测结合在一起，避免了洪泛，减少了网络的带宽并提高了包的抵达率，提高了位置服务的性能。因此，在不增加网络带宽的前提下提高了位置服务效率，节约了网络的能源和带宽。
参考文献
[1] LI J， JANNOTTI J， DE C， et al. A scalable location service for geographic Ad hoc routing[C]. Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom)， 2000:120-130.
[2] SU K F， CHOU C， WANG Wei Tong， et al. Improving data transmission with helping nodes for geographical Ad hoc routing[J]. Computer Networks， 2007，51:4997-5010.
[3] LUO Xin Wei， CAMP T， NAVIDI W. Predictive methods for location services in mobile Ad hoc networks[C]. Proceedings of the 5th IEEE International Workshop on Algorithms for Wireless， Mobile， Ad Hoc and Sensor Networks(WMAN)， 2005:246-252.
[4] DERHAB A， BADACHE N. Balancing the tradeoffs between scalability and availability in mobile Ad hoc networks with a flat hashing-based location service[J]. Ad Hoc Networks， 2008(6):1013-1030.
[5] 于宏毅.无线移动自组织网[M].北京:人民邮电出版社，2005.
[6] 张帆，李德敏，陶莉.基于位置信息的MANET路由协议综述[J].计算机工程与应用，2005(20):120-123.