臺灣博碩士論文加值系統

對無線感測網路之部署而言，有效率且精確的部署極具重要性。近年來，一些具有能量節省之分散式自我部署演算法已被提出，像智慧型兼具群集結構部署演算法、分散式自我部署演算法。這些演算法利用群集結構與點對點結構之協合對感測器部署提供均勻的分佈。當網路拓樸有較均勻的分佈，我們可以平衡網路內之交通負載量，進而使網路之覆賒捫n達到最大且增長網路生命週期。為了進一步改善自我部署演算法之效能，在本篇論文裡，我們提出一個兼具均勻性且能量節省之演算法。這演算法不但使網路拓樸更均勻地分佈，而且加快了演算法之收斂速度以達到能量節省之效能。
當網路拓樸已經達到均勻分佈下，我們提出在均勻分佈下增長系統生命週期之演算法，目的是為了使感測器有較長的時間能彼此通訊。此外，在已建構之系統環境下，我們也發現網路拓樸以及感測器能量之均勻分佈能使系統達到最佳之效能。最後，我們考慮感測器所收集的資料如何有效率地傳送到基地台以及感測器因長時間使用而損壞對網路所造成的影響，進而提出避免網路分割且有效率地能量使用之繞徑方法，使得感測器所收集的資料有方向性地傳送到基地台並解決因感測器損壞所造成網路分割的問題。
經由效能的模擬分析，驗證了我們所提出兼具均勻性且能量節省演算法之均勻分佈與收斂速度效能優於智慧型兼具群集結構部署演算法以及分散式自我部署演算法。此外，在我們所提出增長系統生命週期的方法中，更均勻地感測器位置分佈以及能量分佈將會使系統獲得更好的效能。最後，經由模擬結果分析，我們也驗證了所提出避免網路分割且有效率地能量使用之繞徑方法確實解決了網路分割的問題並增長感測器之使用壽命。這也使得感測器之覆賒捫n不至於迅速縮減。

Efficient and accurate sensor deployment is a critical requirement for the development of wireless sensor networks (WSNs). Recently, distributed energy-efficient self-deployment algorithms, such as the intelligent deployment and clustering algorithm (IDCA) and the distributed self-spreading algorithm (DSSA), have been proposed. These algorithms offer almost uniform distribution for sensor deployment by employing a synergistic combination of cluster structuring and a peer-to-peer deployment scheme. While the topology of WSNs achieves nearly uniform distribution, we can balance the traffic load to maximize the networks coverage and increase the networks lifetime. To further improve the performance of self-deployment algorithms, an uniform and energy-efficient deployment algorithm (UEEDA) is proposed in this thesis. The algorithm not only makes the networks topology more uniformly distribution but also accelerates algorithm convergence speed to achieve energy-efficiency.
While the networks topology has achieved uniform distribution, a lifetime-extended under uniform distribution (LEUD) algorithm is also developed to possibly provide ubiquitous communication for a longer duration in large-scale networks. Furthermore, under the system model, we also find uniform networks topology and uniform energy distribution of sensors could optimize system performance. Finally, we consider how the received data by sensors transmits to the base station and the effect on networks due to some dead sensors. Therefore, networks partition-free and energy-efficient routing (PFEER) scheme is proposed to make the received data by sensors directionally transmit to the base station and solve the problem of networks partition due to some dead sensors.
Based on the performance analysis, we conclude that the proposed UEEDA outperforms both of DSSA and IDCA in terms of uniformity and algorithm convergence speed. Moreover, in the proposed LEUD method, better uniform distribution in sensors’ location and sensors’ energy makes system obtain optimal performance. Finally, simulation results demonstrate that PFEER certainly solves the networks partition problem and offers a longer system lifetime. This also prevents networks coverage from reducing rapidly.

Chapter 1 Introduction
1.1 Background
1.2 Motivation and objective
1.3 Organizations of the thesis
Chapter 2 Overview of Wireless Sensor Networks
2.1 Introduction to WSNs
2.1.1 Factors influencing sensor networks design
2.2 The applications of WSNs
2.2.1 Military applications
2.2.2 Environmental applications
2.2.3 Health applications
2.2.4 Home applications
2.2.5 Other commercial applications
2.3 Sensor networks communication architecture
2.3.1 Application layer
2.3.2 Transport layer
2.3.3 Network layer
2.3.4 Data link layer
2.3.5 Physical layer
Chapter 3 Uniform and Energy-Efficient Deployment of Intelligent
Wireless Sensor Networks
3.1 Introduction
3.2 Preliminary works
3.2.1 Distributed Self-Spreading Algorithm (DSSA)
3.2.2 Intelligent Deployment and Clustering Algorithm (IDCA)
3.3 Performance metrics in mobile WSNs
3.3.1 Coverage
3.3.2 Uniformity
3.3.3 Time
3.3.4 Distance
3.4 The proposed deployment algorithm
3.5 Simulation results
Chapter 4 Design a Lifetime-Extended Algorithm in Deployed
Environment
4.1 Energy-efficient WSNs design
4.1.1 Controlled sensor placement
4.2 Proposed a lifetime-extended algorithm
4.3 Maximize system lifetime
4.4 Optimal system lifetime
4.5 Simulation results
Chapter 5 Design a Networks Partition-Free and Energy-Efficient
Routing Scheme
5.1 Introduction
5.1.1 Networks architecture
5.1.2 Low-Energy Adaptive Clustering Hierarchy (LEACH)
5.2 Energy-efficient routing scheme
5.3 The proposed routing scheme
5.3.1 Partition-Free and Energy-Efficient Routing (PFEER) scheme
5.3.2 Networks Partition Reconstruction Algorithm (NPRA)
5.4 Simulation results
Chapter 6 Conclusions and Future Research
6.1 Conclusions
6.2 Future research
References

[1]I. F. Akyildiz, W. Y. Su, and S. E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks (Elsevier) Journal, March 2002.
[2]C. E. Jones, K. M. Sivalingam, P. Agrawal, and J. C. Chen, “A Survey of Energy Efficient Network Protocols for Wireless Networks,” Wireless Networks, vol. 7, no. 4, 2001, pp. 343–358.
[3]W. Ye, J. Heidemann, and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” Proceedings of IEEE Global Telecommunications Conference, vol. 3, June 2002, pp. 1567–1576.
[4]S. Kumar, F. Zhao, and D. Shepherd, “Collaborative Signal and Information Processing in Microsensor Networks,” IEEE Signal Processing Magazine, vol. 19, no. 2, Mar. 2002, pp. 13–14.
[5]S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” Proceedings of IEEE International Conference Communications, vol. 2, June 2001, pp. 472–476.
[6]C. Shen, C. Srisathapornphat, and C. Jaikaeo, “Sensor Information Networking Architecture and Applications,” IEEE Personal Communications, vol. 8, no. 4, Aug. 2001, pp. 52–59.
[7]G. Hoblos, M. Staroswiecki, and A. Aitouche, “Optimal Design of Fault Tolerant Sensor Networks,” Proceedings of IEEE International Conference on Control Applications, Sept. 2000, pp. 467–72.
[8]Bulusu et al., “Scalable Coordination for Wireless Sensor Networks: Self-Configuring Localization Systems,” ISCTA 2001, July 2001.
[9]J. M. Rabaey et al., “Picoradio Supports Ad Hoc Ultra-Low Power Wireless Networking,” IEEE Computer Magazine, vol. 33, no. 7, July 2000, pp. 42–48.
[10]A. Bakre, and B. R. Badrinath, “I-TCP: Indirect TCP for Mobile Hosts,” Proceedings of the 15th International Conference on Distributed Computing Systems, May 1995, pp. 136–143.
[11]E. Shih, S. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan, “Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” Proceedings of ACM MobiCom’01, July 2001, pp. 272–286.
[12]E. Shih, B. H. Calhoun, S. Cho, and A. Chandrakasan, “Energy-Efficient Link Layer for Wireless Microsensor Networks,” Proceedings of IEEE Computer Society Workshop on VLSI, April 2001, pp. 16–21.
[13]K. Chakrabarty, S. S. Iyengar, Q. Hairong, and C. Eungchun, “Grid Coverage for Surveillance and Target location in Distributed Sensor Networks,” IEEE Transactions on Computers, vol. 51, no. 12, Dec. 2002, pp. 1148–1153.
[14]P. L. Chiu and F. Y. S. Lin, “A Simulated Annealing Algorithm to Support the Sensor Placement for Target Location,” Canadian Conference on Electrical and Computer Engineering, vol. 2, May 2004, pp. 867–870.
[15]S. S. Dhillon, and K. Chakrabarty, “Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks,” IEEE Wireless Communications and Networking, vol. 3, March 2003, pp. 1609–1614.
[16]P. L. Chiu and F. Y. S. Lin, “A Near Optimal Sensor Placement Algorithm to Achieve Complete Coverage/Discrimination in Sensor Networks,” IEEE Communications Letters, vol. 9, no. 1, January 2005, pp. 43–45.
[17]P. L. Chiu and F. Y. S. Lin, “A Simulated Annealing Algorithm for Energy-Efficient Sensor Network Design,” Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, April 2005, pp. 183–189.
[18]D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS),” Global Telecommunications Conference, vol. 5, Nov. 2001, pp. 25–29.
[19]D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) Using AOA,” Proceedings of the 22th Annual Joint Conference of the IEEE Computer and Communications Societies, 2003.
[20]C. C. Han and B. Mani, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, July 2001.
[21]S. Capkun, M. Hamdi and J. P. Hubaux, “GPS-Free Positioning in Mobile Ad-Hoc Networks,” Proceedings of the 34th Annual Hawaii International Conference on System Sciences, Jan 3–6 2001, pp.10.
[22]D. Niculescu and B. Nath, “Position and Orientation in Ad Hoc Networks,” Computer Science Department.
[23]N. Heo and P. K. Varshney, “A Distributed Self Spreading Algorithm for Mobile Wireless Sensor Networks,” IEEE Wireless Communications and Networking, vol. 3, March 2003, pp. 1597–1602.
[24]N. Heo and P. K. Varshney, “Energy-Efficient Deployment of Intelligent Mobile Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics – Part A, vol. 35, no. 1, Jan. 2005, pp. 78–92.
[25]V. Kawadia and P. R. Kumar, “Power Control and Clustering in Ad Hoc Networks,” Proceedings of the 22th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, March 2003, pp. 459–469.
[26]C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, vol. 15, no. 7, Sep. 1997, pp. 1265–1275.
[27]N. Heo and P. K. Varshney, “An Intelligent Deployment and Clustering Algorithm for A Distributed Mobile Sensor Network,” IEEE International Conference on Systems, Man and Cybernetics. vol. 5, Oct. 2003, pp. 4576–4581.
[28]Y. C. Wang, C. C. Hu and Y. C. Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” Proceedings of the First International Conference on Wireless Internet, July 2005, pp. 114–121.
[29]P. L. Chiu and F. Y. S. Lin, “Energy-Efficient Sensor Network Design Subject to Complete Coverage and Discrimination Constraints,” IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 26-29, Sept 2005, pp. 586–593.
[30]K. Akkaya, and M. Younis, “A Survey of Routing Protocols in Wireless Sensor Networks,” Elsevier Ad Hoc Network Journal, vol. 3/3, 2005, pp. 325–349.
[31]J. N. Al-Karaki, and A.E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey,” IEEE Wireless Communications, vol. 11, no. 9, Dec. 2004, pp. 6–28.
[32]Y. Chen, and Q. Zhao, “On the Lifetime of Wireless sSensor Networks,” IEEE Communications Letters, vol. 9, no. 11, Nov. 2005, pp. 976–978.
[33]W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 9, Oct. 2002, pp. 660–670.
[34]H. Oh, H. Bahn, and K. J. Chae, “An Energy-Efficient Sensor Routing Scheme for Home Automation Networks,” IEEE Transactions on Consumer Electronics, vol. 51, no. 3, Aug. 2005, pp. 836–839.
[35]K. P. Shih, H. C. Chen, J. K. Tsai, and C. C. Li, “A Distributed Partition-Free Lazy Movement Protocol for Mobile Sensor Networks,” Proceedings of the Workshop on Wireless, Ad Hoc, and Sensor Networks, Chungli, Taiwan, Aug. 2005.
[36]W. H. Yuen, H. N. Lee, and T. D. Andersen, “A Simple and Effective Cross Layer Networking System for Mobile Ad Hoc Networks,” Proceedings of the 13th IEEE International Symposium on Personal Indoor and Mobile Radio Communications, vol. 4, Sept. 2002, pp. 1952–1956.