﻿ 基于路径网络的无线广播模型最短路径搜索 The Shortest Path Search of Radio Broadcast Model Based on Path Network

Computer Science and Application
Vol. 08  No. 12 ( 2018 ), Article ID: 27988 , 6 pages
10.12677/CSA.2018.812199

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

Ying Yang1*, ShuaihuYang2, Lei Yang3

1College of Computer and Electronic Information, Guangxi University, Nanning Guangxi

2Collegeof Mathematics and Information Science, Guangxi University, Nanning Guangxi

3Institute of Applied Physics, Guangxi Academy of Sciences, Nanning Guangxi

Received: Nov. 28th, 2018; accepted: Dec. 6th, 2018; published: Dec. 13th, 2018

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广西大学计算机与电子信息学院，广西 南宁

2广西大学数学与信息科学学院，广西 南宁

3广西科学院应用物理研究所，广西 南宁

1. 引言

2. 相关工作

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

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

Figure 1. Kd-tree

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

Figure 2. Index of EB

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

Figure 3. Region needed

Figure 4. The shortest path from R1 to R16

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

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

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

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

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

5. 实验评估

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

Figure 6. Algorithm performance comparison

6. 结论

The Shortest Path Search of Radio Broadcast Model Based on Path Network[J]. 计算机科学与应用, 2018, 08(12): 1798-1803. https://doi.org/10.12677/CSA.2018.812199

1. 1. 王金如. 基于移动位置的信息分享服务系统研究与实现[D]: [硕士学位论文]. 北京: 北京邮电大学,2016.

2. 2. 严锐. 融合用户特征分类和协同过滤的餐饮位置服务推荐[D]: [硕士学位论文]. 武汉: 武汉大学, 2017.

3. 3. 黄达. 基于移动位置数据的城市交通状态分析[D]: [硕士学位论文]. 北京: 北京交通大学, 2017.

4. 4. Pióro, M., Tomaszewski, A. and Capone, A. (2018) Anto-nio Maximization of Multicast Periodic Traffic Throughput in Multi-Hop Wireless Networks with Broadcast Transmissions. Ad Hoc Networks, 77, 119-142. https://doi.org/10.1016/j.adhoc.2018.04.011

5. 5. Alina, B., Antonino, G. and Antonio, C. (2018) An Innovative MapRe-duce-Based Approach of Dijkstra’s Algorithm for SDN Routing in Hybrid Cloud, Edge and IoT Scenarios. Lecture Notes in Computer Science, 185-198.

6. 6. Zang, Y., Wang, C., Yu, Y., Luo, L., et al. (2017) Joint Enhancing Filtering for Road Network Extraction. IEEE Transactions on Geoscience and Remote Sensing, 55, 1511-1525. https://doi.org/10.1109/TGRS.2016.2626378

7. 7. 刘钊. 基于协同过滤的位置智能推荐及隐私保护方法研究[D]: [硕士学位论文]. 南京: 南京邮电大学, 2017.

8. 8. Hu, L., Nooshabadi, S. and Ahmadi, M. (2015) Massively Parallel KD-Tree Construction and Nearest Neighbor Search Algorithms. IEEE International Symposium on Circuits and Systems, Lisbon, 24-27 May 2015, 2752-2755. https://doi.org/10.1109/ISCAS.2015.7169256

9. NOTES

*通讯作者。