在無線感測網路中，多收集點 (Multi-Sink) 的建置是一種延長網路存活時間的方法，大量的感測資料將可分散給各收集點，避免收集點周遭的熱點做過多次資料代傳，提早將電量耗盡。而過去針對多收集點負載平衡 (Load balancing) 的研究裡，感測器多半選擇最近的收集點做為資料傳送目的地，此策略可減少網路的整體電量消耗，然而在無線感測網路裡，事件的發生經常會集中在特定的區域，若該地區的感測器均傳送資料到最近的收集點，將會使該收集點鄰近的熱點負擔過重，提早將電量耗盡，導致收集點被孤立在網路外，並造成大量的路由路徑斷裂。
因此本文提出了一個適用於多收集點無線感測網路的負載平衡機制。透過我們所提出的移動式錨點 (Mobile Anchor)，將感測網路動態的劃分成數個地區，以分配適當的資料量給各收集點。而為了適應各種型態的資料流量，我們將機器學習 (Machine Learning) 的強化學習法導入移動式錨點，並實現一個Q-Learning學習代理人。代理人經過一段時間的學習後，將可取得一個最佳的錨點移動策略，遵循此策略將可達到熱點的負載平衡，避免特定收集點提早被孤立，同時延長整個網路的存活時間。

In wireless sensor networks (WSNs), the deployment of multiple sink (Multi-Sink) is an effective way to prolong the lifetime of network. The high data traffic load can be distributed among numbers of sinks, and it obviously reduces data forwarding times for hotspots around sink. Many past researches about load balancing in Multi-Sink WSNs, sensors choose the nearest sink as the destination for sending data. However, in WSNs, events often occur in specific area. If sensors in this area all follow the Nearest-Sink strategy, sensors around nearest sink called hotspots will exhaust energy early. It means that this sink is isolated from network early and numbers of routing paths are broken.
In this paper, we propose a load balancing scheme in Multi-Sink WSNs. A Mobile Anchor we proposed to adaptively partition the network into numbers of regions for sinks, so that suitable data load can be assigned to sinks. To adapt to different data traffic pattern, we apply a Machine Learning method called Reinforcement Learning to Mobile Anchor and implement a Q-Learning agent. Through numbers of interactions with environment, the agent can discovery a near-optimal control policy about movement of Mobile Anchor. The policy can achieve minimization of residual energy’s variance among hotspots, which prevent the early isolation of specific sink and prolong the lifetime of WSNs.

[1] Akyildiz I.F., Weilian S., Sankarasubramaniam Y., Cayirci E.: ‘A survey on sensor networks’, IEEE Commun. Mag., 2002, 40, pp. 102–114
[2] W. Chengjie, Y. Ruixi, and Z. Hongchao, "A Novel Load Balanced and Lifetime Maximization Routing Protocol in Wireless Sensor Networks," in Vehicular Technology Conference, 2008. VTC Spring 2008. IEEE, 2008, pp. 113-117.
[3] Soyturk, M. and Altilar, T., ”A Novel Stateless Energy-Efficient Routing Algorithm for Large-Scale Wireless Sensor Networks with Multiple Sinks” in Proc. of the IEEE Annual Wireless and Microwave Technology Conference, 2006.
[4] Hyunyoung Lee, Klappenecker, A., Kyoungsook Lee, and Lan Lin ”Energy efficient data management for wireless sensor networks with data sink failure” in Proc. of the IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov. 2005.
[5] Yuichi Kiri, Masashi Sugano, Masayuki Murata, "Self-Organized Data-Gathering Scheme for Multi-Sink Sensor Networks Inspired by Swarm Intelligence," saso, pp.161-172, First International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2007), 2007.
[6] Soyturk, M. and Altilar, T., ”A Routing Algorithm for Mobile Multiple Sinks in Large-Scale Wireless Sensor Networks”, in Proc. of the 2nd International Symposium on Wireless Pervasive Computing, Feb. 2007.
[7] Qing Huang; Yong Bai and Lan Chen, ”An Efficient Route Maintenance Scheme for Wireless Sensor Network with Mobile Sink” in Proc. of the IEEE 65th Vehicular Technology Conference, April 2007.
[8] Haiyun Luo, Fan Ye, Jeffy Cheng, Songwu Lu and Lixia Zhang, ”Two- Tier Data Dissemination in Large-Scale Wireless Sensor Networks” Wireless Networks 11, 161-175, 2005.
[9] Zoltan Vincze, Rolland Vida, "Deploying Multiple Sinks in Multi-hop Wireless Sensor. Networks", in Proceedings of ICPS 2007, IEEE International Conference
[10] Chunping Wang, Wei Wu, "A Load-balance Routing Algorithm for Multi-sink Wireless Sensor Networks," in International Conference on Communication Software and Networks, 2009. ICCSN 2009.
[11] Rei-Heng Cheng, Shiuan-Yea Peng, Chiming Huang, "A Gradient-Based Dynamic Load Balance Data Forwarding Method for Multi-sink Wireless Sensor Networks," apscc, pp.1132-1137, 2008 IEEE Asia-Pacific Services Computing Conference, 2008
[12] FORTUNE S., DU D., HWANG F.: ‘Voronoi diagrams and Delaunay triangulations’, Eucl. Geom. Comput., 1992, 1, pp. 193–233
[13] M.L. Puterman, “Markov Decision Processes,” Wiley Interscience,1994. R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. The MIT Press, March 1998.
[14] L. P. Kaelbling, M. L. Littman, and A. P. Moore, “Reinforcement learning: A survey,” Journal of Artificial Intelligence Research, vol. 4, pp. 237–285, 1996.
[15] C. Watkins, “Learning from delayed rewards,” Ph.D. dissertation, Cambridge University, Cambridge, England, 1989.
[16] A. G. Barto, S. J. Bradtke, and S. P. Singh, “Learning to act using real-time dynamic programming,” Artificial Intelligence, vol. 72, pp. 81–138, 1995.
[17] C. J. C. H. Watkins, and P. Dayan, “Technical note: Q learning,” Machine Learning, vol. 8, no. 3, pp. 279-292, 1992.
[18] R. Bellman, Dynamic Programming. Princeton, NJ: Princeton Univ. Press, 1957.
[19] Forster, A.: Machine Learning Techniques Applied for Wireless Ad-Hoc Networks: Guide and Survey. In: Proc. of ISSNIP’07, Melbourne, pp. 367–370 (2007)
[20] T. Suzuki, M. Bandai and T. Watanabe, “DispersiveCast: Dispersive Packets Transmission to Multiple sinks for Energy Saving in Sensor Networks,” in Proc. of Personal, Indoor and Mobile Radio Communications (PIMRC) 2006.
[21] Marc Toussaint, “Lecture Notes: Markov Decision Processes” April 13, 2009