跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/15 12:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張詠庭
研究生(外文):Yung-Ting Chang
論文名稱:無線感測器網路上以資料相關性為基礎之高效能資料聚集通訊協定之研究
論文名稱(外文):A Study on High-Performance Data Aggregation with Data Correlate-Based Routing Protocols in wireless Sensor Networks
指導教授:許丕榮許丕榮引用關係
指導教授(外文):Pi-rong Sheu
學位類別:碩士
校院名稱:國立雲林科技大學
系所名稱:電機工程系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:66
中文關鍵詞:群集式資料聚集資料相關性基因演算法啟發式演算法線性規劃感測器網路
外文關鍵詞:Cluster-BasedData AggregationData CorrelationGenetic AlgorithmHeuristic AlgorithmLinear ProgrammingSensor Network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:131
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,無線感測器網路是相當熱門的研究主題。由於感測器技術的快速進步,促進了無線感測器網路的蓬勃發展。無線感測器網路通常被應用在許多不同的領域上,像國防軍事、動植物棲息地的監控,以及民生應用。雖然,無線感測器網路可以提供很多有價值的應用,但也需要去克服許多延伸的問題。在無線感測器網路裡,最重要的問題之一,就是如何將偵測到的這些資料最有效地傳送至基地台。
在無線感測器網路的資料傳遞可區分為四種:(1) tree-based (2) chain-based (3) mobile agent-based 與 (4) cluster-based。在它們之中,除了mobile agent-based之外,都是將網路裡所有感測器的資料傳送至基地台。在密集度較高的網路裡,這些資料傳遞型態,可能會引起在相同區域的資料重複性,導致較多的電力消耗和間接減少網路生命週期。
在論文中,我們利用不同感測器所偵測到重複性的資料,發現資料中必定有某些相關性的特性來減少基地台接收到重複性的資料,並且使用此特性去改良一般cluster-based資料傳遞。我們知道,傳統的cluster-based形式利用clusterhead去收集cluster內所有感測器偵測的資料後傳送至基地台。然而,在我們提出的方法中,我們每次只使用一個clusterhead偵測cluster內的資料,而後再傳送至基地台。這個方法,在高密集度的網路中,可避免產生過多重複性資料,減少clusterhead的電力消耗與收集時間並且延長網路生命週期。
對於上述的議題,我們藉由啟發式演算法,基因演算法以及混合整數規劃去求解它並且嘗試去比較。比較結果顯示,雖然啟發式演算法沒有辦法像混合整數規劃獲得一個最佳解,它仍然可以找到一個可用的解。然而當我們啟發式演算法與 [WRBIVQC04] 所使用方法做比較,我們可以發現啟發式演算法裡感測器間的傳送距離在網路中的距離較長。由此可見,這些感測器從目標物偵測的資料比mobile agent-based形式到更加廣泛,並且也有助於基地台接收到較少的重複性資料。
The wireless sensor networks are quite popular in recent years. The rapid progress of the sensor technology promotes the vigorous development of the wireless sensor networks. The wireless sensor networks are generally used in lots of applications of different fields, like the military of the national defense, the habitat monitoring of animals and plants, and the consumer applications. Though the wireless sensor networks can offer many valuable applications, it still suffers many problems needed to be overcome. One of the most important problems is how to transmit those detected data to the base station more efficiently in the wireless sensor networks.
The data transmission mode in the wireless sensor networks can be divided into four types: (1) tree-based (2) chain-based (3) mobile agent-based and (4) cluster-based. Among them, besides the mobile agent-based, they all transmit data of sensors in the networks to the base station. This data transmission method may cause the reiterations of the same area in the higher density networks. That result in the power consuming and the network lifetime decreasing indirectly.
In this thesis, we utilize the characteristic that the reiteration data detected by different sensors must have certain correlation to decrease the data repetitions in the base station and use it to improve the ordinary cluster-based data transmission. As we know, the traditional cluster-based mode utilizes the clusterhead to collect all data detected from sensors then transmit to the base station. However, in our proposed method, we only use one cluseterhead which changes each time to detect the information in this cluster and transmit to the base station. In this way, we could avoid the data redundency in the high density networks, reduce the power consuming and collecting time of the clusterhead, and prolong the lifetime of networks.
For the above issue, we try to make a comparison by solving it with the heuristic algorithm, the genetic algorithm, and the mixed-integer programming. The comparison result shows that though the heuristic algorithm does not have a optimal solution like what is obtained by the mixed-integer programming, it still can find a feasible one. However when we compare the heuristic algorithm with the method proposed by [WRBIVQC04], we can find that the heuristic algorithm can have longer data transmission distance among sensors in the network. It indicates that these sensors can detect more extensive data from the target than the mobile agent-based method which help the base station to receive less reiterated data.
中文摘要………………………………………………………………………………i
英文摘要……………………………………………………………………………iii
目錄………………………………………………………………………………...….v
圖目錄……………………………………………………………………………...vii
表目錄…………………………………………………………………………...viii
一、 簡介…………………………………………………………....………1
二、 相關工作………………………………………………………..……..5
2.1 資料傳遞方式型態…………………………………………………....5
2.2 目前相關研究……………………………….………………………...5
2.2.1 Tree-based型態………………………………………….………….5
2.2.2 Chain-based型態……………………………………….…………..6
2.2.3 Mobile agent-based型態…………………………………….……...6
2.2.4 Cluster-based型態……………………………..……………………7
三、 問題描述…………………………………………………..…………..9
3.1 鏈結分群和圖形理論的關係………………………..………………..9
3.2 網路模型……………………………………………..………………10
3.3 電力模型………………………………………..……………………11
3.4 Sensor間的資料相關性……………………………..…………….12
3.5 MICDS問題……………………………………..………………...13
四、 求解MICDS問題…………………………...….…………………....17
4.1 啟發式演算法求解MICDS問題……………...………………….....17
4.1.1 MICDS啟發式演算法…………………..………………………...17
4.1.2 實例說明……………………………….……………….……………19
4.2 基因演算法求解MICDS問題………………………………………21
4.2.1 基因演算法簡介…………….........………………………………….21
4.2.2 無線感測器網路架構……….……..………………………………...22
4.2.3 基因演算法流程圖……………..……………………………………24
4.2.4 初始族群與族群大小………..…………..…………………………..25
4.2.5 染色體的表示……..……..…………………………………………..25
4.2.6 求值………..………………..………………………………………..26
4.2.7 選擇與複製…………………..……………………………………....27
4.2.8 交配……………………………..……………………………………29
4.2.9 突變………………………………..…………………………………30
4.2.10 終止條件……………………………...……………………...………30
4.3 混合整數規劃求解MICDS問題…………...……………….……....31
4.3.1 線性規劃簡介…………………………….………………...………..31
4.3.2 混合整數規劃求解MICDS問題…….……………………………..35
五、 模擬環境與結果…………………..………………………………....42
六、 結論………………………………..……………………..…………..48
參考文獻……………………………………………………………………………..49
參考文獻
[AlWF02] K. M. Alzoubi, P. J. Wan, and O. Frieder, “New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks,” Proceedings of 35th Hawaii International Conference System Sciences, pp. 1-7, Jan. 2002.
[ASSC02] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, vol. 40, pp. 102-114, Aug. 2002.
[AtTH03] A. L. Atov, H. T. Tran, and R. J. Harris, “Efficient QoS Partition and Routing in Multiservice IP Networks,” Performance, Computing and Communications Conference, 2003, pp. 435-441, Apr. 2003.
[BaDa01a] N. Banerjee and S. K. Das, “Fast Determination of QoS-Based Multicast Routes in Wireless Networks Using Genetic Algorithm,” Communications, vol. 8, pp. 2588-2592, 2001.
[BaDa01b] N. Banerjee and S. K. Das, “MODeRN: Multicast On-Demand QoS-Based Routing in Wireless Networks,” Vehicular Technology Conference, vol. 3, pp. 2167-2171, 2001.
[BaKT01] P. Basu, N. Khan, and Thomas D. C. Little, “A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks,” Proceedings of IEEE ICDCS ''01, pp. 413-418, Apr. 2001.
[BaMu00] D. Banerjee and B. Mukherjee, “Wavelength-Routed Optical Networks: Linear Formulation, Resource Budgeting Tradeoffs, and A Reconfiguration Study,” IEEE/ACM Transactions on Networking, pp. 598-607, Oct. 2000.
[Basa99] S. Basagni, “Distributed and Mobility-Adaptive Clustering for Multimedia Support in Multi-Hop Wireless Networks,” Proceedings of IEEE VTC, vol. 2, pp. 889-893, Sept. 1999.
[BeGT96] D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis, “Stability Conditions for Multiclass Fluid Queueing Networks,” IEEE Transactions on Automatic Control, pp. 1631-1681, Nov. 1996.
[ChDT00] M. Chatterjee, S. K. Das, and D. Turgut, “An On-demand Weighted Clustering Algorithm (WCA) for Ad Hoc Networks,” IEEE GLOBECOM’00, vol. 3, pp. 1697-1701, Dec. 2000.
[ChHs05] S. T. Cheng and C. L. Hsu, “Genetic Optimal Deployment in Wireless Sensor Networks,” Journal of Internet Technology, pp. 9-18, 2005.
[ChTa00] J. H. Chang and L. Tassiulas, “Energy Conserving Routing in Wireless Ad-Hoc Networks,” Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 22-31, 2000.
[CLHE02] C. Chakrabarty, K. Lyengar, S. S. Hairong Qi, and C. Eungchun, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transactions on Computers, pp. 1448-1453, Dec. 2002.
[CrBV04] R. Cristescu, B. Beferull-Lozano, and M. Vetterli, “On Network Correlated Data Gathering,” In INFOCOM’04, Hong Kong, 2004.
[CuTa05] H. Cunqing and Y. Tak-Shing Peter, “Optimal Routing for Maximizing Lifetime of Wireless Sensor Networks,” In INFOCOM’ 05, 2005.
[DiIs00] S. Ding and N. Ishii, “An Online Genetic Algorithm for Dynamic Steiner Tree Problem,” Industrial Electronics Society, 2000. 26th Annual Conference of the IEEE, vol. 2, pp. 812-817, 2000.
[DMEA03] A. K. Das, A. K. Marks, R. J. El-Sharkawi, M. Arabshahi, and A. Gray, “Minimum Power Broadcast Trees for Wireless Networks: Integer Programming Formulations,” Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1001-1010, Apr. 2003.
[DRWT97] R. Dube, C. D. Rais, K. Y. Wang, and S. K. Tripathi, “Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks,” IEEE Personal Communications Magazine, vol. 4, no. 1, pp. 36-45, Feb. 1997.
[FaPu01] S. Fang and S. Puthenepura, “Linear Optimization and Extensions: Theory and Algorithm,” Prentice-Hall International, Inc., 2001
[GeTs95] M. Gerla and J. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” ACM/Baltzer Journal of Wireless Networks, vol. 1, pp. 225-238, 1995.
[GiTB00] A. I. Giortzis, L. F. Turner, and J. A. Barria, “Decomposition Technique for Fixed Channel Assignment Problems in Mobile Radio Networks,” Proceedings of IEEE Communications, vol. 147, pp. 187-194, June 2000.
[GNDC05] H. Gupta, V. Navda, S. Das, and V. Chowdhary, “Efficient Gathering of Correlated Data in Sensor Networks,” MobiHoc, 2005.
[GPSV03] L. Gouveia, P. Patricio, A. F. De Sousa, and R. Valadas, “MPLS
Over WDM Network Design with Packet Level QoS Constraints
Based on ILP Models,” Conference of the IEEE Computer and Communications Societies, 2003.
[GuYo03] G. Gupea and M. Younis, “Load-Balanced Clustering of Wireless Sensor Networks,” IEEE International Conference on Communications, vol. 3, May 2003.
[HaPe01] Z. J. Hass and M. R. Pearlman, “The Performance of Query Control Schemes for The Zone Routing Protocol,” IEEE/ACM Transactions on Networking, vol. 9, issue 4, pp. 427-438, Aug. 2001.
[HeCB00] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Communication Protocols for Wireless Microsensor Networks,” In Proceedings of the IEEE Hawaii International Conference on System Sciences, Jan. 2000.
[HePi93] M. Herzberg and A. Pitsillides, “A Hierarchical Approach for the Bandwidth Allocation, Management and Control in B-ISDN,” IEEE International Conference on Communications, vol. 3, pp. 1230-1324, May 1993.
[Hu04] C. P. Hu, “An Efficient QoS Power-Aware Reverse Multicast Routing Protocol in Wireless Sensor Networks,” Department of Electrical Engineering, National Yunlin University of Science & Technology, Thesis for the degree of master of science, Taiwan, R.O.C., 2004.
[KeJD03] D. Kemei, W. Jie, and Z. Dan, “Chain-Based Protocol for Broadcasting and Gathering in the Sensor Networks,” Parallel and Distributed Processing Symposium, pp. 22-26, Apr. 2003.
[KiHa05] H. S. Kim and K. J. Han, “A Power Efficient Routing Protocol Based on Balanced Tree in Wireless Sensor Networks,” DFMA ''05. First International Conference on Distributed Frameworks for Multimedia Applications, pp. 138-143, 2005.
[KrEW02] B. Krishnamachari, D. Estrin, and S. Wicker, “Modelling Data-Centric Routing in Wireless Sensor Networks,” IEEE INFOCOM, 2002.
[KuVe02] V. Kumar and P. Venkataram, “An Efficient Resource Allocation Scheme for Mobile Multimedia Networks,” 4th International Workshop on Mobile and Wireless Communications Network, pp. 89-92, 2002.
[Lee03] Y. P. Lee, “Efficient Clustering Algorithms for Backbone Formation in Mobile Ad Hoc Networks,” Department of Electrical Engineering, National Yunlin University of Science & Technology, Thesis for the degree of master of science, Taiwan, R.O.C., 2003.
[LiHo04] N. Li and J. Hou, “BLMST: A Scalable, Power Efficient Broadcast Algorithm for Wireless Networks,” Quality of Service in Heterogeneous Wired/Wireless Networks, 2004, pp. 44-51, Oct. 2004.
[Liou03] L. C. Liou, “Setting-up Effective Balance Data Load’s Low Postpone Data Collected Tree in Wireless Sensor Networks,” Department of Computer Science and Information Engineering, Chung-Hua University. Thesis for the degree of master of science, Taiwan, R.O.C., 2003.
[LiRS02]S. Lindsey, C. Raghavendra, and K. M. Sivalingam, “Data Gathering Algorithms in Sensor Networks Using Energy Metrics,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, pp. 924-935, Sept. 2002.
[LoXu02] C. P. Low and S. Xueyan, “On Finding Feasible Solutions for The Delay Constrained Group Multicast Routing Problem,” IEEE Transactions on Computers, pp. 581-588, May 2002.
[PaRo04] R. Pascal and W. Roger, “Gathering Correlated Data in Sensor Networks,” Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing, Oct. 2004.
[PeBh94] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of ACM SIGCOMM’94, pp. 234-244, Sep. 1994.
[RaRa00] B. Ramamurthy and A. Ramakrishnan, “Virtual Topology Reconfiguration of Wavelength-Routed Optical WDM Networks,” Global Telecommunications Conference, 2000. GLOBECOM ''00. IEEE, vol. 2, pp. 1269-1275, 2000.
[RaSi95] R. Ramaswami and K. N. Sivarajan, “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Transactions on Networking, pp. 489-500, Oct. 1995.
[RoBD02] A. Roy, N. Banedee, and S. K. Das, “An Efficient Multi-Objective QoS-Routing Algorithm for Wireless Multicasting,” Vehicular Technology Conference, 2002. VTC IEEE 55th, vol. 3, pp. 1160-1164, May 2002.
[RySC01] J. H. Ryu, S. Song, and D. H. Cho, “Clustering Scheme for Energy Conservation in Two-Tiered Mobile Ad Hoc Networks,” Electronics Letters of IEEE, vol. 37, issue 11, pp. 710-711, May 2001.
[TWLS01] Y. C. Tseng, S. L. Wu, C. Y. Lin, and J. P. Sheu, “A Multi-Channel MAC Protocol with Power Control for Multi-Hop Mobile Ad Hoc Networks,” 2001 International Conference on Distributed Computing Systems Workshop, pp. 419-424, Apr. 2001.
[ViVe02] B. P. Vijay and P. Venkataram, “A LP-RR Principle-Based Admission Control for A Mobile Network,” IEEE Transactions on Systems, Man and Cybernetics, Part C, pp. 293-306, Nov. 2002.
[Wang02] C. W. Wang, “A Study on Stable Clustering for Mobile Ad Hoc Networks,” Department of Electrical Engineering, National Yunlin University of Science & Technology, Thesis for the degree of master of science, Taiwan, R.O.C., 2002.
[WRBIVQC04] Q. Wu, S. V. Rao, J. Barhen, S. S. Iyengar, V. K. Vaishnavi, H. Qi, and K. Chakrabarty, “On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 6, June 2004.
[YCCY05] L. H. Yen, M. Z. Cai, Y. M. Cheng, and P. Y. Yang, “Minimizing Energy Expense for Chain-Based Data Gathering in Wireless Sensor Networks,” The 2nd European Workshop on Wireless Sensor Networks, 2005.
[YeKa02] E. Yetginer and E. Karasan, “Robust Path Design Algorithms for Traffic Engineering with Restoration in MPLS Networks,” Computers and Communications, pp. 933-938, 2002.
[ZaJM00] H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks,” SPIE Optical Networks Magazine, vol. 1, no. 1, Jan. 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊