博碩士論文 955202014 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:11 、訪客IP:18.207.238.169
姓名 強芝瑋(Chih-Wei Charng)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱 在無線感測網路下處理不同重要性區域的覆蓋問題
(Coverage of the Weighted Field in Wireless Sensor Networks)
相關論文
★ 無線行動隨建即連網路上之廣播與繞徑問題★ 熱門電影的高效能廣播演算法
★ 無線行動隨建即連網路上之媒體存取問題★ 使用功率調整來增加多節點封包無線網路
★ 在無線行動隨建即用網路下Geocast 之設計與實做經驗★ 一個適用於熱門隨選視訊服務之快速排程廣播策略
★ 應用數位浮水印技術於影像之智慧財產權保護與認證★ 在寬頻分碼多重擷取技術上分配及再分配多重正交可變展頻係數碼
★ 無線行動隨建即連網路上之廣播排程協定★ 在無線行動隨建即連網路下支援即時多媒體傳送的媒介存取協定
★ 以樹狀結構為基礎的Scatternet建構協定★ 在無線感應器網路中具有省電機制並且採用對角線路徑的方向性擴散
★ 隨意型無線網路上一個具有能量保存的GRID繞徑協定★ 在無線感應器網路中具有省電機制的傳輸協定
★ 隨意型無線網路上一個具有能量保存以及平衡的繞徑協定★ 環形藍芽網路:一個藍芽通訊網路的新拓樸及其繞徑協定
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 無線感測網路(wireless sensor networks, WSNs)的應用很廣,常用在監測/偵測環境。這些應用大部分都有覆蓋(coverage) 的問題。此問題主要就是找尋較少的感測器來偵測事件(event)的發生,且讓感測器覆蓋住所有事件可能發生的地方。通常被監測區域會隨著區域的重要程度,而有不同程度的感測需求。較重要的區域會有較高的感測需求。但大部份的論文,常假設偵測範圍內,每個區域都有相同的重要性。
另外,感測器的感測範圍(sensing range)也常會受到距離的影響,造成感測機率隨著距離增大而降低。在此篇論文中我們採取機率式感測模型(probabilistic detection model)。我們希望使用最少的感測器個數,覆蓋具有不同重要性需求的區域。首先,我們證明用最少感測器來達成完全覆蓋是一個NP-完成性的問題。接著我們提出一個近似(approximation)的演算法來尋找較佳的感測器擺放位置。此外,我們也提出了此一問題理論上需佈置感測器的漸近下限(lower bound)值。從實驗的結果,可以得知我們的方法,找出的感測器個數最差是漸近下限的3倍。
摘要(英) The wireless sensor networks (WSNs) are widely used in many applications to monitor/sense environmental conditions. Most of these applications have the coverage problem. The coverage problem is to place minimal number of sensors which can detect the events in a sensing field. If every point in a sensing field is covered by at least one sensor, the sensing field is full coverage. In the real applications, the sensing requirement of a region depends on the importance of the region. A more important region requires a higher coverage rate or detection probability. However, most of researchers pay less attention to the issue that different regions in a sensing field have different important degrees.
Due to the signal attenuation and noise under realistic environment, the detection probability of a sensor will decrease with increasing its sensing distance. Therefore, we use the probabilistic detection model instead of the binary detection model to solve the coverage problem in which different regions of a sensing field have different important degrees. The region with higher important degree is, the higher event detection probability is required. First, we prove that finding the minimum number of sensors to cover a sensing field with different important regions is NP-complete. Then we propose an approximation algorithm to solve this problem in polynomial time and find the lower bound of this problem. Simulation results show that the solution of our approximation algorithm in the number of sensors is less than three times than the lower bound.
關鍵字(中) ★ 覆蓋問題
★ 機率式感測模型
★ 無線感測網路
★ NP-完成性
關鍵字(英) ★ Coverage problem
★ probabilistic detection model
★ wireless sensor networks
★ NP-complete
論文目次 Chapter 1 Introduction...1
Chapter 2 Preliminary... 4
2.1 Related works... 4
2.2 Detection model... 5
2.3 Our Detection Model and Our Sensing Field Setting.. 7
Chapter 3 Sensor Placement for Gradually Weighted Field.. 11
3.1 Proof SCGWF is NP-complete... 11
3.2 Our Approximation Algorithm.. 21
3.3 Lower Bound Setting.. 30
Chapter 4 Simulation Results.. 34
Chapter 5 Conclusions.. 44
References... 45
參考文獻 [1] Troops start Mexico border duty B.B.C. News, June 2006.
http://news.bbc.co.uk/2/hi/americas/5051720.stm
[2] http://en.wikipedia.org/wiki/United_States%E2%80%93Mexico_barrier
[3] N. Ahmed, S. Kanhere, and S. Jha, “Probabilistic Coverage in Wireless Sensor Networks,” in Proceedings of IEEE on Local Computer Networks (LCN), pp. 672–681, Nov. 2005.
[4] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai, “Deploying Wireless Sensors to Achieve Both Coverage and Connectivity,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 131-142, May 2006.
[5] Y. L. Cai, W. Lou, M. L. Li, and X. Y. Li, “Target-Oriented Scheduling in Directional Sensor Networks,” in Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1550-1558, May 2007.
[6] M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz, “Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges,” in Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), vol. 3, pp. 438- 445, Aug. 2005.
[7] R. S. Chang, and S. H. Wang, “Self-Deployment by Density Control in Sensor Networks,” Journal of Vehicular Technology, vol. 57, no. 3, pp. 1745-1755, May 2008.
[8] S. Chellappan, X. Bai, and B. Ma, “Mobility Limited Flip-Based Sensor Networks Deployment,” Journal of Parallel and Distributed Systems, vol. 18, no. 2, pp. 199-211, Feb. 2007.
[9] S. Cook, “The Complexity of Theorem Proving Procedures,” in proceedings of ACM Symposium on Theory of Computing, pp. 151-158, May 1971.
[10] A. Elfes, “Occupancy Grids: a Stochastic Spatial Representation for Active Robot Perception”, in Proceedings of Conference on Uncertainty in AI, pp. 60-70, July 1990.
[11] C. Fang and C. P. Low, “Redundant Coverage in Wireless Sensor Networks,” in Proceedings of IEEE International Conference on Communications (ICC), pp. 3535-3540, June 2007.
[12] M. Hefeeda and M. Bagheri, “Randomized K-Coverage Algorithms for Dense Sensor Networks,” in Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ), pp. 2376-2380, May 2007.
[13] M. Hefeeda and H. Ahmadi, “A Probabilistic Coverage Protocol for Wireless Sensor Networks,” in Proceedings of IEEE International Conference on Network Protocols (ICNP), pp. 41-50, Oct. 2007.
[14] J. Jeong, S. Sharafkandi, and D. Du, “Energy-Aware Scheduling with Quality of Surveillance Guarantee in Wireless Sensor Networks,” in Proceedings of the Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS), pp. 55–64, Sep. 2006.
[15] W. C. Ke, B. H. Liu, and M. J. Tsai, “Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete,” Journal of Computers, vol. 56, no. 5, pp. 710-715, May 2007.
[16] S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage With Wireless Sensors,” in International Conference on Mobile Computing and Networking (MobiCom), pp. 284-298, Aug. 2005.
[17] D. Lichtenstein, “Planar Formulae and Their Uses,” SIAM Journal on Computing, vol. 11, no. 2, pp. 329-343, May 1982.
[18] B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 411-419, May 2008.
[19] S. S. Ram, D. Manjunath, S. K. Iyer, and D. Yogeshwaran, “On the Path Coverage Properties of Random Sensor Networks,' Journal of Mobile Computing, vol. 6, no. 5, pp. 446-458, May 2007.
[20] J. P. Sheu and H. F. Lin, “Probabilistic Coverage Preserving Protocol with Energy Efficiency in Wireless Sensor Networks,” in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp. 2631-2636, March 2007.
[21] N. Shrivastava, R. Mudumbai, U. Madhow, and S. Suri, “Target Tracking with Binary Proximity Sensors: Fundamental Limits, Minimal Descriptions, and Algorithms,” in Proceedings of ACM International Conference on Embedded Networked Sensor Systems (SenSys), pp. 251-264, Oct. 2006.
[22] V. Sler, S. Kannan, and K. Daniilidis, “Sampling Based Sensor-Network Deployment,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1780-1785, Oct. 2004.
[23] S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” in Proceedings of IEEE International Conference on Communications (ICC), vol. 2, pp. 472-476, June 2001.
[24] G. Takahara, K. Xu, and H. Hassanein, “Efficient Coverage Planning for Grid-Based Wireless Sensor Networks,” in Proceedings of IEEE International Conference on Communications (ICC), pp. 3522-3526, June 2007.
[25] G. Wang, G. Cao, P. Berman, and T. La Porta, "Bidding Protocols for Deploying Mobile Sensors," Journal of Mobile Computing, vol. 6, no. 5, pp. 515-528, May 2007.
[26] T. Yan, T. He and J. Stankovic, “Differentiated Surveillance for Sensor Networks,” in Proceedings of ACM Embedded Networked Sensor Systems (SenSys), pp. 51-62, Nov. 2003.
[27] S. Yang, F. Dai, M. Cardei, and J. Wu, "On Connected Multiple Point Coverage in Wireless Sensor Networks," Journal of Wireless Information Networks, vol. 13, no. 4, pp. 289-301, Oct. 2006.
[28] Y. Zhu and L. M. Ni, “Probabilistic Wakeup: Adaptive Duty Cycling for Energy-Efficient Event Detection,” in Proceedings of the ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM), pp. 360 - 367, Oct. 2007.
[29] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” Journal of Embedded Computing Systems, vol. 3, no. 1, pp. 61-91, Feb. 2004.
[30] Y. Zou and K. Chakrabarty, “Uncertainty-Aware and Coverage-Oriented Deployment for Sensor Networks,” Journal of Parallel and Distributed Computing, vol. 64, pp. 788-798, July 2004.
指導教授 許健平、張貴雲
(Jang-Ping Sheu、Guey-Yun Chang)
審核日期 2008-7-21
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明