传感器网络中数据时新性移动设备的调度

摘要

To collect the time-sensitive data in Wireless sensor networks, this paper intiOduces the mobile sinks and proposes two heuristic algorithms. The first algorithm is based on the TSP （Travelling Salesman Problem）and performs better when time constraints are relatively weak. It first cuts original problem into several sub-problems and solves them one by one until all time requirements are met. In the circumstance of stringent time constraints, another algorithm plans the mobile elements （ME） paths in a greedy manner. It starts by building short ME tours started from the sink and then expands them with the lowest cost nodes as much as possible, which always maintains the property that no tour violates the time constraints of the nodes it visits. Theoretic analysis and experiments both show that the proposed algorithm decreases the required mobile elements and shortens the data collection time, which could be applied to large scale sensor networks.%为了在传感器网络中收集时间敏感性的数据。引入了移动设备来收集数据。提出了两种启发式算法，一种是基于货郎担问题的解法，将原问题分割成较小集合，然后逐步求解小问题，该算法适用于数据敏感性要求相对较低的应用；而当数据敏感性要求较高时，提出的贪婪式算法逐步建立移动设备的移动路径，即从基站（Sink）开始迭代选择代价值最小的节点。直到不能再添加节点进移动路径中。理论分析和模拟结果表明，提出的算法可以减少数据收集过程中所需要的移动设备的数目．而且大大节省了数据收集的总时间，从而可以应用在大规模网络中。