臺灣博碩士論文加值系統

一個優質的無線感測網路，端視該網路是否提供最大的感測覆蓋面(coverage area)、良好的連通力(connectivity)及較長的生命週期。受到廣域環境實際需求與限制，許多感測網路感測器之布局並非預設的，而是屬於不定式佈局，這情境就無法保證無線感測網路品質。因此，改善感測網路布局，提升無線感測網路品質是本論文研究的主要目標。
基於在感測網路中實際的應用，本論文以機率感測覆蓋模式(probabilistic sensing coverage model)表示感測點檢測其鄰近事件發生之功能模式。我們以等位曲線(contour graph)表示多個感測點覆蓋面及覆蓋洞(coverage hole)型態。針對感測器佈局之數量，我們提出一個以期望密度考慮的感測器佈局數量演算法。藉由可移動的感測器(mobile sensor)改善網路品質是本文主要策略，針對此議題，我們提出三種混合式虛擬力演算法(Hybrid Virtual Force Algorithm, HVFA)，藉由收集鄰近感測器的資訊，我們可以決定移動感測器新的最佳位置。模擬結果顯示，在給定的覆蓋門檻θ=0.9下 (coverage threshold parameter θ=0.9)，我們所提出的三種演算法在綜合效能指標上皆優於傳統方法。另外，我們也介紹“粗略位置”考量的分散式多匯集點(multiple sink)布局，我們提出一個多匯集點訓練協定演算法(Multiple-Sink Training Protocol Algorithm, MSTPA)來達成感測節點的歸屬分配，進而改善數據傳送所需功耗。模擬結果顯示分散式多匯集點布局相較於單匯集點布局具有優異的節能效果。

The quality of wireless sensor network (WSN) depends on whether the network offers the largest sensing coverage area, good network connectivity and a prolongation life time capability. Therefore, improvement in sensor deployment to promote the quality of distributed WSN is an important topic. It is also the main objective in this dissertation.
Based on realistic applications in sensor networks, a probabilistic sensing coverage model is used in this dissertation to represent the function model of detecting an adjacent event emergence by a sensing node. We sketch multiple sensors coverage and coverage hole using contour graph concept. As for the sensor deployment number, we propose a sensor deployment number algorithm based on the consideration of expected density. The main strategy in this dissertation is to improve the network quality via the movement of mobile sensors. To consider this topic, we propose three Hybrid Virtual Force Algorithms (HVFAs). We can decide the new optimal positions of mobile sensors by collecting the information of neighbor’s nodes. Simulation results show that, under the coverage threshold parameter θ=0.9, the proposed three algorithms outperform the conventional method in terms of synthesized performance index. In addition, we further introduce distributed multiple sink deployment concept based on coarse-grain location awareness. A Multiple-Sink Training Protocol Algorithm (MSTPA) is proposed to achieve the assignment of sensor nodes, and then, to improve the required power consumption of data delivery. Simulation results show that, compared to the centralized single sink deployment, the distributed multiple sink deployment has significant effect on power saving.

TABLE OF CONTENTS
PAGE
ACKNOWLEDGEMENTS 5
摘要 6
ABSTRACT 7
TABLE OF CONTENTS 8
LIST OF FIGURES 10
LIST OF TABLES 12
1. INTRODUCTION 13
1.1 Distributed Wireless Sensor Networks 13
1.2 Sensor Operational Functions and Ranges 14
1.3 Sensor Deployment Topology 15
1.4 Issues That Are Studied in This Dissertation 17
1.5 Contributions in This Dissertation 18
1.6 Thesis Organization 19
2. SENSING COVERAGE 20
2.1 Disk Sensing Coverage Function 20
2.2 Probabilistic Sensing Coverage Model for Multiple Sensor Nodes 22
2.3 Coverage Surface Estimating by Contour Graph 23
2.4 Deployment Sensor Number and Expected Sensor Density 24
2.5 Neighbor Node Density Consideration Base on Sensing Power Consumption 28
3. VIRTUAL FORCE ALGORITHMS FOR MOBILE SENSOR NETWORK 32
3.1 Mobile Sensor Network and Objective Function 32
3.2 Hybrid Virtual Force Algorithm 33
3.3 Network Connectivity and k-Connectivity 39
3.4 Distributed Active-Sleeping Scheduling 40
4. SYNTHESIZING PERFORMANCE ESTIMATION 43
4.1 Performance Metrics 43
4.2 Synthesizing Performance Estimation 44
4.3 Simulation Result 45
5. COARSE-GRAIN LOCATION AWARENESS WSNS 49
5.1 Origin 49
5.2 Corona Sensor Cell and Training Protocol 49
5.3 Multiple Sink Architecture and Training Protocol 53
5.4 Power Consumption of CSCs Training Mode 55
5.5 Power Consumption of CSCs Data Delivery Mode 57
6. SUMMARY AND CONCLUSIONS 60
REFERENCES 61
APPENDIX
A ACRONYMS 64
B SYMBOL REPRESENTATION 65

REFERENCES
[1]I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, vol. 38, no. 4, pp. 393-422, 2002.
[2]Z. Bojkovic and B. Bakmaz, “A survey on wireless sensor networks deployment,” WSEAS Transactions on Communications, vol.7, no. 12, pp. 1172-1181, Dec. 2008.
[3]F. Dressler, Self-Organization in Sensor and Actor Networks. New York, John Wiley and Sons, Inc., 2007.
[4]B. Wang, “Coverage problems in sensor networks: a survey,” ACM Computing Surveys, vol. 43, no. 4, article 32, pp.32.1-32.53, Oct. 2011.
[5]M. Li and B. Yang, “A survey on topology issues in wireless sensor network,” in Proceedings of the International Conference on Wireless Networks, Las Vegas, Nev., USA, pp.503-510, Jun. 2006.
[6]X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in ACM International Conference on Embedded Networked Sensor Systems, pp. 28-39, Nov. 2003.
[7]G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration for energy conservation in sensor networks,” ACM Transactions on Sensor Networks, vol. 1, no. 1, pp. 36-72, Aug. 2005.
[8]F. Aurenhammer, “Voronoi diagrams - a survey of a fundamental geometric data structure,” ACM Computing Surveys, vol. 23, no. 3, pp. 345-405, Sep. 1991.
[9]G. Wang, G. Cao, and T. L. Porta, “Movement-assisted sensor deployment,” in Proceeding of IEEE INFOCOM, pp.2469-2479, 2004.
[10]N. Heo and P. K. Varshney, "An intelligent deployment and clustering algorithm for a distributed mobile sensor network," in Proceedings of IEEE International Conference on Systems, Man and Cybernetics, pp. 4576-4581, 2003.
[11]W. Li and C. G. Cassandras, “Distributed cooperative coverage control of sensor networks,” in Proc. 44th IEEE Conf. Decision Control, pp. 2542–2547, Dec. 2005.
[12]X. Li and Y. Xi, “Distributed cooperative coverage and connectivity maintenance for mobile sensing devices,” in Proc. 48th IEEE Conf. Decision Control, pp. 7891–7896, Dec. 2009.
[13]Y. Zou, and K. Chakrabarty, “Sensor deployment and target localization in distributed sensor networks,” ACM Trans. Embed. Computer System, vol. 3, no 1, pp. 61–91. 2004.
[14]J. H. Wen, C. C. Yang, and Y. F. Huang, “A probabilistic sensor detection model based on contour graph for network coverage in wireless sensor network,” International Conference on Advanced Information Technologies, Apr. 2013.
[15]N. Ahmed, S.S. Kanhere, and S. Jha, “The holes problem in wireless sensor networks: a survey,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, no. 2, pp. 4–18, Apr. 2005.
[16]P. Santi, “Topology control in wireless Ad Hoc and sensor networks,” ACM Computing Surveys, vol. 37, no. 2, pp. 164–194, Jun. 2005.
[17]A. Chen, S. Kumar, and T. H. Lai, “Local barrier coverage in wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 4, pp. 491–504, 2010.
[18]J. Cortes, “Coverage optimization and spatial load balancing by robotic sensor networks,” IEEE Transactions on Automatic Control, vol. 55, no. 3, pp. 749–754, 2010.
[19]A. Howard, M. J. Matari´c, and G. S. Sukhatme, “Mobile sensor network deployment using potential field: a distributed scalable solution to the area coverage problem”, in Proceedings of 6th International Conference on Distributed Autonomous Robotic Systems, Jun. 2002.
[20]N. Heo and K. Varshney,“Energy-efficient deployment of intelligent mobile sensor networks”, IEEE Transactions on Systems and Humans, vol. 35, no. 1, pp. 78 - 92 Jan. 2005.
[21]H. Zhang and J. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” Ad Hoc and Sensor Wireless Networks: An International Journal, vol. 1, no. 1-2, pp. 89–123, Jan. 2005.
[22]M. Zhong, and G. Cassandras, “Distributed coverage control and data collection with mobile sensor networks,” IEEE Transactions on Automatic Control, vol. 56, no. 10, pp. 2445 – 2455, Oct. 2011.
[23]F. Barsi, A. A. Bertossi, F. B. Sorbelli, R. Ciotti, S. Olariu, and M. C. Pinotti, “Asynchronous corona training protocols in wireless sensor and actor networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 20, pp. 1216 – 1230, 2009.
[24]F. Barsi, A. A. Bertossi, C. Lavault, A. Navarra, S. Olariu, M. C. Pinotti, and V. Ravelomanana, “Efficient location training protocols for heterogeneous sensor and actor networks,” IEEE Transactions on Mobile Computing, vol. 10, pp. 377 – 391, 2010.
[25]A. A. Bertossi, S. Olariu, and M. C. Pinotti, “Efficient training of sensor networks,” 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks, July 15, 2006.
[26]J. H. Wen, C. C. Yang, C. M. Lin, and Y. F. Huang, “Corona sensor cell based deployment for multiple-sink wireless sensor networks,” WSEAS Transactions on Communications, vol. 9, no. 1, pp. 449-459, Sep. 2013.