由於無線感測網路(wireless sensor networks, WSNs)之實務應用，受現實中各式各樣的地理環境，使得"洞"的產生及位置是很難避免，也很難去得知的。所以在進行封包傳送路由建置時，傳送此路由會受到因感測網路中有“洞”的存在而造成封包在傳遞時，可能因此延遲甚至遺失。為了解決這些問題，我提出一個新的路由方法(RNG Hole Avoiding Routing protocol, RNGHAR)，可以塑造出在無線感測網路中的"洞"，使得在進行事件封包傳送時，如果會遇到"洞"時，可事先得知、並避開經過洞的路徑。本篇論文提出 RNGHAR這個方法，是利用關聯鄰近圖(relative neighborhood graph, RNG)的路由演算法，勾勒出在無線感測網路中的"洞"，進而可以收集到"洞"的資訊，接著在進行事件封包傳送時，利用此資訊建構一條避開"洞"的路由，因而達到事件封包可事先避開"洞"，且可沿著最短路徑，由來源的位置順利傳送到目的地。由模擬結果顯示，我所提出的方法在平均節點數、封包傳送成功率以及能量的消耗上比起現存的方法都來的好。

In wireless sensor networks, “holes” are hardly to know its location and avoid either because of various actual geographical environments. A hole can be dynamically formed due to unbalanced deployment, failure or power exhaustion of sensors, animus interference, or physical barriers such as buildings or mountains. Hence, we hope to propose the RNG Hole Avoiding Routing protocol, RNGHAR which can model “holes” existed in wireless sensor network and a event packets can avoid meeting a “hole” in advance instead of bypassing a hole when it meets the hole.

    This thesis proposes a novel algorithm RNGHAR which uses RNG (relative neighborhood graph) modeling holes then we can collect hole information in order to construct in advance hole avoiding routing path. Hence event packets will be guided to overcome the hole and move along the shortest path from source node to the sink node. Simulation studies show that my proposed method achieve good performance in terms of average hop count, packet delivery success rate and power consumption in comparison with the existing protocols.

Contents
誌謝                                    
中文摘要                                
Abstract                                
List of Figures                                III     
List of Tables                                 V
1 Introduction …………………………………………1
2 Related Work ………………………………………..4
2.1     Non-Prediction Approaches…………………………..5
2.2     Prediction Approaches……………………………..…7
2.3     Summary........................................12
3 The RNG Hole Avoiding Routing protocol…….....14
3.1     Network Environments and Assumption…………....16
3.2     Three Phases of Protocol……………………………17
3.2.1 Relative Neighborhood Graph Construction Phase…..18
3.2.2 Hole Detection Phase…………………………………22
3.2.2.1   Circle Detection Step………………………….…22
3.2.2.2   Hole Estimation Ste……………………...………30
3.2.2.3   Hole Boundary Step………………………...……33
3.2.3 Create Hole Avoiding Routing Path Phase……………38
4 Simulation Results and Analysis…………..………44
4.1      Simulation Environment………………….………..45
4.2      Results and Analysis……………………………….46
5 Conclusion and Future Work……………..……….51
5.1     Conclusion…………………………………………..51
5.2     Future Work…………………………………………52
References ……………………………………………53
Appendix A. Conference Version …………………...58


List of Figures

Figure 1-1: An example of a hole……………………………………………………..2
Figure 2-1: Example of GPRS………………………………………………………...5
Figure 2-2: Example of TPGF………………………………………………………....6
Figure 2-3: The major disadvantage of PAGER………………………………………7
Figure 2-4: Example of Black Region…………………………………………………9
Figure 2-5: (a) TENT rule’s criterion (b) Example of BOUNDHOLE……………...10
Figure 2-6: An Example of HAIR Protocol………………………………………….12
Figure 2-7: The edge (u, v) does not belong RNG because of w…………………….13
Figure 3-1: Example of sensor network environment………………………………..17
Figure 3-2: Three Phases Process Flow Chart……………………………………….18
Figure 3-3: Example of RNG Graph Construct……………………………………...20
Figure 3-4: Relative Neighborhood Graph Construction Flow Chart……………….21
Figure 3-5: Hole Detection Flow Chart……………………………………………...22
Figure 3-6: Example of Wireless Sensor Network Framework……………………...23
Figure 3-7: RNG Graph of Constructed from Wireless Sensor Network Framework.24
Figure 3-8: Tree of diversion from RNG…………………………………………….29
Figure 3-9: Circle Detection Flow Chart……………………………………………..30
Figure 3-10: Concept of Hole Estimation…...……………………………………….32
Figure 3-11: Hole Estimation Flow Chart……………………………………………33
Figure 3-12: Example of Hole Boundary…………………………………………….37
Figure 3-13: Hole Boundary Flow Chart…………………………………………….38
Figure 3-14: Example of Related Location of Sink, Event and Hole………………...40
Figure 3-15: Example of Create Hole Avoiding Routing Path………………………42
Figure 3-16: Create Hole Avoiding Routing Path Flow Chart……………………….43
Figure 4-1: The Average Hops of RNGHAR and GPSR in Different Hole Size of Circular………………………………………………………………….47
Figure 4-2: The Comparison of Packet Delivery Success Rate of RNGHAR and GPSR Mechanism………………………………………………………48
Figure 4-3: Counterclockwise Direction of GPSR Right-Hand-Rule..........................49
Figure 4-4: The Comparison of Remaining Energy of Nodes on Boundary of Hole of RNGHAR and GPSR Mechanism............................................................50


List of Tables

Table 3-1: Node Information Table……………………………………..15
Table 3-2: Construction Packet………………………………………….18
Table 3-3: Circle Detection Packet…………………………………...…23
Table 4-1: Parameters for simulation……………………………….…...46

[1]M.A.M. Vieira, Jr. C.N. Coelho, Jr. D.C. da Silva, J.M. da Mata, “Survey on wireless sensor network devices,” Proceedings of the 2003 international conference on emerging technologies and factory automation, ETFA 2003. IEEE Digital Object Identifier 10.1109/ETFA. 2003.1247753, Volume 1, Page(s): 537 – 544, 16-19 Sept. 2003.

[2]J.N. Al-Karaki, A.E. Kamal, “Routing techniques in wireless sensor networks: a survey,” Proceedings of the 2004 international conference on wireless communications [see also IEEE Personal Communications], IEEE Digital Object Identifier 10.1109/MWC.2004.1368893, Volume 11, Issue 6, Page (s): 6 – 28, Dec. 2004.

[3]Nadeem Ahmed, S. Salil, Kanhere, Jha Sanjay, “The holes problem in wireless sensor networks: a survey,” ACM SIGMOBILE Mobile Computing and Communications Review, Volume 9, Issue 2, Page (s): 4 – 18, April 2005.

[4]Franz Aurenhammer, “Voronoi diagrams—a survey of a fundamental geometric data structure,” ACM Computing Surveys (CSUR), Volume 23, Issue 3, Page (s): 346 – 405, Sept. 1991

[5]J.W. Jaromczyk, G.T. Toussaint, “Relative neighborhood graphs and their relatives,” IEEE Digital Object Identifier 10.1109/5.163414, Volume 80, Issue 9, Page (s): 1502- 1517, Sept. 1992.

[6]Julien Cartigny, Francois Ingelrest, David Simplot-Ryl and Ivan Stojmenovi, “Localized LMST and RNG based minimum-energy broadcast protocols in ad hoc networks,” IRCICA/LIFL, Université de  Lille 1, INRIA Futurs, France SITE, University of Ottawa, Ottawa Ont., Canada K1N 6N5 Received 4 August 2003. Accepted 6 Sept. 2003. Available online 26 Nov. 2003. Page (s): 1- 16.

[7]S. Borbash, E. Jennings, “Distributed topology control algorithm for multihop wireless networks,” Proceedings of the 2002 international joint conference on neural networks, IJCNN 2002. IEEE Digital Object Identifier 10.1109/IJCNN.2002.1005497, Volume 1, Page (s): 355 – 360, 12-17 May 2002.

[8]Wang Ying-Hong, Tsai Chih-Hsiao, Mao Hung-Jen, Huang Kuo-Feng, “An Energy-Efficient Hierarchical Multiple-Choice Routing Path Protocol for wireless Sensor Networks Sensor Networks,” Proceedings of the 2006 international conference on ubiquitous and trustworthy computing. Volume 1, Page (s): 570 – 571, 05-07 June 2006.

[9]Shin Kee-Young, Song Junkeun, Kim Jin-Won, Yu Misun, Mah Pyeong- Soo, “REAR: Reliable Energy Aware Routing Protocol for Wireless Sensor Networks,” Proceedings of the 2007 9th international conference on advanced communication technology. IEEE Digital Object Identifier 10.1109/ICACT.2007.358410, Volume 1, Page (s): 525-530, 12-14 Feb. 2007.

[10]N. Ouferhat, A. Mellouk, “Optimal QoS and adaptatiw routing in Wireless Sensor Networks,” Proceedings of the 2006 2nd information and communication techngs, ICTTA 2006. Volume 2, Page (s): 2736– 2741, 24-28 April 2006.

[11]Brad Karp, H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the 6th annual international conference on Mobile computing and networking, MobiCom 2000. Page (s): 243 – 254, Aug. 2000.

[12]Shu Lei, Zhou Zhang- Bing, Manfred Hauswirth, Phuoc Danh Le, Yu Peng, Lin Zhang, “Transmitting streaming data in wireless multimedia sensor  networks with holes,” Proceedings of the 6th international conference on Mobile and ubiquitous multimedia, MUM 2007. Page (s): 24 – 33, Dec. 2007.

[13]Le Zou, Mi Lu, Zixiang Xiong, “PAGER: a distributed algorithm for the dead-end problem of location-based routing in sensor networks,” Proceedings of the 2004 13th international conference on computer communications and networks, ICCCN 2004. IEEE Digital Object Identifier 10.1109/ICCCN.2004.1401720, Page (s): 509 – 514.

[14]Qing Fang, Jie Gao, J. Leonidas Guibas, “Locating and bypassing holes is sensor networks,” Mobile Networks and Applications. Volume 11, Issue 2. Page (s): 187– 200, April 2006.  

[15]Jia Weijia, Wang Tian, Wang Guojun, Guo Minyi, “Hole Avoiding in Advance Routing in Wireless Sensor Networks,” Proceedings of the 2007 international conference on wireless communications and networking conference, WCNC 2007. IEEE Digital Object Identifier 10.1109/WCNC.2007.645, Page (s): 3519 – 3523, 11-15 March 2007.

[16]Yu Fucai, Lee Euisin, Choi Younghwan, Park Soochang, Lee Donghun, Ye Tian, Kim Sang-Ha, “A modeling for hole problem in wireless sensor networks,” Proceedings of the 2007 international conference on Wireless communications and mobile computing, IWCMC 2007. Page (s): 370 – 375, Aug. 2007.

[17]Yu Fucai, Lee Euisin, Choi Younghwan, Park Soochang, Lee Donghun, Ye Tian, Kim
Sang-Ha, “A Hole Geometric Modeling in Wireless Sensor Networks,” Proceedings of the 2007 international conference on wireless communications, networking and mobile computing, WiCom 2007. IEEE Digital ObjectIdentifier10.1109/WICOM.20
07.606, Page (s): 2432 – 2435, 21-25 Sept. 2007.

[18]Kun Bi, Kun Tu, Naijie Gu, Wan Lin Dong, Xiaohu Liu, “Topological Hole Detection in Sensor Networks with Cooperative Neighbors Systems and Networks Communication,” Proceedings of the 2006 international conference, ICSNC 2006. IEEE Digital Object Identifier 10.1109/ICSNC.2006.71, Page (s): 31 – 31, Oct. 2006.
	
[19]Stefan Funke, “Topological hole detection in wireless sensor networks and its applications,” Proceedings of the 2005 joint workshop on foundations of mobile computing, DIALM-POMC 2005. Page (s): 44 – 53, Sept. 2005.

[20]H. Sabbineni, K. Chakrabarty, “Location-aided flooding: an energy-efficient data dissemination protocol for wireless-sensor networks,” Computers. IEEE Digital Objecttransaction10.1109/TC.2005.8, Volume54, Issue 1, Page (s): 36 – 46, Jan. 2005.