فهرست:
1 فصل اول مقدمه. 1
1.1 مکانیزمهای ذخیرهسازی انرژی در شبکههای حسگر بیسیم. 2
1.1.1 بهینهسازی رادیو. 3
1.1.2 کاهش حجم اطلاعات... 6
1.1.3 طرح خواب و بیدار. 7
1.1.4 مسیریابی با کارایی انرژی.. 8
1.1.5 راهحل شارژ. 10
1.2 ویژگیهای شبکههای حسگر بیسیم از منظر مسیریابی.. 11
1.3 الزامات طراحی الگوریتمهای مسیریابی در شبکههای حسگر. 13
1.4 بررسی کاستیهای الگوریتمهای مسیریابی موجود. 17
1.5 دستاوردها و نوآوریهای این پایان نامه. 21
2 فصل دوم مروری بر کارهای پیشین.. 23
2.1 الگوریتمهای مسیریابی نامبتنی بر ساختار. 24
2.1.1 الگوریتمهای جغرافیایی.. 24
2.1.2 الگوریتمهای مبتنی بر هوش مصنوعی و تئوری مورچگان. 27
2.1.3 الگوریتمهای خوشهبندی.. 30
2.2 الگوریتمهای مبتنی بر ساختار. 34
2.2.1 الگوریتم RPL.. 34
2.2.1.1 گراف مسیریابی جهت دار مبتنی بر مقصد (DODAG) 35
2.2.1.2 شناسههای پروتکل... 36
2.2.1.3 تشکیل مسیر در گراف.... 37
2.2.1.4 معیارهای وزن دهی مسیر در پروتکل RPL.. 38
2.2.2 الگوریتم LB_RPL.. 40
2.2.3 الگوریتم UDCB.. 41
2.2.4 الگوریتم UDDR.. 42
2.2.4.1 فاز انتخاب والد.. 43
2.2.4.2 حرکت خودخواهانه. 44
2.2.4.3 بازی مشترک.... 44
2.2.4.4 فاز اتصال.. 45
3 فصل سوم مدل شبکه مورد بررسی و تعریف مسأله مسیریابی بهینه. 47
3.1 همبندی شبکه. 48
3.2 چگالی گرهها 49
3.3 مدل لینک مخابراتی بیسیم. 49
3.4 مکانیزم دسترسی به کانال مخابراتی.. 50
3.5 تعریف مسأله توزیع ترافیک بهینه. 51
4 فصل چهارم الگوریتم مسیریابی درختی با هدف مصرف انرژی متوازن. 52
4.1 فاز ایجاد درخت... 54
4.2 بررسی اثر افزایش رنج مخابراتی.. 55
4.3 نحوه انتخاب والد ترجیحی.. 58
4.4 تحلیل پیچیدگی الگوریتم PBLD... 64
5 فصل پنجم چارچوب شبیهسازی و مقایسه نتایج عملکرد. 66
5.1 محیط شبیهسازی.. 67
5.2 پارامترهای شبیهسازی.. 68
5.3 سناریوهای شبیهسازی.. 70
5.4 نتایج شبیهسازی.. 70
5.4.1 عملکرد الگوریتم PBTR با توجه به تعداد گرهها 70
5.4.2 عملکرد الگوریتم PBTR با توجه به تعداد گرههای تولید کننده ترافیک... 72
5.4.3 عملکرد الگوریتم PBTR با توجه به نرخ تولید ترافیک متغییر. 74
6 فصل ششم جمعبندی و نتیجهگیری.. 77
منابع و مراجع. 81
فهرست اشکال
صفحه
شکل1‑1طبقه بندی مکانیزم های ذخیره سازی انرژی.. 3
شکل2‑1 معماری پیشنهادی ارتباطات سه لایه. 33
شکل4‑1یک برش از شبکه. 56
شکل 4‑2 برشی از شبکه بعد از افزایش رنج مخابراتی.. 57
شکل 5‑1 نمونهای از گراف مسیریابی الگوریتم PBTR.. 68
شکل 5‑2 نمودار میزان طول عمر الگوریتمها در برابر با تعداد گره ها 71
شکل 5‑3 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر تعداد گره ها 72
شکل 5‑4 نمودار میزان طول عمر الگوریتم ها در برابر تعداد گره های تولید کننده ترافیک.... 73
شکل 5‑5 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر تعداد گره های تولیدکننده ترافیک.... 74
شکل 5‑6 نمودار میزان طول عمر الگوریتم ها در برابر نرخ تولید ترافیک توسط گره ها 75
شکل 5‑7 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر نرخ نولید ترافیک توسط گره ها 76
منبع:
Rault, Tifenn, Abdelmadjid Bouabdallah, and Yacine Challal. "Energy Efficiency in Wireless Sensor Networks: a top-down survey. " Computer Networks 67 (2014): 104-122.
S. Cui, A. Goldsmith, A. Bahai, Energy-constrained modulation optimization, IEEE Trans. Wireless Commun. 4 (5) (2005)2349–2360.
F. M. Costa, H. Ochiai, A comparison of modulations for energy optimization, in: Wireless Sensor Network Links, IEEE GlobalTelecommunications Conference, 2010, pp. 1–5.
J. W. Jung, W. Wang, M. A. Ingram, Cooperative transmission range extension for duty cycle-limited wireless sensor networks, in: Int. Conf. on Wireless Communication, Vehicular Technology, Information Theory and Aerospace and Electronic Systems Technology, Chennai, 2011, pp. 1–5.
S. Jayaweera, Virtual MIMO-based cooperative communication for energy constrained wireless sensor networks, IEEE Trans. Wireless Commun. 5 (5) (2006) 984–989.
L. H. Correia, D. F. Macedo, A. L. dos Santos, A. A. Loureiro, J. M. S. Nogueira, “Transmission power control techniques for wireless sensor networks”, Comput. Netw. 51 (17) (2007) 4765–4779.
X. Chu, H. Sethu, Cooperative topology control with adaptation for improved lifetime in wireless ad hoc networks, in: IEEE INFOCOM, Orlando, FL, USA, 2012, pp. 262–270.
H. -N. Dai, Throughput and delay in wireless sensor networks usingdirectional antennas, in: 5th Int. Conf. on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, 2009, pp. 421–426.
A. P. Subramanian, S. R. Das, Addressing deafness and hidden terminal problem in directional antenna based wireless multi-hopnetworks, Wireless Netw. 16 (6) (2010) 1557–1567.
M. Masonta, Y. Haddad, L. D. Nardis, A. Kliks, O. Holland, Energyefficiency in future wireless networks: Cognitive radiostandardization requirements, in: IEEE 17th Int. Workshop onComputer Aided Modeling and Design of Communication Links andNetworks, Barcelone, 2012, pp. 31–35
M. Naeem, K. Illanko, A. Karmokar, A. Anpalagan, M. Jaseemuddin,Energy-efficient cognitive radio sensor networks: parametric andconvex transformations, Sensors 13 (8) (2013) 11032–11050.
E. Fasolo, M. Rossi, J. Widmer, M. Zorzi, In-network aggregationtechniquesfor wireless sensor networks: a survey, IEEE WirelessCommun. 14 (2) (2007) 70–87.
Z. Yan, V. Subbaraju, D. Chakraborty, A. Misra, K. Aberer, Energyefficientcontinuous activity recognition on mobile phones: anactivity-adaptive approach, in: 16th Int. Symp. on WearableComputers, Newcastle, 2012, pp. 17–24.
S. Wang, A. Vasilakos, H. Jiang, X. Ma, W. Liu, K. Peng, B. Liu, Y. Dong,Energy efficient broadcasting using network coding aware protocolin wireless ad hoc network, in: IEEE Int. Conf. on Communications(ICC), Kyoto, 2011, pp. 1–5.
N. Kimura, S. Latifi, A survey on data compression in wireless sensornetworks, in: Int. Conf. on Information Technology: Coding andComputing,Las Vegas, NV, 2005, pp. 8–13.
R. de Paz Alberola, D. Pesch, Duty cycle learning algorithm (DCLA)for IEEE 802. 15. 4 beacon-enabled wireless sensor networks, Ad HocNetw. 10 (4) (2012) 664–679.
R. Carrano, D. Passos, L. Magalhaes, C. Albuquerque, Survey andtaxonomy of duty cycling mechanisms in wireless sensor networks,IEEE Commun. Surv. Tutorials 16 (1) (2014) 181–194.
H. Ba, I. Demirkol, W. Heinzelman, Passive wake-up radios:from devices to applications, Ad Hoc Netw. 11 (8) (2013) 2605–2621.
S. Misra, M. P. Kumar, M. S. Obaidat, Connectivity preservinglocalized coverage algorithm for area monitoring using wirelesssensor networks, Comput. Commun. 34 (12) (2011) 1484–1496.
E. Karasabun, I. Korpeoglu, C. Aykanat, Active node determinationfor correlated data gathering in wireless sensor networks, Comput. Netw. 57 (5) (2013) 1124–1138.
D. Kumar, T. C. Aseri, R. Patel, EEHC: energy efficient heterogeneousclustered scheme for wireless sensor networks, Comput. Commun. 32 (4) (2009) 662–667.
H. Li, Y. Liu, W. Chen, W. Jia, B. Li, J. Xiong, COCA:constructingoptimal clustering architecture to maximize sensor networklifetime, Comput. Commun. 36 (3) (2013) 256–268.
A. Liu, J. Ren, X. Li, Z. Chen, X. S. Shen, Design principles andimprovement of cost function based energy aware routingalgorithms for wireless sensor networks, Comput. Netw. 56 (7)(2012) 1951–1967.
Z. Wang, E. Bulut, B. Szymanski, Energy efficient collision awaremultipath routing for wireless sensor networks, in: IEEE Int. Conf. on Communications, Dresden, 2009, pp. 1–5.
M. Radi, B. Dezfouli, K. A. Bakar, M. Lee, Multipath routing inwireless sensor networks: survey and research challenges, Sensors12 (1) (2012) 650–685.
S. Misra, N. E. Majd, H. Huang, Constrained relay node placement inenergy harvesting wireless sensor networks, in: IEEE 8th Int. Conf. on Mobile Adhoc and Sensor Systems, Valencia, 2011, pp. 2155–6806.
D. Dandekar, P. Deshmukh, Energy balancing multiple sink optimaldeployment in multi-hop wireless sensor networks, in: IEEE 3rdInt. Advance Computing Conference, Ghaziabad, 2013, pp. 408–412.
W. Liang, J. Luo, X. Xu, Prolonging network lifetime via a controlledmobile sink in wireless sensor networks, in: IEEE GlobalTelecommunications Conference, Miami, 2010, pp. 1–6.
R. Sugihara, R. Gupta, Optimizing energy-latency trade-off in sensornetworks with controlled mobility, in: IEEE INFOCOM, Rio deJaneiro, 2009, pp. 2566–2570.
P. Nintanavongsa, M. Naderi, K. Chowdhury, Medium access controlprotocol design for sensors powered by wireless energy transfer,in: IEEE INFOCOM, Turin, 2013, pp. 150–154.
K. Tutuncuoglu, A. Yener, Communicating using an energyharvesting transmitter: optimum policies under energy storagelosses, IEEE Trans. Wireless Commun. (2012) 1–11 (submitted forpublication), Available at.
L. Xie, Y. Shi, Y. Hou, A. Lou, Wireless power transfer andapplications to sensor networks, IEEE Wireless Commun. 20 (4)(2013) 140–145.
K. Kaushik, D. Mishra, S. De, S. Basagni, W. Heinzelman, K. Chowdhury, S. Jana, Experimental demonstration of multi-hop RFenergy transfer, in: IEEE 24th Int. Symp. on Personal Indoor andMobile Radio Communications, London, UK, 2013, pp. 538–542.
Dohler, M. ; Watteyne, T. ; Winter, T. ; Barthel, D. ; “Routing Requirements for Urban Low-Power and Lossy Networks”, RFC 5548, 2009.
Manap, Z. ; Ali, B. ; Ng, C. ; Noordin, N. ; Sali, A. ; “A Review on Hierarchical Routing Protocols for Wireless Sensor Networks”, Wireless Personal Communications, DOI 10. 1007/s11277-013-1056-5, 2013.
Martocci, J. ; De Mil, P. ; Riou, N. ; Vermeylen, W. ; “Building Automation Routing Requirements in Low-Power and Lossy Networks”, RFC 5867, 2010.
Yao Y, Gehrke J. Query processing in sensor networks, In Proceedings of the First Biennial Conference on Innovative Data Systems Research (CIDR), Asilomar, California, January 5–8, 2003; 46–55.
Madden S, Franklin M, Hellerstein J, Hong W. TinyDB: an acquisitional query processing system for sensor networks. ACM Transactions on Database Systems March 2005; 30(1): 122–173.
Madden S, Franklin M, Hellerstein J, Hong W. TAG: a tiny aggregation service for ad-hoc sensor networks, In Proceedings of the 5th symposium on Operating systems design and implementation, Boston, MA, USA, December 9–11, 2002.
Sadagopan N, Singh M, Krishnamachari B. Decentralized utility-based design of sensor networks. Mobile Networks and Applications 2006; 11(3): 341–350.
Al-Karaki JN, Kamal AE. Routing techniques in wireless sensor networks: a survey. IEEE Wireless Communications 2004; 11(6): 6–28.
Zhao L, Liu G, Chen J, Zhang Z. Flooding and directed diffusion routing algorithm in wireless sensor networks, In Proceedings of the 5th International Conference on Hybrid Intelligent Systems, Shenyang 2009. vol. 2, August 2009; 235–239.
Bouabdallah F, Bouabdallah N, Boutaba R. On balancing energy consumption in wireless sensor networks. IEEE Transactions on Vehicular Technology 2009; 58(6): 2909–2924.
Al-Karaki JN, Kamal AE. Routing techniques in wirelesssensor networks: a survey. IEEE Wireless Communications2004; 11(6): 6–28.
Wang, X. -h. ; Che, C. -m. ; Li, L. ; “Reliable multi-path routing protocol in wireless sensor networks” In Proceedings of the 2010 International Conference on Parallel and Distributed Computing,Applications and Technologies, p. p. 289–294, 2010.
Wang, Z. ; Bulut, E. ; Szymanski, B. K. ; “Energy efficient collision aware multipath routing for wireless sensor networks”, In Proceedings of the 2009 IEEE international conference oncommunications, 2009.
Gaddour, O. ; Kouba, A. ; "RPL in a nutshell: A survey", Computer Networks, Vol. 56, p. p. 3163-3178, 2012.
Shu, L. ; Zhang, Y. ; Yang, L. ; Wang, Y. ; “TPGF: geographic routing in wireless multimedia sensor networks”, Telecommunication Systems, Vol. 44, p. p. 79-95, 2010.
Felemban, E. ; Lee, C. ; Ekici, E. ; “MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks,” IEEE Trans. Mobile Comput. , vol. 5, no. 6, p. p. 738–754, 2006.
Kim, S.; “An Ant-based Multipath Routing Algorithm for QoS Aware Mobile Ad-hoc Networks”, Wireless Personal Communications, Vol. 66, p.p. 739-739, 2012.
Pi, S. ; Sun, B. ; “Fuzzy Controllers Based Multipath Routing Algorithm in MANET”, Physics Procedia, Vol. 24, p. p. 1178-1185, 2012.
Krishna, P. ; Saritha, V. ; Vedha, G. ; Bhiwal, A. ; Chawla, A. ; “Quality-of-service-enabled ant colony-based multipath routing for mobile ad hoc networks”, IET Communications, Vol. 6, No. 1, p. p. 76-84, 2012.
Villaverde, C. ; Rea, S. ; Pesch, D. ; “Inrout: A qos aware route selection algorithm for industrial wireless sensor networks”, Ad Hoc Networks, Vol. 10, No. 3, p. p. 458-483, 2012.
Tuah N, Ismail M. Extending lifetime of heterogenous wireless sensor network using relay node selection. International Conference of Information and Communication Technology (ICoICT) 2013; 1: 17–21. 2012; 23(9): 1762–1774.
Chu Y, Tseng C, Hung C, et al. Application of loadbalanced tree routing algorithm with dynamic modification to centralized wireless sensor networks. In IEEE Sensors, 2009; 1392–1395.
He, T. ; Stankovic, J. ; Lu, C. ; Abdelzaher, T. ; “SPEED: A stateless protocol for real-time communication in sensor networks,” in Proc. International Conference on Distributed Computing Systems, Providence, May 2003.
Xue, Y. ; Ramamurthy, B. ; Vuran, M. ; “SDRCS: A service differentiated real-time communication scheme for event sensing in wireless sensor networks”, Computer Networks, Vol. 55, p. p. 3287-3302, 2011.
Heinzelman WR, Chandrakasan A, Balakrishnan H, Energy – efficient communication protocol for wireless microsensor networks[C], Proc of the 33rd Intl Conf on System Sciences, 2000:1-10.
Zhao Y, Wu J, Li F, Lu S. On maximizing the lifetime of wireless sensor networks using virtual backbone scheduling. IEEE Transactions on Parallel and Distributed Systems 2012; 23(8): 1528–1535
Bala Krishna M, Doja MN. Self-organized energy conscious clustering protocol for wireless sensor networks. In 14th International Conference on Advanced Communication Technology, Pyeong Chang, Korea, 2012.
L. Q. Liu, “Balanced low-latency convergecast tree based on wireless sensor network,” Master Thesis. Chung Hua University, Hsinchu, Taiwan, 2003. (in Chinese)
H. Dai, and R. Han, “A node-centric load balancing algorithm for wireless sensor networks,” in proceedings of IEEE GLOBECOM '03,. vol. 1, pp. 548-552, 2003.
S. Phoha, T. LaPorta, and C. Griffin, “Sensor Network Operations,” John Wiley & Sons, Inc. Publication, 2006.
W. B. Heinzelman, A. P. Chandrakasan, H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670, 2002.
S. Lindsey, and C. S. Raghavendra, “PEGASIS: Power-efficient gathering in sensor information systems,” in proceedings of IEEE Aerospace Conference, vol. 3, pp. 1125-1130, Mar. 2002.
Huang C, Cheng R, Wu T, Chen S. Localized routing protocols based on minimum balanced tree in wireless sensor networks. In 5th International Conference on Mobile Ad-hoc and Sensor Networks, Waterloo, Canada, 2009; 503–510.
Chakraborty S, Chakraborty S, Nandi S, Karmakar S. Energy-efficient data gathering for road-side sensor networks ensuring reliability and fault-tolerance. In 27th International Conference on Advanced Information Networking and Applications (AINA), Barcelona, Spain, 2013; 189–196.
Tsao, T. ; Alexander, R. ; Dohler, M. ; Daza, V. ; Lozano, A. ; " A Security Threat Analysis for the Routing Protocol for Low-Power and Lossy Networks (RPLs)", RFC 7416, 2015.
Goyal, M. ; Baccelli, E. ; Philipp, M. ; Brandt, A. ; Matrocci, J. ; " Reactive Discovery of Point-to-Point Routes in Low-Power and Lossy Networks", RFC6997, 2013.
Levis, P. ; Clausen, T. ; Hui, J. ; Gnawali, O. ; Ko, J. ; "The Trickle Algorithm", RFC6206, 2011.
Vasseur, J. ; Kim, M. ; Pister, K. ; Dejean, N. ; Barthel, D. ; “Routing metrics used for path calculation in low-power and lossy networks”, RFC6551, 2012.
Karkazis, P. ; Trakadas, P. ; Leligou, H. ; Sarakis, L. ; Papaefstathiou, I. ; Zahariadis, T. ; “Evaluating routing metric composition approaches for QoS differentiation in low power and lossy networks”, Wireless Networks, doi:10. 1007/s11276-012-0532-2, December 2012.
Winter, T. ; Thubert, P. ; “RPL: IPv6 routing protocol for low-power and lossy networks”, RFC6550, 2012.
Xinxin L, Guo J, Bhatti G, Orlik P, Parsons K. Load balanced routing for low power and lossy networks. IEEE Wireless Communications and NetworkingConference (WCNC) 2013; 1: 2238–2243, DOI:10. 1109/WCNC. 2013. 6554908.
Behzadan A, Anpalagan A. Utility driven balanced communication (UDBC) algorithm for data Routing in wireless sensor networks. In 25th IEEE Biennial Symposium on Communications, Canada, Queen’s University, 2010; 187–192.
Behzadan, Afshin, et al. "An energy‐efficient utility‐based distributed data routing scheme for heterogenous sensor networks. " Wireless Communications and Mobile Computing (2014).
Hou, J. ; Li, N. ; Stojmenovic´, I. ; Handbook of sensor networks: Algorithms and architectures, chap. 10: Topology construction and maintenance in wireless sensor networks, Wiley Interscience, p. 315, 2005.
Rappaport, T. Wireless Communications: Principles and Practice, 2nd Edition, Prentice-Hall, 2002.
Nesary Moghadam, M. ; Taheri, H. ; Karrari, M. ; "Minimum cost load balanced multipath routing protocol for low power and lossy networks", Wireless Networks Vol. 20, No. 8, p. p. 2469-2479, 2014.
Shi, H. ; Yin, B. Adaptive clustering and transmission range adjustment for topology control in wireless sensor networks. Doctoral Dissertation, University of Missouri at Columbia Columbia, MO, USA, 2006.
Digi International Inc. XBee/XBee-PRO User's Manual v1. xEx, Sept. 2009.