基于路径网络的无线广播模型最短路径搜索

The Shortest Path Search of Radio Broadcast Model Based on Path Network

摘要: 针对广播模型采用的传统最短路径计算的不足，本文结合路径网络的特点，提出椭圆边界算法EBA，通过把网络分割成区，将其放在任一分区到另一分区的最小和最大可能距离的信息检索中，并利用相邻辖区算法NRA，解决极端情况下，搜索空间过大和广播周期过长的问题，使其在内存、访问延迟时间和CPU时间的性能优于传统的方法，并通过仿真实验验证其有效性。

Abstract: Aimed at the shortcomings of traditional shortest path calculation used in broadcasting model, through dividing the network into regions, this paper proposes the Elliptical Boundary Algorithm EBA in the information retrieval of the minimum and maximum possible distance from any region to another region, and uses the next region algorithm NRA to solve the problem of excessive search space and long broadcast cycle in extreme cases. The performance of memory, access delay time and CPU time is better than traditional methods, and its effectiveness is verified by simulation experiments.

1. 引言

随着移动位置服务LBS (Location-based Service)的发展，移动设备用户可以向服务商请求到距离他们位置最近的业务或者服务 [1] ，如目的地导航，在地图上找到个人联系信息或接受交通拥挤之类的警示等。

为了回应基于位置的查询，如具体位置的导航，设备通常选择预先装载图数据并执行本地查询，或者把它连接到由GSM/3G/Wi-Fi服务提供商的位置服务器上。前者容易导致移动设备重负荷且只能有少数预先存储的地图可用，当用户去到一个新的国家或城市时，这个选择会失效 [2] 。此外，储存本地地图易导致过时的网络信息服务。选择后者，由于越来越多的用户和服务，本地的服务器在线查询已经面临着可扩展性和网络拥塞等问题 [3] 。

上述问题一个较有效的解决方法是无线广播模型 [4] 。它的主要优势在于服务器端没有进程产生，网络开销与客户端的数量无关，且用户隐私得以保证。由于服务器的硬件要求低，多台服务器可以安装在不同的位置以提供大面积覆盖；而它的缺陷在于没有考虑路径网络的特点。

本文主要研究基于路径网络的无线广播模型的最短路径搜索，针对广播模型采用的传统最短路径计算的不足，利用路径网络的特点，提出了利用椭圆边界算法EBA，通过把网络分割成区，并将其放在任一分区到另一分区的最小和最大可能距离的信息检索中，并利用相邻辖区算法NRA，解决极端情况下，搜索空间过大的问题使其在内存要求、访问延迟时间和CPU时间的性能优于传统的方法，并通过路径网络的仿真实验验证新方法的有效性。

2. 相关工作

路径网络是一个有向加权图G = (V, E)。其中V是节点Vi的集合，每个节点Vi以 i, x _i, y _i>形式来表示标识和节点坐标。E是边界(v _i, v _j)的集合，表示成 i, ia _i, w _ij>，包含有连接节点v _i，v _j的标识和边界w _ij的权值，w _ij为边界长度。源节点Vs和目标节点Vt间的最短路径是连接Vs和Vt的具有最小边界权值和的边界序列。

假设用户的位置，即最短路径的源和目的地是位于两个网络节点Vs和Vt，而不是一些边缘上的任意位置。首先考虑Dijkstra算法 [5] ，它不请求任何的预先计算，因此广播周期只保护路径网络的信息，例如所有节点的邻接表。这种方法的访问延迟是不可接受的，因为无法知道用户查询的源和目的地，在一个周期内以一定顺序来组织节点是不可能的。

在AcrFlag算法中 [6] ，路标和SPQ会广播节点/边(邻接信息)，分别以位向量，距离向量，彩色四叉树的形式。它和Dijkstra面临着相同的问题：相邻边/节点的信息可能已经被传递，需要等待下一个周期，并造成不可接受的延误，除了在CPU在客户端的时间处理缩短外，其他所有性能影响因素较差。

Landmark算法 [7] 是可以实现选择性收听的有效方法。为了能够修剪搜索空间，客户端需能够接收整个检索。因为存储了众多的预算距离，导致了较长的广播周期，较长的收听时间，并在客户端的内存要求较高。

3. 椭圆边界算法EBA (Elliptic Boundary Algorithm)

为了能处理最短路径查询，本文把路径网络分割成区，即分区(region)并且使用一个索引结构来引导检索。椭圆边界算法EBA关键在于为客户端提供Vs和Vt间的最短路径距离的一个上限。这个上限用于修剪过于远离Vs和Vt而影响最短路径搜索的网络信息节点。通过把网络分割成区，并将其放在任一分区到另一分区的最小和最大可能距离的EB信息检索中。EBA检索有两个组成部分。首先定义分割区，并提供一个节点的映射到分区的，其次制定两个分区间的最大/最小距离。

本节采用一个简单但非常有效的分区方法kd-tree [8] ，如图1所示：最初，网络由一条平行于x轴的直线y = 10分为两个分区，对应于所有的网络节点中位数的y坐标。每两个分区由平行线划分成y轴，对应节点位数的x坐标；对于上界分区这条直线是x = 9，对于下界是x = 11。过程中持续递归，在两轴之间交替，直到达到所需的分区数(即kd-tree的叶子)。在图1的16个分区中，kd-tree在右边显示分区的构建；每个节点的值对应于分割相应分区成子分区的x或y的值。

Figure 1. Kd-tree

图1. Kd-树

EBA检索的第一部分包含有kd-tree的分割值，在本文的例子中，检索的第一部分是序列<10; 9; 11; 16; 15; 7; 6; 5; 4; 12; 13; 7; 8; 14; 15>。在通常的例子中，如果有n个分区，则序列含有n − 1个值。假定最左边叶子的最左边分区是R1，依次为其近临分区编号。本文将此规则应用到第二个叶节点(R3, R4)等，并得出该地区在如图所示的数字。

为了能够选择性收听，EBA检索的第二部分在每个分区间提供了最大和最小距离。例如，一个n*n的矩阵A，n是所有分区的总数。每一行代表源分区而每一列代表了目的分区。每个单元格A_Ri,Rj有两个值：从任何节点Ri到任何节点Rj距离的最小和最大值。为了创建矩阵A，EB需要预先计算来自不同分区边界节点对的最短路径，设S是预先计算的最短路径的集合，例如在不同分区的任何边界节点对之间的路径。设R是接收分区，而不是Rs或Rt。Vs到Vt的最短路径可能只通过出现在S的至少一条路径的节点v(v $\in$ R)。把出现在S中的节点称为跨界节点，剩余的为本地节点。每个分区的数据被分成跨界段和本地段，因此，如果 $R\notin \left\{Rs,Rt\right\}$ ，用户可能只接收到前者而不能接收到后者。注意到两个段对Rs和Rt都是所需的，因为本地节点可能出现在由Vs到Rs的边界节点的路径上，或者从Rt的边界节点到Vt的路径上。

如图2，源节点Vs在辖区R1而目的节点Vt在辖区R5，最短路径的最大值是UB = A_Ri,_Rj = 7。因此客户端只需接收源和目的的分区，加上R2 (1 + 2 < 7)和R4 (1 + 2 < 7)。而分区R3和R6是不需要的,因为他们的最小距离之和大于UB (分别是6 + 2和8 + 1)。

Figure 2. Index of EB

图2. EB的索引

4. 邻接分区算法NRA (Next Region Algorithm)

因为EBA允许选择性收听，它的搜索空间(被客户端接收的分区集合)会变得很大。当源和目的远离时这个问题会加剧，在极端情况下Vs和Vt在最远的分区，则EBA可能接收全部分区。在这种情况下，EBA算法的性能可能比Dijkstra算法还差，因为EBA的广播周期更长了。

本小节提供的邻接分区算法NRA可以解决上述问题。服务器再次预先计算不同分区的边界节点的最短路径，但检索保持对应每个出现在任一边界节点的任一最短路径的中心分区的节点对Ri和Rj。这些分区保证包含有从Ri的任何节点到Rj的任何节点的最短路径。以检索一个m*m布尔值的矩阵A为例，其中m是网络分区的数量。Rm分区的检索A^m是一个有m行m列的矩阵。A^m在Rm数据前放置在广播周期中。每个单元格 $A_{Ri,Rj}^m$ 在广播周期中指示着Ri到Rj的最短路径所需要的下个分区Rnxt，注意Rnxt可能就是Rm本身。图3展示了周期的构建和相应的必需分区，其中未标签的位置是分区和相应的检索未对应。

Figure 3. Region needed

图3. 必需分区图

考虑图4中的例子，设源节点在有两个边界节点的分区R1，目的节点在有一个边界节点的分区R16。R1和R16的边界节点中有两条最短路径：一个通过R2, R6, R7, R11, R12，另外一个通过R5, R6, R7, R11, R12。NR检索记录从R1到R16的任一最短路径只通过上述分区集合(在图中以灰色表示)，同时在A中相应位置为1。

Figure 4. The shortest path from R1 to R16

图4. R1到R16的最短路径

邻接分区算法NRA的描述如下：

1) 在处理一个查询时，设备在频道中收听，接收当前包，然后等待随后的索引广播。

2) 客户端接收包含有下个索引的指针，然后寻找下个请求分区Rnxt。当Rnxt被广播时它被唤醒并且持续监听直到决定下个所需要分区的A^{nx t +1}同样被收到。

3) 当接收到最后一个索引时，表明Rnxt是客户端已经处理的分区，收听停止。

4) 要找到从R1中的源到R25中的目的地的最短路径。假设当R11数据被广播时形成查询，指明R13是下一个所需要的分区。

5) 设备被唤醒来接收R13与相邻检索R14，客户端持续从频道接收信息直到A¹⁵指向R19 (如图5所示)。

Figure 5. NRA, receive A¹⁵

图5. NRA，接收A¹⁵

5. 实验评估

实验评估Dijkstra、ArcFlag、Landmark、EBA 和NRA五种算法的性能特性，客户端的算法在Java 2 Micro Edition (J2ME)平台上实现，使用的是Java ME SDK v3.0。实验设备(内存，CPU等)模拟SDK内部作为一种通用GPS功能的手机，支持目前的J2ME标准。服务器端进程由C++实现。使用仿真路径网络(2183节点和3042边界)。

图6呈现了在路径网络中五种算法的收听时间、内存、访问延迟时间和CPU时间的性能对比。由图6可以看到，NRA在收听时间和内存消耗方面性能最好，其次是能够有修剪效果的EBA。

另一方面，EBA和NRA的不足在对于长的路径是明显的，因为他们监听和存储整个广播周期;对于Landmark来说问题更加严重，因为它的周期很长。此外，NRA实现了比Dijkstra算法还短的访问延迟，这是因为NRA只接收不跨越整个周期的广播数据包的一个子集。

(a) 收听时间 (b) 内存 (c) 访问延迟 (d) CPU时间

Figure 6. Algorithm performance comparison

图6. 算法性能对比

6. 结论

本文主要研究的是如何使最短路径计算适应广播模型，利用路径网络的特点，并针对广播模型的不足。通过把网络分割成区，将其放在任一分区到另一分区的最小和最大可能距离的信息检索中，并利用相邻辖区算法NRA，解决极端情况下，搜索空间过大和广播周期过长的问题，最后通过仿真实验验证了新算法在收听时间、内存、访问延迟时间等性能提高的有效性。

基金项目

本研究工作受广西大学大学生创新创业训练项目(国家级No. 201810593068)，以及第四批南宁市特聘专家《基于查询感知的移动位置更新服务系统》项目资助。

NOTES

^*通讯作者。