淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2306201121021000
中文論文名稱 延長無線感測網路運作時間之繞徑演算法
英文論文名稱 Lifetime Based Routing Algorithm in Emergency Object Tracking
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 99
學期 2
出版年 100
研究生中文姓名 黃文發
研究生英文姓名 Wen-Fa Huang
學號 896410106
學位類別 博士
語文別 英文
口試日期 2011-06-14
論文頁數 43頁
口試委員 指導教授-蔡憶佳
委員-謝孫源
委員-林慶昌
委員-林慧珍
委員-顏淑惠
委員-蔡憶佳
中文關鍵字 中介值  感測網路  多重路徑演算法 
英文關鍵字 Betweenness  Sensor network  Routingalgorithm 
學科別分類 學科別應用科學資訊工程
中文摘要 本論文主要提出一個適於用於感測網路中尋找路徑之演算法,因組成感測網路的基本儲電子設備(簡稱感測節點)設計上都是以體積越小越好, 所以此電子設備所配置電池電量也相對的比較少,過去設計適用於感測網路之尋找路徑演算法相關論文也以節省設備電量消耗為主, 以此目的設計之路徑演算法主要分成兩方面發展。一、針對感測節點不傳輸資料時可以休眠進入低電量消耗,需傳輸資料時感測節點則進入原本正常耗電量得傳輸模式。二、不同感測節點傳輸至相同目的之感測節點時,若傳輸路徑中若有經過相同感測節點,則這些感測節點會等待不同來源的資料並合併後統一傳送。
現今基於感測網路上之應用種類繁多,因此發展新式設計尋找路徑演算法概念時會依據應用特性而設計。本篇論文是應用於偵測移動物體位置並即時傳送回應資料之感測網路而設計的尋找路徑之演算法,此種感測網路的應用設計有兩項特徵,一為感測節點不設計為可以進入休眠模式降低迷失偵測移動物體位置的功能,另一則是符合即時送回應資料而不採用中途節點延遲等待資料合併。此尋找路徑之演算法設計時會依據網路結構特性發展多條路徑傳輸資料,最後經由改變路徑傳輸資料而平衡每個感測節點耗電量, 避免感測節點喪失偵測與傳輸資料的功能。
英文摘要 Sensor networks have many applications, a typical setting is in nature environment monitoring, such as forest fire, tsunami, and earthquake. In order to be easily deployed in this environment, sensor device is design to have small form factor, and as lightweight as possible, thus, its battery capacity is limited. The issue of battery capacity is more important when applied in tracking moving objects, and when real time response of the system is critical where the routing algorithm do not need to perform data aggregation. This paper proposed a routing algorithm for tracking objects and perform emergency reporting when a situation occurred and at the same time reducing total energy consumption and thus prolonging the system lifetime. Our algorithm is called sensor on demand betweenness vector(SOBV). This algorithm is a multipath routing algorithm based on the characteristics of network topology.
論文目次 Chinese Abscract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I
English Abscract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Sensor network system design . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Node Deployment . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Energy Conservation . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Time Synchronization . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Sensor Network Routing Algorithm Designed . . . . . . . . . . . . . . 6
2 Sensor Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Address Centric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Data Centric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Location-based Protocol . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Hierarchical Protocol . . . . . . . . . . . . . . . . . . . . . . . 12
3 Network Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1 Betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Betweenness and Network Size . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Betweenness and Network Connectivity . . . . . . . . . . . . . . . . . 17
3.4 Local Betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Betweenness Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1 Packet Format of AODV and BODV . . . . . . . . . . . . . . . . . . 21
4.2 Path Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Data Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.4 Path Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1 Routing algorithm Simulation . . . . . . . . . . . . . . . . . . . . . . 30
6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Appendix A: Betweenness and Network Size . . . . . . . . . . . . . . . . . . . 38
Appendix B: Betweenness and Network Connectivity . . . . . . . . . . . . . . 41

List of Figures
1.1 Components of a sensor node. . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sensor network architecture. . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Taxonomy of approaches to energy savings in sensor networks. . . . . 4
2.1 Address-centric routing protocol: multiple sources send difference
data through difference path to a destination d1. . . . . . . . . . . . . 7
2.2 Data-centric protocol: multiple source send difference data through
same path to destination d1. . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 AODV finds routing path, source will broadcast messages to the
neighbor nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 SPIN protocol: ADV is advertisement message, REQ is request the
data message. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 GAF: source s selects the nearest node b from sink node by using
GPS to pass data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 LEAH: the black nodes are cluster head, each node in local cluster
will transmit messages to the cluster head. . . . . . . . . . . . . . . . 12
3.1 Number of shortest path between node s and d passes through node i. 15
3.2 Coordinate in grid area. . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Betweenness distribution at network size 200-1000. . . . . . . . . . . 17
3.4 Betweenness distribution at transmission range 02-1. . . . . . . . . . 18
3.5 The number of control message from node s to d passed through node i. 19
4.1 (a) AODV Request Message Format. (b) AODV Reply Message Format.
(c) BODV Reply Message Format. . . . . . . . . . . . . . . . . 22
4.2 Record reply message approach. . . . . . . . . . . . . . . . . . . . . . 22
4.3 Record reply message approach. . . . . . . . . . . . . . . . . . . . . . 23
4.4 Routing path build by SOBV routing algorithm. . . . . . . . . . . . . 24
5.1 Betweenness distribution. N=500. X-axis is betweenness of node. . . 29
5.2 The average shortest path of random. Number of nodes is 300-1000 . 30
5.3 Status of residual battery capacity of AODV, battery capacity is 500
units. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.4 Status of residual battery capacity of SOBV, battery capacity is 500
units. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.5 X-axis shows transmission times. Y-axis illustrates number of dead
node. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
A.1 Betweenness distribution at network size 200. . . . . . . . . . . . . . 38
A.2 Betweenness distribution at network size 400. . . . . . . . . . . . . . 39
A.3 Betweenness distribution at network size 600. . . . . . . . . . . . . . 39
A.4 Betweenness distribution at network size 800. . . . . . . . . . . . . . 40
A.5 Betweenness distribution at network size 1000. . . . . . . . . . . . . . 40
B.1 Betweenness distribution at transmission range 0:2. . . . . . . . . . . 41
B.2 Betweenness distribution at transmission range 0:4.. . . . . . . . . . . 42
B.3 Betweenness distribution at transmission range 0:6. . . . . . . . . . . 42
B.4 Betweenness distribution at transmission range 0:8. . . . . . . . . . . 43
B.5 Betweenness distribution at transmission range 1. . . . . . . . . . . . 43

List of Tables
3.1 Parameters of network size experiment . . . . . . . . . . . . . . . . . 15
3.2 Parameters of network connectivity experiment . . . . . . . . . . . . 17
4.1 Notation of SOBV routing algorithm . . . . . . . . . . . . . . . . . . 20
4.2 SOBV routing algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 SOBV routing table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.4 Notation of SOBV routing path . . . . . . . . . . . . . . . . . . . . . 25
4.5 Transmission algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6 Lotto function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.1 Parameters of simulation . . . . . . . . . . . . . . . . . . . . . . . . . 31
參考文獻 [1] J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer Networks, Vol. 52, Issue 12, pp. 2292-2230, 2008.
[2] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, Vol. 38, Issue 4, pp. 393-422, 2002.
[3] T. Arampatzis, J. Lygeros and S. Manesis, “A survey of applications of wireless sensors and wireless sensor networks,” In Proc. 13th Mediterranean Conference on Control and Automation, pp. 719-724, Limassol, Cyprus, June 27-29, 2005.
[4] G. Anastasi, M. Conti, M. Francesco and A. Passarella, “Energy conservation in wireless sensor networks: A survey,” Ad Hoc Networks, Vol 7, Issue 3, pp. 537-568, 2009.
[5] B. Sundararaman, U. Buy and A. Kshemkalyani, “Clock synchronization for wireless sensor networks: a survey,” Ad Hoc Networks, Vol 3, Issue 3, pp. 281-323, 2005.
[6] G. Simon, M. Maroti, A. Ledeczi, G. Balogh, B. Kusy, A. Nadas, G. Pap, J. Sa Sallai and K. Frampton, “Sensor network-based countersniper system,” In Proc. of the Second International Conference on Embedded Networked Sensor
Systems, pp. 1-12, Baltimore, MD, 2004.
[7] J. Campbell, P.B. Gibbons, S. Nath, P. Pillai, S. Seshan and R. Sukthankar,“IrisNet: an Internet-scale architecture for multimedia sensors,” In Proc. of the ACM Multimedia Conference, pp. 81-88, 2005.
[8] G. Wener-Allen, K. Lorincz, M. Ruiz, O. Marcillo, J. Johnson, J. Lees. and M. Walsh, “Deploying a wireless sensor network on an antive volcano,” IEEE Internet Computing , Vol. 10, Issue 2, pp. 18-25, March 2006.
[9] Md. A. Rahman, A. El Saddik and W. Gueaieb,“SenseFace: A Sensor Network Overlay for Social Networks,” In Proc. IEEE I2MTC, pp. 1031-1036, 2009.
[10] A. Mararculescu, S. Nikoletseas, O. Powell, J. Rolim, “Efficient tracking of moving targets by passively handling traces in sensor networks,” In Proc. of
the IEEE Global Telecommunications Conference, pp. 1-12, New Orleans, LA, U.S.A., 2008
[11] K. Akkaya and M. Younis, “A survey on routing protocols for wireless sensor networks,” Ad Hoc Networks, Vol. 3, Issue 3, pp. 325-349, 2005.
[12] Taewook Kang, Jangkyu Yun, Hoseung Lee, Icksoo Lee, Hyunsook Kim, Byunghwa Lee, Byeongjik Lww and Kijun Han, “A Clustering Method for Energy Efficient Routing in Wireless Sensor,” In Proc. of the 6th WSEAS Int.
Conf. on Electronics, Hardware, Wireless and Optical Communications, pp.133-138, Greece, 2007.
[13] S. Tilak, N. Abu-Ghazaleh and W. Heinzelman, “A taxonomy of wireless microsensor network models,” ACM SIGMOBILE Mobile Computing and Communications Review, Vol 6, Issue 2 , pp. 28-36, 2002.
[14] Charles E. Perkins and Elizabeth M. Royer, “Ad hoc On-Demand Distance Vector Routing,” In Proc. of the 2nd IEEE workshop on Mobile Computing Systems and Application, pp. 90-100, New Orleans, LA, 1999.
[15] W. Heinzelman, J. Kulik and H. Balakrishnan,“Adaptive protocols for information dissemination in wireless sensor networks,” In Proc. of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 174-185, Seattle, 1999.
[16] Y. Xu, J. Heidemann and D. Estrin, “Geography -informed energy conservation for ad hoc routing,” In Proc. of the 7th Annual ACM/IEEE International Conference, pp. 70-84, Rome, July 2001.
[17] W. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient communication protocol for wireless sensor networks,” In Proc. of the Hawaii International Conference System Sciences, pp. 3005-3014, Hawaii, 2000.
[18] L.d Costa, F.A. Rodrigues, G. Travieso and P.R.V. Boas, “Characterization of complex networks: A survey of measurements,” Adv. Phys., Vol 56, Issue 1, pp. 167-242, 2007.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2016-07-06公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-07-06起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信