Optimal Stop Points for Data Gathering in Sensor Networks with Mobile Sinks

• 作者: Junyoung Park Kyoungjin Moon Sunggu Lee Sungjoo Yoo
• 来源期刊: 无线传感网络(英文)
• 学科: 工学
• 关键词: Wireless Sensor Network (WSN) Mobile SINK Energy Efficiency Optimization Tabu SEARCH HEURISTIC
• 年，卷（期）: 2012,（1）
• 页码范围: 8-17
• 页数: 10页
• 分类号: TN92

摘要

Given a wireless sensor network (WSN) in which a mobile sink is used to collect data from the sensor nodes, this paper addresses the problem of selecting a set of stop points that results in low energy usage by the sensor nodes. This paper assumes an approach in which a mobile sink travels along a fixed path and uses a stop-and-collect protocol since this has previously been shown to be an efficient WSN data collection method. The problem of selecting an optimal set of stop points is shown to be an NP-hard problem. Then, an Integer Linear Programming (ILP) formulation is used to derive an optimal algorithm that can be used for small problem instances. Next, a polynomial-time Tabu-search-based heuristic algorithm is proposed. Simulations are used to compare the energy consumption values, computation times and expected network lifetimes when using the optimal ILP algorithm, the proposed heuristic algorithm and several other possible heuristic algorithms. The results show that the proposed heuristic algorithm results in near-optimal energy usage values with low computation times, thereby making it suitable for large-sized WSNs.