跳到主要內容

臺灣博碩士論文加值系統

(34.204.180.223) 您好!臺灣時間:2021/08/03 23:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:胡智彬
研究生(外文):Chin-Pin Hu
論文名稱:一個在無線感測器網路上以電力為考量之高效能QoS反向多播路徑繞送通訊協定
論文名稱(外文):An Efficient QoS Power-Aware Reverse Multicast Routing Protocol in Wireless Sensor Networks
指導教授:許丕榮許丕榮引用關係
指導教授(外文):Pi-Rong Sheu
學位類別:碩士
校院名稱:國立雲林科技大學
系所名稱:電機工程系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:79
中文關鍵詞:電力感測器網路
外文關鍵詞:power-awareQoS
相關次數:
  • 被引用被引用:0
  • 點閱點閱:120
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
雖然學術界在已過幾年已對MANET有了廣泛的研究並得到豐碩的研究成果,但由於無線感應器網路與隨意網路在本質上還是有所區別的,所以專為隨意網路所研發之相關技術和通訊協定並不一定能直接應用在WSNET上。
電力的管理在無線通訊網路上之所以被受重視,其主要的因素為大部分的可移動式主機,主要是依賴電池所提供的電力運作。由於無線感應器網路的電池電力相對於隨意網路來得較小並且感應器網路的環境比MANETs網路更不容易掌控,因此電池電力在WSNET上的重要性遠超過其它考量因素。
當設計路徑繞送通訊協定卻未將電力的消耗納入考慮時,整個無線通訊網路的運作將可能會出現二種不被期望的現象:一是網路上的每一個節點的電力都被大量的消耗,這將使得整個網路的生存週期大大地被縮短。二是網路上的每一個節點的電力消耗相當地不平均,也就是說,某些節點的電力會比其它節點的電力更快地被消耗完。很明顯地,這時通過這些無電力節點的路徑便會出現中斷的情況。當路徑中斷的情況增多時,整個網路便會出現不穩定的現象,結果網路的生存週期將大大地被縮短。因此如何有效地在路徑繞送通訊協定中納入節省電力之機制,在近年已成為一個重要的研究課題。
在無線感應器網路上之路徑繞送問題上,資料聚集(data aggregation)已被提出為一個特別有用的範例。由資料聚集所衍生出在無線感應器網路之通訊模式便可區分為四大類型:(1)一對全部(one-to-all)之通訊模式、(2)一對一(one-to-one)之通訊模式、(3)多對一(many-to-one)之通訊模式及(4)全部對一(all-to-one)之通訊模式。前兩種通訊模式與一般MANETs網路相同,唯有後兩種通訊模式與MANETs網路有著明顯的不同。
因此本篇論文對後兩種通訊模式提出以電力當作QoS參數之高效能路徑繞送通訊協定。當有k個來源節點欲傳送資料封包至sink節點時,必須保証其繞送路徑上每一節點在傳送封包的過程中都不會發生電力不足的情況;即多對一(many-to-one)通訊模式,我們將此通訊需求定義為以電力為考量之反向多播路徑繞送問題(The power-aware many-to-one routing problem, PAMOR問題)。當k=(n-1)時,PAMOR問題則變成全部對一(all-to-one)之通訊模式,我們將此通訊需求定義為以電力為考量之反向廣播路徑繞送問題(The power-aware all-to-one routing problem, PAAOR問題)。針對以上問題,我們對其設計啟發式演算法來尋求問題之合適解,並利用線性規劃及基因演算法來尋求問題之最佳解,最後以電腦模擬來對此三種方法作效能的比較。
Although many research efforts have bee proposde in MANET, since the differences between MANET and WSNET, so many protocols and algorithms have been proposed for MANET, they are not well suited to the features and application requirements of WSNET.
Most of the wireless communication networks operated on batteries, which contain limited power. Since the battery of WSNET comes to MANET relatively small, so the power efficiency is more important consideration in WSNET.
When a routing protocol is designed without taking into account power consumption, two undesirable phenomena will occur during the operation of the wireless communication networks. The first one is that every hosts on the wireless communication networks will consume power heavily and the lifetime is shortened seriously, the second is the uneven consumption. In other, certaion hosts will consume power faster than other host. It is obvious that the route that travel through there powerless hosts will be cut off. The whole wireless communications networks will become unstable and end up suffering shortened lifetime.
Data gathering is a useful paradigm in WSNET. Since the data gathering of WSNET, the commumication model can be divided into four classes: (1) one-to-all communication model (2) one-to-one communication model (3) many-to-one communication model (4) all-to-one communication model. First two kinds of communication model are the same as MANET. The last two communication model are different from MANET obviously.
Hence we propose an efficient QoS power-aware reverse multicast routing protocol. When k sources would like to deliver packets to sink, we must ensure the low power condition will not occur during every node deliver packets. We define the many-to-one communication model as the power-aware many-to-one routing problem (PAMOR probelm). When k=(n-1), we define the all-to-one communication model as the power-aware all-to-one problem (PAAOR problem). Above twe problem, we design the heuristic algorithm to find the feasible solution and use the linear programming and genetic algorithm to find the optimal solution. Finally, we use computer simulation to compare the performance above three kind methods.
中文摘要
英文摘要
目錄
圖目錄
表目錄

第一章 導論
第二章 問題描述
2.1 電力模型
2.1.1 節點之電力模型
2.1.2 鏈結之電力消秏量模式
2.2 PAMOR問題
2.3 PAAOR問題
第三章 求解PAMOR問題
3.1 啟發式演算法求解PAMOR問題
3.1.1 PAMOR_S啟發式演算法
3.1.2 PAMOR_C啟發式演算法
3.1.3 實例說明
3.2 線性規劃求解PAMOR問題
3.2.1 線性規劃簡介
3.2.2 線性規劃求解PAMOR問題
3.3 基因演算法求解PAMOR問題
3.3.1 基因演算法簡介
3.3.2 無線感測器網路架構
3.3.3 基因演算法流程圖
3.3.4 初始族群與族群大小
3.3.5 染色體的表示
3.3.6 求值
3.3.7 選擇與複製
3.3.8 交配
3.3.9 突變
3.3.10終止條件
第四章 求解PAAOR問題
4.1 啟發式演算法求解PAAOR問題
4.1.1 PAAOR_S啟發式演算法
4.1.2 PAAOR_C啟發式演算法
4.1.3 實例說明
4.2 線性規劃求解PAAOR問題
4.3 基因演算法求解PAAOR問題
4.3.1 無線感測器網路架構
4.3.2 初始族群與族群大小
4.3.3 染色體的表示
4.3.4 求值
4.3.5 選擇與複製
4.3.6 交配
4.3.7 突變
4.3.8 終止條件
第五章 模擬環境與結果
第六章 結論
參考文獻
[1] http://www.pitotech.com.tw
[2] http://www.qualnet.com
[3] http://www.scalable-network.com
[4] 黃能富,“區域網路與高速網路,”維科出版社,1998年6月。
[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, April 2003.
[BaDa01a] N. Banerjee and S. K. Das, “Fast Determination of QoS-Based Multicast Routes in Wireless Networks Using Genetic Algorithm,” Communications, 2001, vol. 8, pp. 2588-2592.
[BaDa01b] N. Banerjee and S. K. Das, “MODeRN: Multicast On-Demand QoS-Based Routing in Wireless Networks,” Vehicular Technology Conference, 2001, vol. 3, pp. 2167-2171.
[BeGT96] D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis, “Stability Conditions for Multiclass Fluid Queueing Networks,”Automatic Control,IEEE Transactions on., pp. 1681-1631, Nov. 1996.
[CaHE02] M. Cagalj, J. P. Hubaux, and C. Enz, “Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues,” In Proceedings of the ACM MOBICOM ’02., Sept. 2002.
[CaSS03] J. Cartigny, D. Simplot, and I. Stojmenovic, “Localized Minimum-Energy Broadcasting in Ad-Hoc Networks,” In Proceedings of IEEE INFOCOM 2003., April 2003.
[ChTa00] J. Chang and L. Tassiulas, “Energy Conserving Routing in Wireless Ad -Hoc Networks,” INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE., Vol. 1, pp. 22-31, Mar. 2000.
[ChTa99] J.H. Chang and L. Tassiulas, "Routing for Maximum System Lifetime in Wireless Ad-Hoc Networks," in Proceedings of 37-th Annual Allerton Conference on Communication, Control, and Computing, Monticello., Sept. 1999.
[CLHE02] C. Chakrabarty, K. Lyengar, S.S. Hairong Qi, and C. Eungchun, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” Computers, IEEE Transactions on., pp. 1448-1453, Dec. 2002.
[DiIs00] S. Ding and N. Ishii, “An Online Genetic Algorithm for Dynamic Steiner Tree Problem,” Industrial Electronics Society, 2000. IECON 2000. 26th Annual Confjerence 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. IEEE., pp.1001-1010, April 2003.
[DoYK97] M. Dong, K. Yung and W. Kaiser, “Low Power Signal Processing Architectures for Network Microsensors,” In Proc. Int. Symp. Low Power Electronics and Design., pp. 173-177, Aug. 1997.
[EgGo01] O. Egecioglu and T. Gonzalez, “Minimum-Energy Broadcast in Simple Graphs with Limited Node Power,” In Proc. IASTED Int. Conf. on Parallel and Distributed Computing and Systems., pp. 334–338, 2001.
[FaPu01] Shu-Cherng Fang and Sarat Puthenepura, “Linear Optimization and Extensions: Theory and Algorithm,” Prentice-Hall International, Inc., 2001
[GeCh96] M. Gen and R. Cheng “Genetic Algorithms and Engineering Design,” JOHN WILEY & SONS, ISBN:0-471-12741-8, 1996.
[HeCB00] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy Efficient Communication Protocol for Wireless Microsensor Networks,” IEEE Proc. Hawaii Int’l. Conf. Sys. Sci., pp. 1–10, Jan. 2000.
[HeKB99] W. R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor Networks,” In Proceedings of ACM/IEEE MOBICOM ’99., pp. 174-185, Aug. 1999.
[HeKB02] W. R. Heinzelman, J. Kulik, and H. Balakrishnan, “Negotiation Based Protocols for Disseminating Information in Wireless Sensor Network s ,”Wireless Networks., Vol.8, pp. 169-185, 2002.
[InGE00] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,” Proc. ACM MobiCom ’00., pp. 56–67, 2000.
[JSAC01] C. E. Jones, K. M. Sivalingam, P. Agrawal, and J. C. Chen, “A Survey of Energy Efficient Network Protocols for Wireless Networks,” Wireless Networks., Vol. 7, no. 4, pp. 343-358, Aug. 2001.
[KKWZ03] M. Kubisch, H. Karl, A. Wolisz, L. C. Zhong, and J. M. Rabaey, "Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks," IEEE WCNC 2003., pp. 16-20, Mar. 2003.
[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,” Mobile and Wireless Communications Network, 2002. 4th International Workshop on., pp.89-92, 2002.
[LBWW01] L. Li, V. Bahl, Y. Wang, and R. Wattenhofer, “Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks,” In Proceedings of IEEE INFOCOM 2001., April 2001.
[Lian02] W. Liang, “Constructing Minimum-Energy Broadcast Trees in Wireless Ad Hoc Networks,” In Proceedings of ACM MOBIHOC ’02., pp. 194-205, June 2002.
[LiGe97] C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE J. Select. Areas Commun., pp. 1265-1275, Sept. 1997.
[LiHa01] L. Li and J. Y. Halpern,“ Minimum-Energy Mobile Wireless Networks Revisited,” ICC’01., June 2001.
[LiHS02] N. Li, J. Hou and L. Sha, “BLMST: A Scalable, Power Efficient Broadcast Algorithm for Wireless Sensor Networks,” submitted to ACM MobiHoc., Dec. 2002.
[LiHS03] N. Li, J. C. Hou, and L. Sha, “Design and Analysis of an MST-Based Topology Control Algorithm,” In Proceedings of IEEE INFOCOM 2003., April 2003.
[LiNi01] F. Li, and I. Nikolaidis, “On Minimum-Energy Broadcasting in All Wireless Networks,” In Proc. 26th Annual IEEE Conf. on Local Computer Networks., 2001.
[LiRa01] S. Lindsey and C. S. Raghavendra, “PEGASIS: Power-Efficient Gathering in Sensor Information Systems,” IEEE Aerospace Conference., Mar. 2001.
[LiRa01a] S. Lindsey and C. Raghavendra, “Energy Efficient Broadcasting for Situation Awareness in Ad-Hoc Networks,” In Proc. Int. Conf. Parallel Processing (ICPP’01)., 2001.
[LiRS01b] S. Lindsey, C. Raghavendra, and K. Sivalingam, “Data Gathering in Sensor Networks using the Energy Delay Metric,” In Proceeding of Parallel and Distributed Processing Symposium., Apr. 2001.
[LiWa01] X. Y. Li and P.J. Wan, “Constructing Minimum Energy Mobile Wireless Networks,” ACM Mobile Computing and Communication Reviews., Vol. 5, pp. 55–67, 2001.
[Medo95] E.A. Medova, “Application of Linear Programming Software Tools to ATM /SDH Traffic Management,” Twelfth UK Teletraffic Symposium. Performance Engineering in Telecommunications Networks (Digest No. 1995/054), IEE., pp. 701-711, Mar. 1995.
[MiBa02] A. Misra and S. Banerjee, “MRPC: Maximizing Network Lifetime for Reli- able routing in Wireless Environments,” WCNC2002., pp. 800-806, Mar. 2002.
[PeBh94] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proc. 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.
[PeRo99] C.E. Perkins and E.M. Royer, “Ad-Hoc On-Demand Distance Vector Routing,” 2nd IEEE Workshop on Mobile Computing System and Applications (WMCSA’99)., 1999.
[RaSi95] R. Ramaswami and K.N. Sivarajan, “Routing and Wavelength Assignment in All-optical Networks,” Networking, IEEE/ACM Transactions on., 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.
[RoMe99] V. Rodoplu and T. H. Meng, “Minimum Energy Mobile Wireless Networks,” IEEE JSAC., Vol. 17, no. 8, pp. 1333–44, Aug. 1999.
[ShRa02] R. C. Shah and J. M. Rabaey, “Energy Aware Routing for Low Energy Ad Hoc Sensor Networks,” In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC) 2002., Vol. 1, pp. 350-355, Mar. 2002.
[SiRa98] S. Singh and C. S. Raghavendra, “PAMAS – Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks,” ACM Computer Communication Review., July 1998.
[SiRS99] S. Singh, C. S. Raghavendra, and J. Stepanek, “Power-Aware Broadcasting in Mobile Ad Hoc Networks,” In Proc. PIMRC’99., Sept. 1999.
[SiWR98] S. Singh, M. Woo, and C. S. Raghavendra, “Power-Aware Routing in Mobile Ad Hoc Networks,” Proc. MobiCom ’98., Oct. 1998.
[Sohr00] K. Sohrabi, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Pers. Commun., pp. 16–27, Oct. 2000.
[SrSS02] M. Sridharan, M.V. Salapaka, and A.K. Somani, “A Practical Approach to Operating Survivable WDM Networks,” Selected Areas in Communications, IEEE Journal on., pp. 34-46, Jan. 2002.
[STGS02] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. B. Srivastava, “Optimizing Sensor Networks in the Energy-Latency-Density Design Space,” IEEE Transactions on Mobile Computing., pp. 70–80, Mar. 2002.
[Toh01] C. K. Toh, “Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks,” IEEE Communications Magazine., pp. 138-147, June 2001.
[TrDi00] S. Tragoudas and S. Dimitrova, “Routing with Energy Considerations in Mobile Ad Hoc Networks,” Wireless Communications and Networking Conference, IEEE, Chicago, IL., Sept. 2000.
[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,” Int. Conf. on Distributed Computing Systems, pp. 419-424, 2001.
[ViVe02] B.P. Vijay and P. Venkataram, “A LP-RR Principle-based Admission Control for a Mobile Network,” Systems, Man and Cybernetics, Part C, IEEE Transactions on., pp.293-306, Nov. 2002.
[WCLF01] P. J. Wan, G. Calinescu, X. Y. Li, and O. Frieder, “Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks,” In IEEE INFOCOM 2001., Vol. 2, pp. 1162-1171, Apr. 2001.
[WiNE00] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” In IEEE INFOCOM 2000., Vol. 2, pp. 585-594, Mar. 2000.
[WiNE02] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “The Energy Efficiency of Distributed Algorithms for Broadcasting in Ad Hoc Networks,” In Proceedings of IEEE 5th International Symposium on Wireless Personal Multimedia Communications (WPMC)., pp. 499-503, Oct. 2002.
[WoCu01] A. Woo and D. Culler, “A Transmission Control Scheme for Media Access in Sensor Networks,” Proc. ACM MobiCom ’01, pp.221–35, July 2001.
[YeKa02] E. Yetginer and E. Karasan, “Robust Path Design Algorithms for Traffic Engineering with Restoration in MPLS Networks,” Computers and Communications, 2002., pp. 933-938, 2002.
[YLCLZ02] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, “A Two-Tier Data Dissemination Model for Large-Scale Wireless Sensor Networks,” Proceedings of the Eighth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCOM 2002)., Sept. 2002.
[ZaJM00] H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks,” Opt. Netw. Mag. 1.,pp. 47-60, 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top