臺灣博碩士論文加值系統

Wireless sensor network是近年來一個十分熱門的研究領域。在sensor network當中，通常會有許多節點共用同一個channel，這會造成channel sharing problem，例如：增加route discovery的複雜度、降低network performance以及因為訊號的干擾而必須重傳封包，這會使得energy consumption增加。為了解決上述的問題，有許多網路拓樸控制的演算法被提出來。其中，最廣為使用的就是backbone機制。到目前為止，大多數的backbone演算法都著重在從整個網路當中挑選出適當的節點作為coordinators以減少backbone size，然而過少的 coordinators用來轉送封包將造成效能不佳等負面影響。所以許多啟發式的演算法被提出來，但是這些演算法並不能夠有效率地將多餘的節點除去，以及在稀疏的網路狀態下，網路傳輸效能會大幅度降低。此論文第一部分的目標是提供一個新穎的backbone演算法稱為SmartBone，我們提出先使用Flow-Bottleneck preprocessing來找出所有的critical nodes，這些節點能夠增加connectivity，以及提出Dynamic Density Cutback來將多餘的節點去除掉。SmartBone同時考慮了網路效能以及能源的消耗。採用SmartBone能夠降低一半的backbone size，並且能夠將能源的節省率從採用傳統方法的25%提升到40%，這將節省了大量的能源消耗。另外，在sensor network中的一些節點因為電源耗盡或故障，使得網路的拓樸變得比較稀疏，在這樣惡劣的網路環境下，我們的SmartBone能夠將packet delivery ratio從採用傳統方法的40%提升到90%。sensor network存在另外一個潛在的問題，就是如何有效率的把封包從single-source傳送至multi-sinks。也就是從一個sensor node把資料收集起來，然後傳給對此資料有興趣的多個clients。要處理這種情況的困難之處在於尋找minimum-cost transmission paths，已經有很多routing algorithm被提出來解決這個問題，但是現存的演算法大部分著重於減少能量的消耗。所以當只考慮能量因素時，顯而易見的是會產生很大的延遲現象。這篇論文的第二部分提出一個新穎的multi-path routing algorithm 使用在無線感測器網路環境下。這裡提供了稱為Hop-Count based Routing (HCR) algorithm，此方法同時考慮了能量消耗與傳送的延遲。我們採用了hop count vector (HCV) 來幫助routing decision。另外，加上pruning vector (PV) 可以更加提昇routing performance。我們提出的演算法也提供了maintenance mechanism以處理failed nodes帶來的影響。一個node的錯誤就會使得HCV不正確。所以需要一個有效率的更正演算法。我們提出Aid-TREE (A-TREE) 的演算法可以很容易地採用restricted flooding，這種更正機制比full-scale flooding來得有效率。最後，我們研究了failed nodes對整個網路拓樸的影響，並且提出一個叫做lazy-grouping的演算法，來增進HCR的穩定度。

Wireless sensor network is a rapidly growing discipline with new technologies emerging, and new applications under development. Wireless sensor nodes deposited in various places can measure light, humidity, temperature, etc. and can therefore be used in applications such as security surveillance, environmental monitoring and wildlife watching. A communication channel is generally shared among many sensor nodes in wireless sensor networks. Such sharing reduces the network performance due to aggravated radio interference. At same time it raises energy consumption since packet retransmission is needed when interference occurs. Moreover, the energy consumption could be skyrocket if we don’t limit number of active sensor nodes for the data relays. Topology control can be utilized to address the above problems. Topology control will remove unnecessary transmission links by shutting down some of redundant nodes. Nevertheless topology control will still guarantee network connectivity in order to deliver data efficiently in a wireless sensor network. This thesis proposes two topology control schemes, namely SmartBone and HCR (Hop Count based Routing) separately, in wireless sensor networks. The first scheme in the thesis, SmartBone, proposes a novel mechanism to construct a backbone. Some nodes are chosen as coordinators (i.e. backbone nodes) in the backbone construction process. All nodes then can directly or indirectly communicate with other nodes via these coordinators. The coordinators form the backbone, and the non-selected nodes can perform sleeping schedule or turn off the radio to save the energy consumption. Another potential application model for a sensor network is transmitting packets efficiently from Single-Source to Multi-Sinks. It is to gather data from a single sensor node and deliver it to multiple clients who are interested in the data. This in wireless sensor network model is called Single-Source to Multi-Sinks (SSMS). The difficulty of handling the model is in how to arrange the minimum-cost transmission path. The second proposed scheme in the thesis, HCR, simultaneously addresses energy-cost and end-to-end delay to solve the above problem.

中文摘要 i
Abstract iii
誌謝 v
Table of Content vi
List of Figures viii
List of Tables x
Chapter 1: Introduction 1
Chapter 2: SmartBone: An Energy-Efficient Smart Backbone Construction in Wireless Sensor Networks 1
2.1 Introduction 1
2.2 SmartBone Design 5
2.2.1 Neighborhood Information Collection 7
2.2.2 Flow-Bottleneck Preprocessing 7
2.2.3 BackBone Selecting Procedure 13
2.3 Performance Simulation and Analysis 19
2.3.1 Performance metrics 20
2.3.2 Simulation Environment 20
2.3.3 Simulation Results 21
2.3.4 Sensitivity of thresholds 25
Chapter 3: Minimum-Delay Energy-Efficient Source to Multisink Routing in Wireless Sensor Networks 27
3.1 Introduction 27
3.2 HCR Algorithm 29
3.2.1 Hop Count Vector 29
3.2.2 Next Hop Selection 33
3.2.3 Extended Set Cover with Load-Balance 35
3.2.4 Prune Vector 37
3.3 HCR Maintenance Scheme 40
3.3.1 Flooding Scope 40
3.3.2 Aid-TREE 41
3.4 Robustness Improvement 44
3.5 Simulation Results and Performance Analysis 47
3.5.1 Performance metrics 47
3.5.2 Simulation Scenarios 49
3.5.3 Performance Result and Analysis 51
Chapter 4: Conclusions 63
Appendix: 65
Reference: 68

[1] R. Rajaraman, “Topology control and routing in ad hoc networks: a survey,” ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) News, June 2002.
[2] D. Estrin, et. Al., http://nesl.ee.ucla.edu/tutorials/mobicom02
[3] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, “Topology management for sensor networks: exploiting latency and density,” International Symposium on Mobile Ad Hoc Networking & Computing Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, 2002.
[4] M. Min, F. Wang, D. Du, and P. M. Pardalos, “A Reliable Virtual Backbone Scheme in Mobile Ad-Hoc Networks,” IEEE Mobile Ad hoc and Sensor Systems, 2004.
[5] F. Heide, C. Schindelhauer, K. Volbert, and M. Grünewald, “Energy, congestion and dilation in radio networks,” In Proc. of the fourteenth annual ACM symposium on Parallel algorithms and architectures, 2002.
[6] H. Liu and R. Gupta, “Selective Backbone Construction for Topology Control,” First IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp. 41-50, Fort Lauderdale, Florida, October 2004.
[7] Y. Wang, W. Wang, and X. Y. Li, “Distributed low-cost backbone formation for wireless ad hoc networks,” In Proc. of the 6th ACM international symposium on Mobile ad hoc networking and computing, 2005.
[8] L. Bao, J. J. Garcia-Luna-Aceves, “Topology management in ad hoc networks,” In Proc. of the 4th ACM international symposium on Mobile ad hoc networking & computing, 2003
[9] K. Alzoubi, X.-Y. Li, Y. Wang, P.-J. Wan and O. Frieder, “Geometric Spanners for Wireless Ad Hoc Networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 5, pp. 408-421, 2003.
[10] C. Sengul and R. Kravets, “TITAN: on-demand topology management in ad hoc networks,” ACM SIGMOBILE Mobile Computing and Communications, 2004.
[11] The network simulator – NS-2, http://www.isi.edu/nsnam/ns.
[12] C. C. Shen, C. Srisathapornphat, R. Liu, Z. Huang, C. Jaikaeo, and E. L. Lloyd, “CLTC: A Cluster-Based Topology Control Framework for Ad Hoc Networks,” IEEE Transactions on Mobile Computing, 2004.
[13] S. Srivastava and R. K. Ghosh, “Cluster based routing using a k-tree core backbone for mobile ad hoc networks,” In Proc. of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, 2002.
[14] B. Das and V. Bharghavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” In Proc. of International Conference on Communication, pp. 376-380, 1997.
[15] J. Wu and H. L. Li, “On calculating connected dominating set for efficient routing in ad hoc wireless networks,” In Proc. of the 3rd ACM international workshop on Discrete algorithms and methods for mobile computing and communications, pp. 7-14, 1999.
[16] I. Stojmenovic, M. Seddigh, and J. Zunic, “Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks,” In Proc. of IEEE Hawaii International Conference on System Sciences, January 2001.
[17] X. Cheng, X. Huang, D. Li and D.-Z.- Du, “Polynomial-Time Approximation Scheme for Minimum Connected Dominating Set in Ad Hoc Wireless Networks,” Technical Report TR02-003, Computer Science and Engineering Department, Univ. of Minnesota, 2002.
[18] P.-J. Wan, K. M. Alzoubi and O. Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” In Proc. of the IEEE Conference on Computer Communications (INFOCOM), pp. 1597-1604, 2002.
[19] M. Cardei, X. Cheng, X. Cheng, and D.-Z. Du, “Connected Domination in Multihop Ad HocWireless Networks,” 6th International Conference on Computer Science and Informatics, March 2002, North Carolina, USA.
[20] G. J. Pottie and W. Kaiser, “Wireless integrated network sensors,” Communications of the ACM, 43(5):51–58, May 2000.
[21] R. Ramanathan, R. Rosales-Hain, “Topology Control of Multihop Wireless Networks using Transmit Power Adjustment,” In Proc. of the IEEE Conference on Computer Communications (INFOCOM), 2000.
[22] M. Kubisch, H. Karl, A. Wolisz, L. C. Zhong, and J. Rabaey, “Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks,” Wireless Communications and Networking (WCNC'03), pp. 558-563, March 2003.
[23] H. Koskinen, J. Karvo and O. Apilo, “On Improving Connectivity of Static Ad-Hoc Networks by Adding Nodes”, In Proc. of The Fourth annual Mediterranean workshop on Ad Hoc Networks (Med-Hoc-Net), 2005.
[24] S. M. Das, H. Pucha, and Y. Charlie Hu, “MicroRouting: A Scalable and Robust Communication Paradigm for Sparse Ad Hoc Networks,” In Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), 2005.
[25] R. Meraihi, G. Le Grand, N. Puech, “Improving ad hoc network performance with backbone topology control,” In Proc. of IEEE Vehicular Technology Conference (VTC), pp. 26-29, Sep. 2004.
[26] H. Kim, T. Abdelzaher, and W. Kwon, “Minimum Energy Asynchronous Dissemination to Mobile Sinks in Wireless Sensor Networks,” SenSys'03, LA, CA, pp. 193-204, Nov. 2003.
[27] W. R. Heinzelman, J. Kulik, and H. Balakrishnan “Adaptive Protocols for Information Dissemination in wireless Sensor Networks,” In Proc. of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’99), pp. 174-185, August 15-20, 1999.
[28] D. Estrin, L. Girod, G. Pottie, and M. Srivastava, “Instrumenting the World with Wireless Sensor Networks,” International Conference on Acoustics, Speech and Signal Processing (ICASSP 2001), pp. 2033-2036, May 2001.
[29] C. H. Ke, et. Al., “Merged Multi-path Routing: Two Energy-Efficient Strategies in Wireless Sensor Networks,” In Chinese, In Proc. of National Computer Symposium (NCS) in Taiwan, Dec. 2005.
[30] F. Heide, C. Schindelhauer, K. Volbert, and M. Grünewald, “Energy, congestion and dilation in radio networks,” In Proc. of the fourteenth annual ACM symposium on Parallel algorithms and architectures, 2002.
[31] D. S. Johnson, “Approximation algorithms for combinatorial problems,” J. Comput. System Sci. 9, 256-278, 1974.
[32] D. Estrin, R. Govindan, J. Heidemann and S. Kumar, “Next Century Challenges: Scalable Coordination in sensor Networks,” ACM/IEEE International Conference on Mobile Computing and Networks (MobiCom ’99), Seattle, Washington, pp. 263-270, August 1999.