在無線感測網路中連續型物體的偵測與追蹤協定之設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：21

、訪客IP：3.141.31.240

姓名

杜信志(Shin-Chih Tu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在無線感測網路中連續型物體的偵測與追蹤協定之設計
(The Protocols for Continuous Objects Detection and Tracking in Sensor Networks)

相關論文

★ 基於OP-TEE的可信應用程式軟體生態系統	★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略	★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案	★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 衛星地面整合網路之隨機接入前導訊號設計與偵測	★ SatPolicy: 基於Trustzone的衛星政策執行系統
★ TruzMalloc: 基於TrustZone 的隱私資料保護系統	★ 衛星地面網路中基於物理層安全的CSI保護方法
★ 低軌道衛星地面整合網路之安全非正交多重存取傳輸	★ 低軌道衛星地面網路中的DRX機制設計
★ 衛星地面整合網路之基於集合系統的前導訊號設計	★ 基於省電的低軌衛星網路路由演算法
★ 衛星上可重組化計算之安全FPGA動態部分可重組架構	★ 衛星網路之基於空間多樣性的前導訊號設計

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來，由於科技及硬體技術的進步，使得體積小、記憶容量大、低成本、多功能、省電、且具無線與感測能力的感測器得以實現。這亦使無線感測網路的應用日趨成熟，並被廣泛應用在許多的領域，例如：災害回報、軍事偵測與監控、位置追蹤、環境監控等多種領域。基於上述的應用領域都有使用感測器來幫助偵測、追蹤某些特定事件，所以我們的研究議題是在無線感測網路中設計連續型物體的偵測與追蹤協定。
目前大部分物體的偵測與追蹤協定其設計重點是針對個體型物體的偵測與追蹤，例如：入侵者、坦克、交通工具等個體型物體。這些個體型物體同通常只會被其所在周圍數個感應器所感測。因此，個體型物體偵測與追蹤協定的設計重點在於，感測到物體的事件節點之間要如何協同計算出物體位置或如何有效率的將感測到物體的位置送到後端使用者。而連續型物體不同於個體型物體的地方在於：連續型物體通常會使得大量的感測器同時偵測的物體的出現，且物體的形狀、體積、位置會隨著時間改變，例如：森林大火、有毒氣體擴散，群居動物遷移、軍隊的行進等等。因此，連續型物體偵測與追蹤協定的設計所要考慮的重點在於如何利用最少的資訊來評估物體的位置以減少物體資訊的回報量，進而減少通訊所造成的電量耗損。
在連續型物體偵測協定設計上，我們提出了兩個協定：第一個協定為，以網路拓墣控制為基礎的分散式連續型物體偵測協定；第二個協定為，以涵蓋方式為基礎的分散式連續型物體偵測協連續型物體偵測協定。在第一個所提出的協定中，我們首先利用三角劃分來減少每一個感測器鄰近節點的數目，進而將事件節點中最靠近物體邊界的節點挑選成邊界節點。被挑選出的邊界節點將會回報它們自己的位置資訊給使用者。而使用者藉由所接收的資訊，可以評估出所有事件節點的位置。在這個協定中，我們同時提出兩個規則來進一步的減少邊界節點的數量，且所提出的規則將不會花費額外的通訊成本。
由於，邊界節點的數量主要是受到連續型物體的邊長所影響。也就是說，無論連續型物體的形狀或體積如何，邊長較長的連續型物體將會有較多的邊界節點。因此，我們提出第二個以涵蓋方式為基礎的分散式連續型物體偵測協連續型物體偵測協定，來改善這個問題。在這個協定中，我們找出所有事件節點中的核心節點。核心節點的位置與跳數(hop-count)半徑資訊可以表達一個涵蓋區域。而所有核心節點的涵蓋區域可以涵蓋出所有事件節點的位置。因此，當使用者收到所有核心節點的回報資訊，將可以評估出連續型物體的位置。由於，核心節點的數量少於邊界節點，所以藉由核心節點來回報資訊給使用者將可以有效率的減少回報物體資訊的通訊量。
在無線感測網路中，感測節點之間需要利用節點編號(node ID)來進行通訊。且在我們設計的連續型物體的偵測與追蹤協定中，需要每個感測節點都要有一個獨一無二的節點編號。因此，在本論文中我們同時設計了一個節點編號分配協定。藉由我們所設計的協定，在無線感測網路佈置後每一個感測節點將可以快速的取得一個獨一無二的節點編號。透過實驗的測試分析我們所設計協定的優越性都得到驗證。

摘要(英)

Recently, scientific progress and hardware technology have made possible the development of wireless sensor nodes in small sizes with large memory capacity, low cost, and the multi-function, which allow a wide range of applications for wireless sensor network, such as in battlefield surveillance, calamity reporting, biomedicine, hazardous environment exploration, environmental monitoring, and position tracking. Since these applications must use sensor nodes to detect and track some specific events, the object detection and tracking protocol is a basic function for these applications. In this dissertation, our research focuses on detection and tracking of continuous objects in wireless sensor networks.
Most of the previous researches on object detection and tracking focus on individual objects, such as intruder, tank, vehicle, etc. The individual object can usually be detected by several neighboring sensor nodes, called event nodes. Therefore, the collaboration of event nodes and efficient transmission of object information to sink nodes are considered in designing individual object detection and tracking protocols. Compared with the individual object, the continuous object is usually larger in size and can diffuse, increase in size, or split into multiple continuous objects, such as forest fire, noxious gas, the social animal moving and the army advancing, which imply that there should be a lot more event nodes. Hence, the main challenge and goal for designing the continuous object detection and tracking protocol is to reduce the number of reporting information to the sink node for energy conservation in communication. Therefore, individual object detection and tracking protocols are unsuitable for continuous object detection and tracking.
In this dissertation, we propose two continuous object detection and tracking protocols: a scalable topology-control-based continuous object detection and tracking (STCB) protocol and a coverage-based continuous object detection and tracking (CBDT) protocol. In the STCB protocol, the event nodes close to the boundary of object will be selected as boundary nodes in a quick distribution manner. Moreover, the location of these selected boundary nodes can represent the location of all event nodes. Therefore, only boundary nodes report their location information to sink nodes; the sink nodes can estimate the location information of continuous objects. Two rules for reducing the boundary node, without spending extra communication cost, are also discussed in the STCB protocol.
The number of selected reporters in a continuous object is proportional to the length of object boundary no matter what size or how sharp the object is. In CBDT protocol, one or several core nodes will be determined from the boundary nodes for reporting continuous object information. The location of the core nodes and their determined hop count can represent all the locations of the event nodes. Therefore, only the core nodes report their information to the sink node; the communication cost in continuous object detection and tracking can be further reduced.
In wireless sensor network, each sensor node needs a unique node ID for communication. A sensor node with a unique node ID would be assumed in our object detection and tracking protocol. Therefore, we also proposed a new node ID assignment protocol for each sensor node that obtains a unique node ID quickly in the network initialization. Through the simulations, the proposed protocols are verified to be both efficient and cost-effective.

關鍵字(中)

★ 連續型物體
★ 無線感測網路
★ 追蹤與偵測

關鍵字(英)

★ continuous objects
★ detection and tracking
★ sensor networks

論文目次

CHAPTER 1 INTRODUCTION 1
CHAPTER 2 PRELIMINARIES 5
2.1 Related works 5
2.2 Environment Assumption 10
CHAPTER 3 LOCATION-BASED ID ASSIGNMENT PROTOCOL 15
3.1 Location-based node ID Assignment Protocol 16
3.1.1 Dynamic node ID Redistribution mechanism 18
3.2 Node ID Maintenance protocol 23
3.3 Summary 25
CHAPTER 4 A SCALABLE PROTOCOL FOR OBJECTS DETECTION AND TRACKING 27
4.1 The proposed protocol 29
4.1.1 Collaborative data processing phase 29
4.1.1.1 Coarse reduction 30
4.1.1.2 Fine reduction 33
4.1.2 Object location reporting phase 39
4.1.2.1 Nearest neighboring reporter identification 40
4.2 The non-ring-type object 44
4.3 Performance evaluations 46
4.3.1 Effects of node degree on the number of reporters 47
4.3.2 Effects of node degree on control message overhead 47
4.3.3 Effects of node degree on data packets overhead 49
4.4 Summary 51
CHAPTER 5 A COVERAGE-BASED DETECTION AND TRACKING PROTOCOL FOR CONTINUOUS OBJECT 53
5.1 The CBDT Protocol 56
5.1.1 Reporter determination phase 56
5.1.1.1 A heuristic for minimum core set 57
5.1.2 The data aggregation phase 64
5.2 k-CBDT protocol 66
5.3 Performance evaluations 67
5.3.1 Effects of node degree on the number of reporters 68
5.3.2 Effects of node degree on communication cost of reporter selection 69
5.3.3 Effects of node degree on communication cost of data reporting 71
5.4 Summary 72
CHAPTER 6 CONCLUSIONS AND FUTURE WORKS 75
BIBLIOGRAPHY 77
PUBLICATIONS 82

參考文獻

[1] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology,” in Workshop on Data Communication, pp. 20-41, 2001.
[2] C. Y. Chang and C. T. Chang, “Hierarchical Cellular-Based Management for Mobile Hosts in Wireless Ad Hoc Networks,” Computer Communications, vol. 24, pp. 1554-1567, 2001.
[3] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” Wireless Networks, vol. 7, no. 6, pp. 609-616, 2001.
[4] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, “Computational geometry: algorithms and applications,” Springer, Second Edition, 2000.
[5] R. Brooks, C. Griffin, and D. S. Friedlander, "Self-Organized distributed sensor network entity tracking," International Journal of High Performance Computing Applications, vol. 16, no. 3, pp. 207-219, 2002.
[6] K. K. Chintalapudi and R. Govindan, “Localized Edge Detection in Sensor Fields,” IEEE Ad Hoc Networks, vol. 1, no. 3, pp. 273-291, 2003.
[7] M. Chu, H. Haussecker, and F. Zhao, “Scalable information-driven sensor querying and routing for ad hoc heterogenous sensor networks,” International Journal of High Performance Computing Applications, vol. 16, no. 3, pp. 293-313, 2002.
[8] M. Ding, D. Chen, K. Xing, and X. Cheng, “Localized fault-tolerant event boundary detection in sensor networks,” in Proceedings of IEEE Conference on Computer Communications, pp. 902 - 913, 2005.
[9] R. Droms, “Dynamic Sensor node Configuration Protocol,” Network Working Group – RFC 2131, 1997.
[10] D. Estrin, R. Govindan, and J. Heidemann, “Embedding the Internet: Introduction,” Communications of the ACM, pp. 38-41, 2000.
[11] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challenges: Scalable Coordination in Sensor Networks,” in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 263-270, 1999.
[12] J. Eriksson, M. Faloutsos, and S. Krishnamurthy, “Scalable Ad Hoc Routing: The Case for Dynamic Addressing,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1108-1119, 2004.
[13] Q. Fang, J. Gao, and L. Guibas, “Locating and bypassing routing holes in sensor networks,” in Proceedings of IEEE Conference on Computer Communications, pp. 2458-2468, 2004.
[14] S. Funke, “Topological hole detection in wireless sensor networks and its applications,” in Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, pp. 44-53, 2005.
[15] C. Gui and P. Mohapatra “Power conservation and quality of surveillance in target tracking sensor networks,” in Proceedings of International Conference on Mobile Computing and Networking, pp. 129-143, 2004.
[16] T. He, S. Krishnamurthy, L. Luo, T. Yan, L. Gu, R. Stoleru, G. Zhou, Q. Cao, P. Vicaire, J. A. Stankovic, T. F. Abdelzaher, J. Hui, and B. Krogh, “VigilNet: An integrated sensor network system for energy-efficient surveillance,” ACM Transactions on Sensor Networks, vol. 2, no. 1, pp. 1-38, 2006.
[17] X. Ji, H. Zha, J. J. Metzner, and G. Kesidis, “Dynamic cluster structure for object detection and tracking in wireless ad-hoc sensor networks,” in Proceedings of the IEEE International Conference on Communications, pp. 3807-3811, 2004.
[18] M. Joa-Ng and I. T. Lu, “A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile Ad Hoc Networks,” Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1415-1425, 1999.
[19] J. M. Kahn, R. H. Katz, and K. S. J. Pister, “Next Century Challenges: Mobile Networking for Smart Dust,” in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 271-278, 1999.
[20] B.-H. Liu, W.-C. Ke, C.-H. Tsai, and M.-J. Tsai, “Constructing a message-pruning tree with minimum cost for tracking moving objects in wireless sensor networks is NP-complete and an enhanced data aggregation structure,” to appear in IEEE Transactions on Computers.
[21] J.-P. Sheu, S.-C. Tu, and L.-H. Chan, “A Distributed IP Address Assignment Scheme for Ad Hoc Networks,” in International Journal of Ad Hoc and Ubiquitous Computing, vol. 3, no.1 pp. 10 - 20, 2008.
[22] J. Liu, P. Cheung, L. Guonidas, and F. Zho, “A dual-space approach to tracking and sensor management in wireless sensor networks”, in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, pp. 131-139, 2002.
[23] J. Liebeherr, M. Nahas, and W. Si, “Application-layer multicasting with delaunay triangulation overlays,” Journal on Selected Areas in Communications, vol. 20, no. 8, pp. 1472-1488, 2002.
[24] L. Lazos, R. Poovendran, and J. A. Ritcey, “Detection and tracking: Probabilistic detection of mobile targets in heterogeneous sensor networks,” in Proceedings of the International Conference on Information processing in sensor networks, pp. 519-528, 2007.
[25] W. H. Liao, Y. C. Tseng, and J. P. Sheu, “GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks,” Telecommunication Systems, vol. 18, pp. 37-60, 2001.
[26] X. Lin and I. Stojmenovic, “GEDIR: Loop-Free Location-based Routing in Wireless Networks,” in Proceedings of the International Conference on Parallel and Distributed Computing and Systems, pp. 1025-1028, 1999.
[27] Y. B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” in Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Networking, pp. 66-75, 1998.
[28] Y. B. Ko and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms,” in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 101-110, 1999.
[29] A. Misra, S. Das, A. McAuley, and S. K. Das, “Autoconfiguration, Registration, and Mobility Management for Pervasive Computing,” IEEE Personal Communications Systems Magazine, vol. 8, pp. 24-31, 2001.
[30] M. Mohsin and R. Prakash, “node ID Assignment in a Mobile Ad Hoc Network,” in Proceedings of Military Communications Conference, vol. 2, pp. 856-861, 2002.
[31] D. Nicules and B. Nath, “Ad-hoc positioning system (APS) using AOA,” in Proceedings of IEEE Conference on Computer Communications, pp. 1734-1743, 2003.
[32] S. Nesargi and R. Prakash, “MANETconf: Configuration of Sensor nodes in a Mobile Ad Hoc Network,” in Proceedings of 21st Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 23-27, 2002.
[33] A. Puliafito, M. Fazio, and M. Villari, “AIPAC: Automatic IP Address Configuration in Mobile Ad Hoc Networks,” Computer Communications, vol.29, no. 8, pp.1189-1200, 2006.
[34] C. E. Perkins, E. M. Belding-Royer, and S. R. Das, “node ID Autoconfiguration for Ad Hoc Networks,” Mobile Ad Hoc Networking Working Group - Internet Draft, 2001.
[35] J. S. Park, Y. J. Kim, and S. Woo, “Stateless Address Auto-configuration in Mobile Ad Hoc Networks Using Site-Local Address,” Mobile Ad Hoc Networking Working Group - Internet Draft, 2002.
[36] A. Savvides, C. C. Han, and M. B. Strivastava, “Dynamic fine-grained localization in ad-hoc networks of sensors,” in Proceedings of International Conference on Mobile Computing and Networking, pp. 166-179, 2001.
[37] J. P. Sheu, S. C. Tu, and L. H. Chan, “A distributed IP address assignment scheme for ad hoc networks,” in Proceedings of the 11th international Conference on Parallel and Distributed Systems, vol. 1, pp. 439-445, 2005.
[38] L. Song, and D. Hatzinakos, “A cross-layer architecture of wireless sensor networks for target tracking,” IEEE/ACM Transactions on Networking, vol. 15, no. 1, pp. 145-158, 2007.
[39] N. Shrivastava, R. Mudumbai U. Madhow, and S. Suri “Target tracking with binary proximity sensors: fundamental limits, minimal descriptions, and algorithms,” in Proceedings of International Conference on Embedded networked sensor systems, pp. 251-264, 2006.
[40] H. Takagi and L. Kleinrock, “Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals,” IEEE Transactions, Communications, Vol. 32, No. 3, pp. 246-257, 1984.
[41] Y.-C. Tseng, S.-P. Kuo, H.-W. Lee, and C.-F. Huang, “Location tracking in a Wireless Sensor Network by Mobile Agents and its Data Fusion Strategies,” The Computer Journal, vol. 47, no. 4, pp. 448-460, 2004.
[42] N. H. Vaidya, “Weak Duplicate Address Detection in Mobile Ad Hoc Networks,” in Proceedings of ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 206 - 216, 2002.
[43] Y. Wang, J. Gao and J. S. B. Mitchell, “Boundary recognition in sensor networks by topological methods,” in Proceedings of International Conference on Mobile Computing and Networking, pp. 122-133, 2006.
[44] K. Weniger and M. Zitterbart, “IPv6 Autoconfiguration in Large Scale Mobile Ad-Hoc Networks”, in Proceedings of European Wireless 2002, Vol. 1, pp. 142 - 148, 2002.
[45] F. Zhao, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration for target tracking,” IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 61-72, 2002.
[46] H. Zhou, L. M. Ni, and M. W. Mutka, “Prophet Address Allocation for Large Scale MANETs,” in Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1304-1311, 2003.
[47] X. Zeng, R. Bagrodia, and M. Gerla, “GloMoSim: A Library for the Parallel Simulation of Large-Scale Wireless Networks,” in Proceedings of 12th Workshop on Parallel and Distributed Simulation, pp. 154-161, 1998.
[48] The Network Simulator (NS), URL .
[49] R. M. Karp, "Reducibility Among Combinatorial Problems", in R. E. Miller and J. W. Thatcher (editors): Complexity of Computer Computations, pp. 85–103, 1972.

指導教授

張貴雲、許健平
(Guey-Yun Chang、Jang-Ping Sheu)

審核日期

2008-7-7

推文