Scheduling for information gathering on sensor network
Tóm tắt
We investigate a unique wireless sensor network scheduling problem in which all nodes in a cluster send exactly one packet to a designated sink node in an effort to minimize transmission time. However, node transmissions must be sufficiently isolated either in time or in space to avoid collisions. The problem is formulated and solved via graph representation. We prove that an optimal transmission schedule can be obtained efficiently through a pipeline-like schedule when the underlying topology is either line or tree. The minimum time required for a line or tree topology with
$$n$$
nodes is
$$3(n - 2)$$
. We further prove that our scheduling problem is NP-hard for general graphs. We propose a heuristic algorithm for general graphs. Our heuristic tries to schedule as many independent segments as possible to increase the degree of parallel transmissions. This algorithm is compared to an RTS/CTS based distributed algorithm. Preliminary simulated results indicate that our heuristic algorithm outperforms the RTS/CTS based distributed algorithm (up to 30%) and exhibits stable behavior.
Tài liệu tham khảo
Younis, O., & Fahmy, S. (2004). Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach. In Proceedings of IEEE INFOCOM, Vol. 1, Hong Kong, March 2004.
Gandham, S., Zhang, Y., & Huang, Q. (2006). Distributed minimal time convergecast scheduling in wireless sensor networks. In ICDCS’06, Lisboa, Portugal, July 4–7, 2006.
Nguyen, G. D., Wieselthier, J. E., & Ephremides, A. (2003). Multiple-access for multiple destinations in ad-hoc networks. In Proceedings WiOpt 03, Sophia-Antipolis, France, March 2003.
Ephremides, A., & Truong, T. (1990). Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications, 38(4), 456–460.
Gupta, P., & Kumar, P. R. (2000). The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2), 388–404.
Song, W.-Z., Yuani, F., & LaHusen, R. (2006). Time-optimum packet scheduling for many-to-one routing in wireless sensor networks. IEEE MASS, Vancouver, Canada, October 9–12, 2006.
Tay, Y. C., Jamieson, K., & Balakrishnan, H. (2004). Collision-minimizing CSMA and its applications to wireless sensor networks. IEEE Journal on Selected Areas in Communications, 22(6), 1048–1057.
Sagduyu, Y. E., & Ephremides, A. (2004). The problem of medium access control in wireless sensor networks. IEEE Wireless Communications, 11(6), 44–53.
Garey, M. A., & Johnson, D. S. (1979). Computer and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman and Company.
Khuller, S., Raghavachari, B., & Young, N. (1995). Balancing minimum spanning and shortest path trees. Algorithmica, 14(4), 305–321.