AHSWN Home • Issue Contents • Forthcoming Papers
An AP Graph Coloring Deployment Algorithm for Indoor Sensor Network Positioning
Xudong Zhu, Yuxin Mao, Ji Qi and Renjie Wang
In large indoor spaces such as complexes and logistics warehouses, sensor networks with automated mobile devices rely on high-accuracy indoor positioning systems. Due to the complexity of the indoor space structure, access point (AP) deployment is the key problem of indoor wireless location applications. The goal is to obtain an AP location scheme with high positioning accuracy and controllable deployment cost for any given indoor space structure, while the deployment algorithm itself has acceptable time overhead. This paper proposes a fast deployment algorithm based on graph theory. In this algorithm, the indoor plane space is modeled according to the coverage characteristics of wireless signals, and the problem is reduced into the k-coloring problem of weighted undirected graphs. Therefore, a graph coloring algorithm is proposed to obtain the deployment location of AP. Experimental results show that the proposed algorithm can achieve better positioning accuracy and cost deployment scheme in polynomial time compared with the existing greedy or heuristic algorithms.
Keywords: Indoor Wireless Location; Access Point; Graph Coloring; Positioning Accuracy