The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system ...The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.展开更多
Sensing coverage is a fundamental problem in sensors networks. Different from traditional isotropic sensors with sensing disk, directional sensors may have a limited angle of sensing range due to special applications....Sensing coverage is a fundamental problem in sensors networks. Different from traditional isotropic sensors with sensing disk, directional sensors may have a limited angle of sensing range due to special applications. In this paper, we study the coverage problem in directional sensor networks (DSNs) with the rotatable orientation for each sensor. We propose the optimal coverage in directional sensor networks (OCDSN) problem to cover maximal area while activating as few sensors as possible. Then we prove the OCDSN to be NP-complete and propose the Voronoi-based centralized approximation (VCA) algorithm and the Voronoi-based distributed approximation (VDA) algorithm of the solution to the OCDSN problem. Finally, extensive simulation is executed to demonstrate the performance of the proposed algorithms.展开更多
将Voronoi图应用于无线传感器网络定位问题中,提出了VBLS(Voronoi diagrams based local-ization scheme)定位算法.它首先对接收到的anchor节点的接收信号强度(RSSI)从大到小进行排序,然后利用UDG图依次计算每个anchor节点的Voronoi区域...将Voronoi图应用于无线传感器网络定位问题中,提出了VBLS(Voronoi diagrams based local-ization scheme)定位算法.它首先对接收到的anchor节点的接收信号强度(RSSI)从大到小进行排序,然后利用UDG图依次计算每个anchor节点的Voronoi区域,最后将所有Voronoi区域交集的质心输出作为定位结果.通过仿真将VBLS和另外两种无需测距的定位算法(W-Centroid和Centroid)进行了比较.仿真结果表明,对于anchor节点随机摆放的情况,VBLS的定位误差比Centroid和W-Centroid分别降低了18%和13%;对于anchor节点均匀摆放的情况,VBLS的定位误差比Centroid降低了7%,比W-Centroid增加了2%.展开更多
文摘The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.
文摘Sensing coverage is a fundamental problem in sensors networks. Different from traditional isotropic sensors with sensing disk, directional sensors may have a limited angle of sensing range due to special applications. In this paper, we study the coverage problem in directional sensor networks (DSNs) with the rotatable orientation for each sensor. We propose the optimal coverage in directional sensor networks (OCDSN) problem to cover maximal area while activating as few sensors as possible. Then we prove the OCDSN to be NP-complete and propose the Voronoi-based centralized approximation (VCA) algorithm and the Voronoi-based distributed approximation (VDA) algorithm of the solution to the OCDSN problem. Finally, extensive simulation is executed to demonstrate the performance of the proposed algorithms.
文摘将Voronoi图应用于无线传感器网络定位问题中,提出了VBLS(Voronoi diagrams based local-ization scheme)定位算法.它首先对接收到的anchor节点的接收信号强度(RSSI)从大到小进行排序,然后利用UDG图依次计算每个anchor节点的Voronoi区域,最后将所有Voronoi区域交集的质心输出作为定位结果.通过仿真将VBLS和另外两种无需测距的定位算法(W-Centroid和Centroid)进行了比较.仿真结果表明,对于anchor节点随机摆放的情况,VBLS的定位误差比Centroid和W-Centroid分别降低了18%和13%;对于anchor节点均匀摆放的情况,VBLS的定位误差比Centroid降低了7%,比W-Centroid增加了2%.
