臺灣博碩士論文加值系統

在無線感測網路(Wireless Sensor Network, WSN)中，一個關鍵的工作便是偵測到所有目標並將所有感測器資訊順利傳回基地台(Sink)，但考慮到佈置感測器的成本昂貴，一般而言我們會將大量散佈的感測器分成多組排程，使一組執行並將其他組設定在低能量消耗的待命狀態，藉此達到輪流使用而不是一次用掉所有感測器的電池能量。假設每一組感測器組合的動作時間及每個感測器消耗能量相同，則在限制的能量下找出越多組的組合，便能夠提升整體排程時間以延長生命週期(Lifetime)。

本篇論文中以上述的問題為主，並探討兩個重要的因素，即偵查所有目標(Full coverage)並且確保傳輸要求(Connectivity)，換句話說在一組感測器組合中，所有的感測器必須都能找到一條路徑使資料得以正確的傳回基地台，且必定可偵查到所有的目標物，才能符合要求。除此之外本篇論文也針對以往類似的問題，Set-k cover problem[1]將其轉換成同意義的Disjoint set cover (DSC) problem[2]提出新的想法，在考慮到各個感測器擁有的初始能量不同的情況下，一個感測器理當能重複出現在不同的組合中提供更多的可能性及幫助，這種概念稱為Joint set並且與原本的Disjoint set想法相反。我們提出一個基因式演算法(Genetic algorithm)協助解決這類的問題，並探討新的能量概念是否能比原本的方式達到更好的結果。

In wireless sensor network(WSN), Our goal is to detect all the targets and let sensors can send all the information to base stations, but considering the high cost of the sensor arrangement, in general we will distribute a large number of sensors into groups scheduling. Assuming each sensor group has the same sensor energy consumption, find out more sensor group will be able to improve the overall schedule time to extend the lifetime.

This paper investigates two important factors, first one is to detect all targets (Full coverage) and second is to ensure that the transmission requirements (Connectivity), in other words a group of sensors, all sensors must be able to find a path to return information to base station, and detect all the targets. In addition this paper has a similar problem, Set-K cover problem. We propose the various sensing devices should have different initial energy case, a sensor should be repeated in different sensor groups to provide more possibilities and help, and this concept called joint set. We propose a genetic algorithm (GA) to solve these problems, and investigate the new concept of energy.

Contents
List of Figures
List of Tables
1 介紹
1.1 無線感測網路介紹
1.2 無線感測網路相關議題
2 相關論文研究 
2.1 同時考慮偵查與傳輸的研究
2.2 針對偵查方面的研究
2.3 針對傳輸方面的研究
2.4 整理及結論
3 問題公式化
3.1 Full coverage定義
3.2 Connectivity定義
3.3 初始能量
3.4 問題定義
4 提出的演算法
4.1 演算法架構
4.1.1 Representation and Initialization
4.1.2 Fitness function
4.1.3 Crossover and Mutation
4.2 Forward Operator
5 實驗結果 
5.1 問題實例與參數設置
5.2 等長能量比較
5.3 不等長能量比較
5.4 感測器數量測試
5.5 目標數量測試
5.6 高電量測試
6 結論與未來展望
Bibliography

[1] N. Aziz, A. W. Mohemmed, and M. Y. Alias. A wireless sensor network
coverage optimization algorithm based on particle swarm optimization and
voronoi diagram. In Proceedings of the 2009 IEEE International Conference
on Networking, Sensing and Control, Okayama, Japan, March 26-29, 2009,
2009.

[2] M. Cardei and D. Z. Du. Improving Wireless Sensor Network Lifetime through
Power Aware Organization. Springer Netherlands, 2005.

[3] X. M. Hu, J. Zhang, and Y. Yu. Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks. In IEEE
TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 14, NO.5, 2010.

[4] J. Jia, J. Chen, G. Chang, and Z. Tan. Energy ecient coverage control
in wireless sensor networks based on multi-objective genetic algorithm. In
Computers and Mathematics with Applications, 2009.

[5] J. Jia, J. Chen, G. Chang, C. Tian, and W. Qin. Maximization for wireless
sensor network lifetime with power ecient cover set alternation. In Circuits
and Systems, 2008, 2008.

[6] C. Joo, J. G. Choi, and N. B. Shro. Delay performance of scheduling with
data aggregation in wireless sensor networks. In IEEE INFOCOM 2010 pro-
ceedings, 2010.

[7] D. B. Jourdan and O. L. Weck. Layout optimization for a wireless sensor
network using a multi-objective genetic algorithm. In VTC 2004-Spring.
2004 IEEE 59th, 2004.

[8] D. B. Jourdan and O. L. Weck. Multi-objective genetic algorithm for the
automated planning of a wireless sensor network to monitor a critical facility.
In Proceedings of SPIE, 2004, 2004.

[9] C. C. Lai, C. K. Ting, and R. S. Ko. An eective genetic algorithm to improve
wireless sensor network lifetime for large-scale surveillance applications. In
Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, 2007.

[10] C. C. Liao and C. K. Ting. Extending wireless sensor network lifetime through
order-based genetic algorithm. In Systems, Man and Cybernetics, 2008. SMC
2008. IEEE International Conference on, 2008.

[11] M. Mahdavi, M. Ismail, and K. Jumari. Load balancing in energy ecient
connected coverage wireless sensor network. In International Conference on
Electrical Engineering and Informatics, 2009, 2009.

[12] M. Senthamilselvi and Dr. N. Devarajan. Energy ecient distributed connected
coverage algorithms with dynamic coverage maintenance in wireless
sensor networks. In 2009 IEEE International Advance Computing Conference
(IACC 2009), 2009.

[13] T. Shu and M. Krunz. Coverage-time optimization for clustered wireless
sensor networks: A power-balancing approach. In IEEE/ACM TRANSAC-
TIONS ON NETWORKING, VOL. 18, NO. 1, FEBRUARY 2010, 2010.

[14] S. Slijepcevic and M. Potkonjak. Power ecient organization of wireless
sensor networks. In Communications, 2001. ICC 2001. IEEE International
Conference on, volume 2, pages 472476 vol.2, 2001.

[15] D. Tian and N. D. Georganas. Connectivity maintenance and coverage preservation in wireless sensor networks. In Ad Hoc Networks, 2005, 2005.

[16] C. K. Ting and C. C. Liao. A memetic algorithm for extending wireless sensor
network lifetime. In Information Sciences, 2010.

[17] X. Wang, S. Wang, and J. J. Ma. An improved co-evolutionary particle
swarm optimization for wireless sensor networks with dynamic deployment.
In Sensors, 2007.

[18] Y. Zhao, J. Wu, F. Li, and S. Lu. Vbs: Maximum lifetime sleep scheduling
for wireless sensor networks using virtual backbones. In IEEE INFOCOM
2010 proceedings, 2010.