無線感測網路(wireless sensor networks)中，良好的網路佈建方式與有效率的通訊協定，是無線感測網路中重要的議題，在近年來亦受到相當大的重視，本論文主要提出了高效的機器人感測器佈建演算法及高效的多頻道通訊協定，藉此提高無線感測網路的監測品質與傳輸效益。
首先，本論文針對感測器佈建議題進行探討，現存的佈建方法大都容易受到障礙物的影響，進而使機器人進入死巷或留下空洞。不同於現有的機器人佈建演算法，本論文所提出機器人佈建無線感測網路的演算法，僅以少量的記憶體成本讓機器人可以克服任何複雜的障礙物，並將適量的感應器佈建於監控區中以達到縮短佈建時間、節省感測器硬體成本及全區覆蓋等目的。此外，機器人僅需與已佈建的感測器進行少量通訊，使大多數已被佈建的感測器可進入省電狀態。
而感測器佈建後的通訊亦是相當重要的工作，近年來，發展多頻道媒體存取協定已受到極大的關注與討論，並被認為是開發頻寬利用率的有效方法。在發展多頻道通訊協定時所遭遇最大的挑戰便是主機會面問題(Rendezvous Problem)與多頻道隱藏節點問題(Multi-Channel Hidden Terminal Problem)。為解決會面問題，部分研究的作法是讓所有主機在特定的頻道中會面，以便進一步協調資料傳輸該使用的頻道。然而，此種作法將可能產生多頻道隱藏主機節點問題。另外，也有部分研究的作法，讓所有主機週期性地在特定頻道的ATIM Window聚集，以協調資料傳輸的頻道，但此種作法會造成其它頻道ATIM Window的頻寬利用率降低。為解決多頻道隱藏主機節點問題並改善多頻道傳輸時的頻寬利用率，本論文提出一多頻道MAC協定(SMC-MAC)，透過創新的階梯式頻道模型，將各頻道的控制區間錯開，並透過頻道對應函式，將各結點分散在不同的頻道中，藉此達成在不增加硬體成本下，有效解決多頻道的主機會面與多頻道隱藏主機節點問題，並提高頻寬利用率，進而提升網路傳輸效能。
我們透過大量的實驗與模擬，證明了本論文所提出的機器人佈建演算法具有高佈點率、低電力成本，且可以在複雜的監測區域中達到全區覆蓋。此外，本論文所提出的多頻道MAC協定可有效增加頻寬利用率，並提昇網路效能。

In wireless sensor networks (WSNs), the deployment and communication issues are very important and have received much attention in the last decade. This thesis mainly proposes efficient deployment and communication algorithms for improving the operating efficiencies of the wireless sensor networks. 
First of all, the goal of developing a deployment algorithm is to deploy sensors in a given monitoring region in a way of low hardware cost and high coverage quality. In recent years, several mechanisms were developed for robot to deploy sensors efficiently. Their performances highly depend on the obstacles since their results are always inefficient when the Dead-End problem is encountered. Therefore, it has been the key challenge for developing a robot deployment mechanism to overcome the Dead-End problem and satisfy the full coverage requirement by using minimal number of sensors. This study proposes an Impasse-aware robot deployment algorithm, called IAD. The proposed IAD mainly consists of basic deployment rules and Dead-End handling rules. The basic deployment rules try to use minimal number of sensors such that the full coverage purpose can be achieved. Moreover, the proposed Dead-End handling rules can efficiently deal with the Dead-End problem. Extensive experiment studies show that our proposed IAD has better performance than existing robot deployment mechanisms in terms of coverage ratio, energy efficiency, deployment path length as well as required stack space.
In addition to investigating the deployment issue, this thesis also investigates the communication issues in WSNs. The Multi-channel media access control (MAC) protocols can increase wireless network capacities. The rendezvous problem is the most frequently encountered challenge in developing multi-channel MAC protocols. Some studies have assumed that each device is equipped with one additional antenna; however, this increases the hardware cost. Other studies have divided the timeline of each channel into several beacon intervals. All stations are awake simultaneously on a predefined channel to enable rendezvous opportunities; however, this leads to low bandwidth utilization. This thesis also presents an efficient staggered multichannel MAC protocol (SMC-MAC) for ad hoc networks. By using a single antenna, the proposed SMC-MAC applies a staggered channel model with a home channel concept for exploiting multi-channel bandwidth resources. Performance results reveal that the proposed SMC-MAC outperforms existing multi-channel MAC protocols in terms of network throughput, control packet collision ratio, packet delay time, packet discarding, packet loss ratio, control overhead, and robustness.
In summary, this thesis proposes robot deployment algorithm and MAC protocols for improving the efficiencies of the WSNs. Extensive experiment studies show that our proposed IAD has better performance than existing robot deployment mechanisms in terms of coverage ratio, energy efficiency, deployment path length as well as required stack space. In addition, the performance results reveal that the proposed SMC-MAC outperforms existing multi-channel MAC protocols in the network throughput, control packet collision ratio, packet delay time, packet discarding, packet loss ratio, control overhead, and robustness.

Contents	V
List of Figures	VII
List of Tables	XI
Chapter 1 Introduction	1
Chapter 2 Related Work	8
2.1 Robot Deployment Mechanism	8
2.2 Multi-Channel MAC Protocol	12
Chapter 3 The Impasse-Aware Deployment (IAD) Algorithm	16
3.1 Network Environment and Problem Statement	16
3.1.1 System Model	16
3.1.2 Problem statement	17
3.2 Optimal Deployment Mechanism without Considering Obstacle	21
3.2.1 Moving Direction Rule	21
3.2.2 Horizontal and Vertical Movement Rules	23
3.3 Impasse-Aware Deployment (IAD) Algorithm	24
3.3.1 The Detail Design of IAD Algorithm	25
3.3.2 The State Diagram of IAD	30
3.3.3 The Algorithm of IAD	32
3.4 Analysis of Deployment Trajectories	34
3.5 Performance Evaluation	39
3.5.1 Coverage Ratio	42
3.5.2 x×y U-shape Obstacles	45
3.5.3 Energy Efficiency	48
3.5.4 Trajectory Path	51
3.5.5 Required Stack Space	52
3.5.6 Average Number of Deployed Sensors	55
3.5.7 Applied Frequency of Each Rule	57
3.6 Summary	59
Chapter 4 The Efficient Staggered Multi-Channel MAC (SMC-MAC) Protocol	60
4.1 Network Environment and Problem Statement	60
4.2 Staggered Channel Model and Frame Structure	63
4.2.1 Staggered Channel Model	63
4.2.2 Frame Structure	65
4.3 Proposed SMC-MAC Protocol	65
4.3.1 Rendezvous Mechanism	66
4.3.2 SMC-MAC Design	67
4.4 Performance Analysis	75
4.5 Performance Evaluation	81
4.5.1 Evaluation Environment	81
4.5.2 Network Throughput	83
4.5.3 Control Packet Collision Ratio	85
4.5.4 Packet Delay	86
4.5.5 Packet Discarding	88
4.5.6 Packet Loss Ratio	89
4.5.7 Control Overheads	90
4.5.8 Robustness	91
4.6 Summary	92
Chapter 5 Conclusions	94
References	96

List of Figures
Figure 1.1. The robot encounters a Dead-End problem	3
Figure 2.1. The disadvantage of the existing ORRD and OFPD robot deployment mechanisms	10
Figure 2.2. The robot deployment mechanisms by applied right-hand policy for reducing the impact of obstacles	10
Figure 2.3. The backward path of the robot when it encounters a Dead-End problem by applying IAD and BSA mechanisms	11
Figure 3.1. Optimal sensor deployment	20
Figure 3.2. The priorities of movement directions	22
Figure 3.3. An example illustrating the deployment trajectory by applying the proposed Moving Direction Rule	23
Figure 3.4. Horizontal and Vertical Movement Rules	24
Figure 3.5. An example to explain that the robot executes the proposed IAD algorithm	26
Figure 3.6. The state diagram of IAD Algorithm	31
Figure 3.7. A WSN deployed by applying the IAD and BSA algorithms	35
Figure 3.8. The obstacle is treated as a rectangle region to simplify the deployment efficiency analysis	36
Figure 3.9. The analysis of the performance improvement of the proposed IAD approach against the existing BSA approach in terms of path	39
Figure 3.10. Shapes of regular obstacles considered in the simulation	40
Figure 3.11. Generation of an irregular obstacle	42
Figure 3.12. Coverage ratio of different mechanisms	43
Figure 3.13. Coverage ratio of different mechanisms when the first Dead-End situation is encountered	44
Figure 3.14. Coverage ratio of different mechanisms at different evaluation time. The obstacles environment given in Fig. 3.10(f) is considered	45
Figure 3.15. Generation of x×y U-shape obstacles	46
Figure 3.16. Coverage ratio of different mechanisms. The experimental environment contains different number of square units	47
Figure 3.17. Deployment path length of different mechanisms and the analysis results. The experimental environment contains different number of square units	48
Figure 3.18. The comparison of the proposed IAD and existing BSA mechanisms in terms of EEI. The experimental environment contains different shapes of regular obstacles	50
Figure 3.19. The comparison of the proposed IAD and existing BSA mechanisms in terms of EEI. The experimental environment contains different number of irregular obstacles	50
Figure 3.20. The snapshots of robot’s backward paths by applying IAD and BSA mechanisms using the obstacle environment given in Fig. 3.10(f)	51
Figure 3.21. The snapshots of robot deployment by applying IAD and BSA using the scenario that contains six irregular obstacles	52
Figure 3.22. The comparison of the proposed IAD and existing BSA mechanisms in terms of required stack space. The experimental environment contains different shapes of regular obstacles	53
Figure 3.23. The comparison of the proposed IAD and existing BSA mechanisms in terms of required stack space. The experimental environment contains different number of irregular obstacles	53
Figure 3.24. The required stack space for handling each Dead-End problem by applying IAD and BSA mechanisms using the obstacle environment given in Fig. 3.10(f)	55
Figure 3.25. The comparison of the proposed IAD and existing BSA mechanisms in terms of the number of deployed sensors. The experimental environment contains different shapes of regular obstacles	56
Figure 3.26. The comparison of the proposed IAD and existing BSA mechanisms in terms of the number of deployed sensors. The experimental environment contains different number of irregular obstacles	57
Figure 3.27. Applied frequency of each rule proposed in IAD in the environment containing different shapes of regular obstacles	58
Figure 3.28. Applied frequency of each rule proposed in IAD in the environment containing different numbers of irregular obstacles	59
Figure 4.1. Proposed staggered channel model	64
Figure 4.2. Frame structure of the SMC-MAC	65
Figure 4.3. Illustration of Receiver Declaration Packet (RDP)	69
Figure 4.4. Illustration of Bitmap Synchronize Operations	73
Figure 4.5. Illustration of the bitwise logical AND operation	74
Figure 4.6. Performance analysis scenarios	76
Figure 4.7. Analysis of the performance improvement I(n) of SMC-MAC compared with the SPB approach	81
Figure 4.8. Influence of propagation models on the network throughput of SMC-MAC	83
Figure 4.9. Average network throughput of SMC-MAC and existing MAC protocols	84
Figure 4.10. Network throughput of SMC-MAC and existing MAC protocols	85
Figure 4.11. Control packet collision ratio of SMC-MAC and existing MAC protocols	86
Figure 4.12. Average packet delay of SMC-MAC and existing MAC protocols	87
Figure 4.13. Packet discarding characteristics of SMC-MAC and existing MAC protocols	89
Figure 4.14. Packet loss ratio of SMC-MAC and existing MAC protocols	90
Figure 4.15. Control overheads of SMC-MAC and existing MAC protocols	91
Figure 4.16. Robustness of SMC-MAC and existing MAC protocols	92

List of Tables
Table 2.1. Comparison of the main characteristics of the proposed IAD with existing related works	11
Table 2.2. Main characteristics of the proposed SMC-MAC and related protocols	14
Table 3.1. Simulation Parameters	40
Table 4.1. Simulation Parameters	82

[1]	R. V. Kulkarni, A.a Förster, and G. K. Venayagamoorthy, “Computational Intelligence in Wireless Sensor Networks: A Survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 1, pp. 68–96, Jan. 2011.
[2]	E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258–1276, Dec. 2013.
[3]	L. Liu and H. Ma, "On Coverage of Wireless Sensor Networks for Rolling Terrains," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 118–125, Jan. 2012.
[4]	X. Li, D. K. Hunter, and S. Zuyev, "Coverage Properties of the Target Area in Wireless Sensor Networks," IEEE Transactions on Information Theory, vol. 58, no. 1, pp. 430–437, Jan. 2012.
[5]	P. Zhang, I. Nevat, G. W. Peters, G. Xiao, and H.-P. Tan, “Event Detection in Wireless Sensor Networks in Random Spatial Sensors Deployments,” IEEE Transactions on Signal Processing, vol. 63, no. 22, pp. 6122–6135, Nov. 2015.
[6]	A. V. Savkin, F. Javed, and A. S. Matveev, "Optimal Distributed Blanket Coverage Self-Deployment of Mobile Wireless Sensor Networks," IEEE Communications Letters, vol. 16, no. 6, pp. 949–951, Jun. 2012.
[7]	X. Li, H. Frey, N. Santoro, and I. Stojmenovic, "Strictly Localized Sensor Self-Deployment for Optimal Focused Coverage," IEEE Transactions on Mobile Computing, vol. 10, no. 11, pp. 1520–1533, Nov. 2011.
[8]	R. C. Luo and O. Chen, "Mobile Sensor Node Deployment and Asynchronous Power Management for Wireless Sensor Networks," IEEE Transactions on Industrial Electronics, vol. 59, no. 5, pp. 2377–2385, May 2012.
[9]	F. J. Cintrón, K. Pongaliur, M. W. Mutka, L. Xiao, J. Zhao, and N. Xi, "Leveraging Height in a Jumping Sensor Network to Extend Network Coverage," IEEE Transactions on Wireless Communications, vol. 11, no. 5, pp. 1840–1849, May 2012.
[10]	Y. Song, B. Wang, Z. Shi, K. R. Pattipati, and S. Gupta, “Distributed Algorithms for Energy-Efficient Even Self-Deployment in Mobile Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 5, pp. 1035–1047, May 2014.
[11]	H. Mahboubi, K. Moezzi, A. G. Aghdam, K. S.-Pour, “Distributed Deployment Algorithms for Efficient Coverage in a Network of Mobile Sensors With Nonidentical Sensing Capabilities,” IEEE Transactions on Vehicular Technology, vol. 63, no. 8, pp. 3998–4016, Oct. 2014.
[12]	Z. Liao, J. Wang, S. Zhang, J. Cao, and G. Min, “Minimizing Movement for Target Coverage and Network Connectivity in Mobile Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 26, no. 7, pp. 1971–1983, Jul. 2015.
[13]	T.-Y. Lin, H. A. Santoso, and K.-R. Wu, “Global Sensor Deployment and Local Coverage-Aware Recovery Schemes for Smart Environments,” IEEE Transactions on Mobile Computing, vol. 14, no. 7, pp. 1382–1396, Jul. 2015.
[14]	M. A. Batalin and G. S. Sukhatme, “The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment,” IEEE Transactions on Robotics, vol. 23, no. 4, pp. 661–675, Aug. 2007.
[15]	C. Y. Chang, C. T. Chang, Y. C. Chen and H. R. Chang, “Obstacle-Resistant Deployment Algorithms for Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 58, no. 6, pp. 2925–2941, Jul. 2009.
[16]	C. Y. Chang, J. P. Sheu, Y. C. Chen, and S. W. Chang, “An Obstacle-Free and Power-Efficient Deployment Algorithm for Wireless Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics--Part A: Systems and Humans, vol. 39, no. 4, pp. 795–806, Jul. 2009.
[17]	E. González, O. Álvarez, Y. Díaz, C. Parra, and C. Bustacara, “BSA: A Complete Coverage Algorithm,” IEEE ICRA, pp. 2040–2044, Barcelona, Spain, Apr. 2005.
[18]	C.-H. Ou and W.-L. He, “Path Planning Algorithm for Mobile Anchor-Based Localization in Wireless Sensor Networks,” IEEE Sensors Journal, vol. 13, no. 2, pp. 466–475, Feb. 2013.
[19]	J. Rezazadeh, M. Moradi, A. S. Ismail, and E. Dutkiewicz, “Superior Path Planning Mechanism for Mobile Beacon-Assisted Localization in Wireless Sensor Networks,” IEEE Sensors Journal, vol. 14, no. 9, pp. 3052–3064, Sep. 2014.
[20]	P. Levis, N. Lee, M. Welsh, and D. Culler, “TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications,” ACM SenSys, pp. 126–137, Los Angeles, USA, Nov. 2003.
[21]	J. Hill and D. Culler, “A Wireless Embedded Sensor Architecture for System-Level Optimization,” Technical Report, U.C. Berkeley, 2002.
[22]	G. T. Sibley, M. H. Rahimi, and G. S. Sukhatme, “Robomote: A tiny mobile robot platform for large-scale sensor networks,” IEEE ICRA, pp. 1143–1148, Washington, D.C., May 2002.
[23]	K. Sakai, M.-T. Sun, W.-S. Ku, T. H. Lai, and A. V. Vasilakos, “A Framework for the Optimal k-Coverage Deployment Patterns of Wireless Sensors,” IEEE Sensors Journal, vol. 15, no. 12, pp. 7273–7283, Dec. 2015.
[24]	IEEE Standard for Information Technology, Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LRWPANs), IEEE Std, Sep. 2006.
[25]	J. Mo, H. S. W. So, and J. Walrand, “Comparison of Multichannel MAC Protocols,” IEEE Transactions on Mobile Computing, vol. 7, no. 1, pp. 50–65, Jan. 2008.
[26]	J. So and N. Vaidya, “Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using A Single Transceiver,” ACM MobiHoc, pp. 222–233, Tokyo, Japan, May 2004.
[27]	J. Zhang, G. Zhou, C. Huang, S. H. Son, and J. A. Stankovic, “TMMAC: An Energy Efficient Multi-Channel MAC Protocol for Ad Hoc Networks,” IEE ICC, pp.3554–3561, Glasgow, Scotland, Jun. 2007.
[28]	W. T. Chen, J. C. Liu, T. K. Huang, and Y. C. Chang, “TAMMAC: An Adaptive Multi-Channel MAC Protocol for MANETs,” IEEE Transactions on Wireless Communications, vol. 7, no. 11, pp. 4541–4545, Nov. 2008.
[29]	J. Lee, J. Mo, T. M. Trung, J. Walrand, and H. S. W. So, “Design and Analysis of a Cooperative Multichannel MAC Protocol for Heterogeneous Networks,” IEEE Transactions on Vehicular Technology, vol. 59, no. 7, pp. 3536–3548, Sep. 2010.
[30]	S. R. Singh and M. Motani, “Cooperative Multi-Channel Access for 802.11 Mesh Networks,” IEEE Journal on Selected Areas in Communications, vol. 30, no. 9, pp. 1684–1693, Oct. 2012.
[31]	A. Jeng, R. Jan, C. Li, and C. Chen, “Release-Time-Based Multichannel MAC Protocol for Wireless Mesh Networks,” Computer Networks, vol. 55, no. 23, pp. 2176–2195, Jun. 2011.
[32]	T. Luo, M. Motani, and V. Srinivasan, “Energy-Efficient Strategies for Cooperative Multichannel MAC Protocols,” IEEE Transactions on Mobile Computing, vol. 11, no. 4, pp. 553–566, Apr. 2012.
[33]	Z. Zhou, Z. Peng, J. H. Cui, and Z. Jiang, “Handling Triple Hidden Terminal Problems for Multichannel MAC in Long-Delay Underwater Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 11, no. 1, pp. 139–154, Jan. 2012.
[34]	Y. Liu, L. X. Cai, and X. Shen, “Spectrum-Aware Opportunistic Routing in Multi-Hop Cognitive Radio Networks,” IEEE Transactions on Mobile Computing, vol. 30, no. 10, pp. 1958–1968, Nov. 2012.
[35]	F. Hou, L. X. Cai, X. (Sherman) Shen, and J. Huang, “Asynchronous Multichannel MAC Design With Difference-Set-Based Hopping Sequences,” IEEE Transactions on Vehicular Technology, vol. 60, no. 4, pp. 1728–1739, May. 2011.
[36]	VINT Group, “UCB/LBNL/VINT Network Simulator ns (version 2),” available: http://www.isi.edu/nsnam/ns
[37]	MW-Node Path for NS2 to Support Multiple Interfaces & Multiple Channels, available: http://www.q2s.ntnu.no/~paquerea/ns.php
[38]	R. Gusella, “Characterizing the Variability of Arrival Processes with Indexes of Dispersion,” IEEE Journal on Selected Areas in Communications, vol. 9, no. 2, pp. 203–211, Feb. 1991.
[39]	C. Dovrolis, P. Ramanathan and D. Moore, “Packet-Dispersion Techniques and a Capacity-Estimation Methodology,” IEEE/ACM Transactions on Networking, vol. 12, no. 6, pp. 963–977, Dec. 2004.
[40]	Susanna S. Epp, Discrete Mathematics with Applications, Brooks Cole, Dec. 2003.
[41]	D. N. M. Dang, C. S. Hong, and S. Lee, “A Hybrid Multi-Channel MAC Protocol for Wireless Ad Hoc Networks,” Wireless Networks, vol. 21, no. 2, pp. 387–404, Feb. 2015.
[42]	S. Debroy, S. De, and M. Chatterjee, “Contention Based Multichannel MAC Protocol for Distributed Cognitive Radio Networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 12, pp. 2749–2762, Dec. 2014.
[43]	G. Y. Chang, W. H. Teng, H. Y. Chen, and J. P. Sheu, “Novel Channel-Hopping Schemes for Cognitive Radio Networks,” IEEE Transactions on Mobile Computing, vol. 13, no. 2, pp. 407–421, Feb. 2014.
[44]	C. M. Chao and H. C. Tsai, “A Channel-Hopping Multichannel MAC Protocol for Mobile Ad Hoc Networks,” IEEE Transactions on Vehicular Technology, vol. 63, no. 9, pp. 4464–4475, Nov. 2014.
[45]	K. H. Almotairi and X. S. Shen, “A Distributed Multi-Channel MAC Protocol for Ad Hoc Wireless Networks,” IEEE Transactions on Mobile Computing, vol. 14, no. 1, pp. 1–13, Jan. 2015.