• صفحه اصلی
  • جمع‌آوری داده آگاه به انرژی در شبکه‌های حسگر قابل شارژ با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات توسعه‌یافته

اشتراک گذاری

آدرس مقاله


کد مقاله : 13991008251461 بازدید : 5860 صفحه: 248 - 260

20.1001.1.16823745.1400.19.4.13.6

نوع مقاله: پژوهشی

جمع‌آوری داده آگاه به انرژی در شبکه‌های حسگر قابل شارژ با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات توسعه‌یافته

محورهای موضوعی : مهندسی برق و کامپیوتر

وحیده فراهانی 1 , لیلی فرزین وش 2 * , مینا زلفی لیقوان 3 , رحیم ابری لیقوان 4

1 - دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر
2 - دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر
3 - دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر
4 - دانشگاه تبریز،دانشکده مهندسی برق و کامپیوتر

تاریخ دریافت : 1399/10/08 تاریخ پذیرش : 1400/09/22 تاریخ انتشار : 1400/12/14

کلید واژه: الگوریتم بهینه‌سازی ازدحام ذرات, خوشه‌بندی, زمان‌بندی خواب گره‌ها, شبکه حسگر قابل شارژ, مسیریابی,

چکیده مقاله :

یک چالش مهم در شبکه‌های حسگر، جمع‌آوری داده با توجه به انرژی محدود گره‌ها است. استفاده از حسگرهای قابل شارژ برای جمع‌آوری اطلاعات و انتقال آنها به چاهک، مشکل محدودیت انرژی را تا حدی مرتفع می‌نماید. با توجه به نرخ پایین برداشت انرژی در گره‌های قابل شارژ، مدیریت مصرف انرژی در این شبکه‌ها امری ضروری است. الگوریتم‌های موجود، جنبه‌های مهم جمع‌آوری آگاه به انرژی- شامل زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی- را به صورت جامع بررسی نکرده‌اند و همچنین اکثر آنها از روش‌های حریصانه و با کارایی پایین استفاده نموده‌اند. در این مقاله، یک روش کارای مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات توسعه‌یافته به نام EDGR برای جمع‌آوری داده در شبکه‌های قابل شارژ ارائه شده است. در الگوریتم پیشنهادی، مسئله مورد نظر به سه مرحله زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی، تقسیم گردیده و مراحل به ترتیب حل شده‌اند. بر اساس نتایج شبیه‌سازی، الگوریتم EDGR مقدار متوسط و انحراف از معیار انرژی ذخیره‌شده در گره‌ها و همچنین نرخ گم‌شدن بسته‌ها را به مقدار قابل توجهي نسبت به روش‌های پیشین بهبود داده است.

چکیده انگلیسی:

This paper investigates the problem of data gathering in rechargeable Wireless Sensor Networks (WSNs). The low energy harvesting rate of rechargeable nodes necessitates effective energy management in these networks. The existing schemes did not comprehensively examine the important aspects of energy-aware data gathering including sleep scheduling, and energy-aware clustering and routing. Additionally, most of them proposed greedy algorithms with poor performance. As a result, nodes run out of energy intermittently and temporary disconnections occur throughout the network. In this paper, we propose an energy-efficient data gathering algorithm namely Energy-aware Data Gathering in Rechargeable wireless sensor networks (EDGR). The proposed algorithm divides the original problem into three phases namely sleep scheduling, clustering, and routing, and solves them successively using particle swarm optimization algorithm. As derived from the simulation results, the EDGR algorithm improves the average and standard deviation of the energy stored in the nodes by 17% and 5.6 times, respectively, compared to the previous methods. Also, the packet loss ratio and energy consumption for delivering data to the sink of this scheme is very small and almost zero

منابع و مأخذ:

[1] M. K. Singh, S. I. Amin, S. A. Imam, V. K. Sachan, and A. Choudhary, "A survey of wireless sensor network and its types," in Proc. of IEEE Int. Conf. on Advances in Computing, Communication Control and Networking, ICACCCN’18, pp. 326-330, Greater Noida, India, 12-13 Oct. 2018.
[2] Z. Jiao, L. Zhang, M. Xu, C. Cai, and J. Xiong, "Coverage control algorithm-based adaptive particle swarm optimization and node sleeping in wireless multimedia sensor networks," IEEE Access, vol. 7, pp. 170096-170105, Nov. 2019.
[3] P. Visu, T. S. Praba, N. Sivakumar, R. Srinivasan, and T. Sethukarasi, "Bio-inspired dual cluster heads optimized routing algorithm for wireless sensor networks," J. of Ambient Intelligence and Humanized Computing, vol. 12, no. 3, pp. 3753-3761, Mar. 2021.
[4] ن. نوروزی، ﻫ. طباطبایی ملاذی و م. فضلعلی، "EBONC: يک روش جديد خوشه‌بندي آگاه از انرژي، مبتني بر تعداد خوشه بهينه براي شبکه حسگر بي‌سيم متحرک،" نشریه مهندسی برق و کامپیوتر ایران، ب- مهندسي كامپيوتر، سال 14، شماره 4 ، صص. 310-299، زمستان 1395.
[5] M. Shafiq, H. Ashraf, A. Ullah, and S. Tahira, "Systematic literature review on energy efficient routing schemes in WSN-a survey," Mobile Networks and Applications, vol. 25, pp. 882-895, Jun. 2020.
[6] و. ستاري نائيني و ف. موحدي، "به کارگیری منطق فازی در انتخاب مناسب گره بعدی برای پیکربندی مسیر با پروتکل LEAP در شبکه‌های حسگر بی‌سیم،" نشریه مهندسی برق و کامپیوتر ایران، ب- مهندسي كامپيوتر، سال 15، شماره 4، صص. 304-295، زمستان 1396.
[7] K. S. Adu-Manu, N. Adam, C. Tapparello, H. Ayatollahi, and W. Heinzelman, "Energy-harvesting wireless sensor networks (EH-WSNs): a review," ACM Trans. on Sensor Networks, vol. 14, no. 2, Article No.: 10, 50 pp., May 2018.
[8] Q. Chen, et al., "Harvest energy from the water: a self-sustained wireless water quality sensing system," ACM Trans. on Embedded Computing Systems, vol. 17, no. 1, Article No.: 3, 24 pp., Jan. 2017.
[9] S. Kosunalp, "An energy prediction algorithm for wind-powered wireless sensor networks with energy harvesting," Energy, vol. 139, pp. 1275-1280, Nov. 2017.
[10] A. Bakar and J. Hester, "Making sense of intermittent energy harvesting," in Proc. of Int. Workshop on Energy Harvesting & Energy-Neutral Sensing Systems, SenSys’18, pp. 32-37, Shenzhen, China, 4-4 Nov. 2018.
[11] J. DeWitt and H. Shi, "Barrier coverage in energy harvesting sensor networks," Ad Hoc Networks, vol. 56pp. 72-83, 1 Mar. 2017.
[12] C. C. Lin, Y. C. Chen, J. L. Chen, D. J. Deng, S. B. Wang, and S. Y. Jhong, "Lifetime enhancement of dynamic heterogeneous wireless sensor networks with energy-harvesting sensors," Mobile Networks and Applications, vol. 22, no. 5, pp. 931-942, Oct. 2017.
[13] A. Bengheni, F. Didi, and I. Bambrik, "EEM-EHWSN: enhanced energy management scheme in energy harvesting wireless sensor networks," Wireless Networks, vol. 25, no. 6, pp. 3029-3046, Aug. 2019.
[14] T. Lu, G. Liu, W. Li, S. Chang, and W. Guo, "Distributed sampling rate allocation for data quality maximization in rechargeable sensor networks," J. of Network and Computer Applications, vol. 80, pp. 1-9, 15 Feb. 2017.
[15] S. Liu and Y. C. Chen, "Robust data collection for energy-harvesting wireless sensor networks," Computer Networks, vol. 167, Article ID: 107025, 11 Feb. 2020.
[16] G. Martinez, S. Li, and C. Zhou, "Wastage-aware routing in energy-harvesting wireless sensor networks," IEEE Sensors J., vol. 14, no. 9, pp. 2967-2974, Sep. 2014.
[17] H. Shafieirad, R. S. Adve, and S. Shahbazpanahi, "Opportunistic routing in large-scale energy harvesting sensor networks," in Proc. of IEEE GLOBECOM Workshops, 6 pp., Washington, DC, USA, 4-8 Dec. 2016.
[18] F. Li, M. Xiong, L. Wang, H. Peng, J. Hua, and X. Liu, "A novel energy-balanced routing algorithm in energy harvesting sensor networks," Physical Communication, vol. 27, no. C, pp. 181-187, Apr. 2018.
[19] J. Li and D. Liu, "An energy aware distributed clustering routing protocol for energy harvesting wireless sensor networks," in Proc. of IEEE/CIC Int. Conf. on Communications in China, ICCC’16, 6 pp., Chengdu, China, 27-29 Jul. 2016.
[20] D. Sharma and A. P. Bhondekar, "An improved cluster head selection in routing for solar energy-harvesting multi-heterogeneous wireless sensor networks," Wireless Personal Communications, vol. 108, no. 4, pp. 2213-2228, Oct. 2019.
[21] Y. Wu and W. Liu, "Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks," IET Wireless Sensor Systems, vol. 3, no. 2, pp. 112-118, Jun. 2013.
[22] S. Sarang, M. Drieberg, A. Awang, and R. Ahmad, "A QoS MAC protocol for prioritized data in energy harvesting wireless sensor networks," Computer Networks, vol. 144, pp. 141-153, 24 Oct. 2018.
[23] P. Zhong, Y. Zhang, S. Ma, J. Gao, and Y. Chen, "An adaptive MAC protocol for wireless rechargeable sensor networks," in Proc. of Int. Conf. on Wireless Algorithms, Systems, and Applications, WASA17, Lecture Notes in Computer Science, Springer, vol. 10251, 5 pp., May 2017.
[24] A. Pal and A. Nasipuri, "Joint power control and routing for rechargeable wireless sensor networks," IEEE Access, vol. 7, pp. 123992-124007, Aug. 2019.
[25] R. S. Liu, K. W. Fan, Z. Zheng, and P. Sinha, "Perpetual and fair data collection for environmental energy harvesting sensor networks," IEEE/ACM Trans. on Networking, vol. 19, no. 4, pp. 947-960, Nov. 2011.
[26] T. Lu, G. Liu, and S. Chang, "Energy-efficient data sensing and routing in unreliable energy-harvesting wireless sensor network," Wireless Networks, vol. 24, no. 2, pp. 611-625, Feb. 2018.
[27] R. R. Rout, M. S. Krishna, and S. Gupta, "Markov decision process-based switching algorithm for sustainable rechargeable wireless sensor networks," IEEE Sensors J., vol. 16, no. 8, pp. 2788-2797, Apr. 2016.
[28] X. Zhang, C. Wang, and L. Tao, "An opportunistic packet forwarding for energy-harvesting wireless sensor networks with dynamic and heterogeneous duty cycle," IEEE Sensors Letters, vol. 2, no. 3, 4 pp., Sept. 2018.
[29] H. Darji and H. B. Shah, "Genetic algorithm for energy harvesting-wireless sensor networks," in Proc. of IEEE Int. Conf. on Recent Trends in Electronics, Information & Communication Technology, RTEICT’16, pp. 1398-1402, Bangalore, India, 20-21 May 2016.
[30] J. Li and D. Liu, "DPSO-based clustering routing algorithm for energy harvesting wireless sensor networks," in Proc. of Int. Conf. on Wireless Communications & Signal Processing, WCSP’15, 5 pp., Nanjing, China, 15-17 Oct. 2015.
[31] M. Deb and S. Roy, "Harvested profile aware multi hop routing protocol for wireless sensor network," in Proc. of Int. Conf. on Emerging Applications of Information Technology, EAIT’18, 4 pp., Kolkata, India, 12-13 Jan. 2018.
[32] S. M. Bozorgi, A. S. Rostami, A. A. R. Hosseinabadi, and V. E. Balas, "A new clustering protocol for energy harvesting-wireless sensor networks," Computers & Electrical Engineering, vol. 64, pp. 233-247, Nov. 2017.
[33] M. M. Afsar and M. Youni, "A load-balanced cross-layer design for energy-harvesting sensor networks," J. of Network and Computer Applications, vol. 145, Article ID:. 102390, 1Nov. 2019.
[34] A. Ratnaweera, S. Halgamuge, and H. Watson, "Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients," IEEE Trans. on Evolutionary Computation, vol. 8, no. 3, pp. 240-255, Jun. 2004.
[35] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 660-670, Oct. 2002.
[36] H. Zhang and J. C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Ad Hoc & Sensor Wireless Networks, vol. 1, pp. 89-124, Jan. 2005.
[37] R. S. Y. Elhabyan and M. C. E. Yagoub, "Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network," J. of Network and Computer Applications, vol. 52, no. C, pp. 116-128, Jun. 2015.
متن کامل:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 19، شماره 4، زمستان 1400  1

مقاله پژوهشی

جمع‌آوری داده آگاه به انرژی در شبکه‌های حسگر قابل شارژ 
با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات توسعه‌یافته

وحیده فراهانی، لیلی فرزین‌وش، مینا زلفی لیقوان و رحیم ابری لیقوان

 

 

1 

چكیده: یک چالش مهم در شبکه‌های حسگر، جمع‌آوری داده با توجه به انرژی محدود گره‌ها است. استفاده از حسگرهای قابل شارژ برای جمع‌آوری اطلاعات و انتقال آنها به چاهک، مشکل محدودیت انرژی را تا حدی مرتفع می‌نماید. با توجه به نرخ پایین برداشت انرژی در گره‌های قابل شارژ، مدیریت مصرف انرژی در این شبکه‌ها امری ضروری است. الگوریتم‌های موجود، جنبه‌های مهم جمع‌آوری آگاه به انرژی- شامل زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی- را به صورت جامع بررسی نکرده‌اند و همچنین اکثر آنها از روش‌های حریصانه و با کارایی پایین استفاده نموده‌اند. در این مقاله، یک روش کارای مبتنی بر الگوریتم بهینه‌سازی ازدحام ذرات توسعه‌یافته به نام EDGR برای جمع‌آوری داده در شبکه‌های قابل شارژ ارائه شده است. در الگوریتم پیشنهادی، مسئله مورد نظر به سه مرحله زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی، تقسیم گردیده و مراحل به ترتیب حل شده‌اند. بر اساس نتایج شبیه‌سازی، الگوریتم EDGR مقدار متوسط و انحراف از معیار انرژی ذخیره‌شده در گره‌ها و همچنین نرخ گم‌شدن بسته‌ها را به مقدار قابل توجهي نسبت به روش‌های پیشین بهبود داده است.

 

کلیدواژه: الگوریتم بهینه‌سازی ازدحام ذرات، خوشه‌بندی، زمان‌بندی خواب گره‌ها، شبکه حسگر قابل شارژ، مسیریابی.

1-       مقدمه

یک شبکه حسگر بی‌سیم2 مجموعه‌ای از گره‌های حسگر است که وظیفه نظارت بر محیط را بر عهده دارند. این گره‌ها مشخصات محیط مانند دما، رطوبت و فشار را اندازه‌گیری کرده و اطلاعات جمع‌آوری شده را به چاهک3 ارسال می‌کنند. از شبکه‌های حسگر برای نظارت بر محیط‌های مختلف استفاده می‌شود که از آن جمله می‌توان به کاربردهای نظامی، کنترل و مدیریت شرایط بحرانی و تحقیقات در حیات جانداران اشاره کرد [1]. یکی از چالش‌های مهم در شبکه‌های حسگر، مدیریت مصرف انرژی در گره‌ها است. هر گره برای جمع‌آوری داده از محیط اطراف خود و همچنین انتقال داده، انرژی مصرف می‌کند. مصرف بی‌رویه انرژی منجر به مرگ زودهنگام گره‌ها می‌شود. در این حالت ممکن است پوشش برخی نواحی دچار مشکل شده و یا ارتباط بخش‌هایی از شبکه با چاهک قطع شود. برای مدیریت مصرف انرژی روش‌های مختلفی پیشنهاد شده که از آن جمله می‌توان به زمان‌بندی خواب گره‌ها4 [2]، خوشه‌بندی5 [3] و [4] و مسیریابی آگاه به انرژی [5] و [6] اشاره کرد.

استفاده از گره‌های حسگر قابل شارژ6 روشی کارا برای مقابله با مسئله محدودیت انرژی است [7]. این گره‌ها از منابع محیطی مختلف مانند نور خورشید، باد و گرما، انرژی برداشت7 کرده و آن را به انرژی الکتریکی تبدیل می‌کنند [8] تا [10]. انرژی الکتریکی حاصل ذخیره شده و برای جمع‌آوری و انتقال داده استفاده می‌شود. با توجه به نرخ پایین برداشت انرژی از محیط، نحوه مصرف انرژی در شبکه‌های قابل شارژ باید مدیریت شود. در این راستا، مسئله جمع‌آوری داده آگاه به انرژی در شبکه‌های حسگر قابل شارژ در مقالات مختلفی بررسی شده است. این الگوریتم‌ها جنبه‌های مختلف جمع‌آوری داده از جمله زمان‌بندی خواب حسگرها [11] تا [13]، برقراری پوشش کامل [11] و [12]، تنظیم نرخ ارسال داده [14] و [15]، مسیریابی [16] تا [18] و خوشه‌بندی [19] تا [21] را مورد مطالعه قرار داده‌اند.

ایراد الگوریتم‌های ارائه‌شده آن است که هیچ کدام از آنها همه جنبه‌های جمع‌آوری داده را مد نظر قرار نداده‌اند. همچنین اکثر این روش‌ها به دلیل استفاده از روش‌های حریصانه8 کارایی کمی دارند. الگوریتم‌های ارائه‌شده در [11] و [12]، مسئله پوشش و ارتباط زمان‌بندی خواب گره‌ها با آن را بررسی نموده‌اند. روش‌های پیشنهادی در [13]، [22] و [23]، فقط لایه پیوند داده9 را مطالعه کرده و به سایر جوانب مسئله جمع‌آوری داده نپرداخته‌اند. مراجع [14] تا [18] و [24] تا [27] فقط مسئله مسیریابی را مورد توجه قرار داده‌اند. در [28] روشی حریصانه برای زمان‌بندی خواب گره‌ها و مسیریابی ارائه شده است. الگوریتم‌های ارائه‌شده در [19]، [29] و [30] به خوشه‌بندی گره‌های قابل شارژ پرداخته‌اند. در [29] و [30] از روش‌های بهینه‌سازی برای خوشه‌بندی استفاده شده است. نحوه کدینگ10 و تابع هزینه11 تعریف‌شده در این مقالات کارا نبوده و منجر به تولید جواب‌های مناسب نمی‌شوند. در [20]، [21] و [31] تا [33] برای جمع‌آوری داده ابتدا خوشه‌بندی انجام شده و سپس مسیریابی برای سرخوشه‌ها12 انجام می‌گردد. این مقالات روش‌هایی حریصانه برای خوشه‌بندی و مسیریابی ارائه داده‌اند و بنابراین کارایی پایینی دارند.

در این مقاله، الگوریتمی آگاه به انرژی برای جمع‌آوری داده‌ها در شبکه‌های حسگر بی‌سیم قابل شارژ به نام 13EDGR ارائه شده است. الگوریتم EDGR از سه تکنیک زمان‌بندی خواب گره‌ها، خوشه‌بندی آگاه به انرژی و مسیریابی آگاه به انرژی، برای مدیریت مصرف انرژی استفاده می‌کند. بر این اساس، الگوریتم به سه مرحله زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی تقسیم شده و مراحل مذکور به ترتیب حل می‌شوند. در طراحی الگوریتم EDGR به این نکته توجه شده که نرخ برداشت انرژی در بازه‌های زمانی مختلف تقریباً ثابت است [11]، [14]، [20]، [25]، [32] و [33]. بنابراین مقدار تقریبی انرژی ذخیره‌شده در هر گره در یک بازه زمانی- که در ادامه دور نامیده می‌شود- تقریباً مشخص است. با توجه به ثابت‌بودن پارامترهای مسئله، می‌توان الگوریتم‌های فراابتکاری14 را برای حل مسئله به کار برد. مراحل روش پیشنهادی با استفاده از یک الگوریتم بهینه‌سازی ازدحام ذرات15(PSO)  توسعه‌یافته به نام PSO-TVAC [34] حل شده‌اند. الگوریتم PSO-TVAC مشکل گیرافتادن در دام کمینه محلی16 را تا حد زیادی حل کرده و جواب‌های مناسبی را با سرعت بالا تولید می‌نماید.

در ادامه، نحوه حل زیرمسایل الگوریتم EDGR توضیح داده شده‌اند. در مرحله اول، بخشی از گره‌ها که انرژی کمتری دارند به حالت خواب می‌روند. در اینجا به این نکته توجه شده که در شبکه‌های با تعداد گره زیاد، تنوع ذرات و اندازه فضای جواب17 قابل توجه است. به منظور کوچک‌کردن فضای حالت، شبکه به چندین بخش تقسیم شده و وضعیت گره‌ها در هر بخش به صورت مستقل بررسی می‌شود. در هر بخش، نحوه انتخاب گره‌ها باید به گونه‌ای باشد که شبکه به صورت کامل پوشش داده شود. بنابراین تابع برازندگی18 بر اساس مقدار انرژی و تعداد گره‌های بیدار و میزان پوشش تعریف شده است. همچنین یک ذره19، مشخص‌کننده وضعیت گره‌ها است. در ادامه، گره‌های بیدار در مرحله دوم خوشه‌بندی می‌شوند. معیارهای در نظر گرفته شده برای خوشه‌بندی، شامل انرژی سرخوشه‌ها و انرژی لازم برای ارسال داده به آنها است. در مرحله پایانی، یک درخت برای انتقال داده از سرخوشه‌ها به چاهک ساخته می‌شود. در اینجا هدف، انتخاب تعداد محدودی گره پرانرژی برای ساخت درخت است. بر اساس نتایج شبیه‌سازی، الگوریتم EDGR کارایی بسیار بالاتری نسبت به روش‌های قبلی دارد.

در ادامه این مقاله، در بخش 2 الگوریتم‌های زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی موجود بر روی شبکه‌های حسگر معمولی و قابل شارژ بررسی شده‌اند. مدل شبکه در بخش 3 آورده شده است. الگوریتم PSO-TVAC که برای حل مراحل روش پیشنهادی استفاده می‌شود، در بخش 4 معرفی گردیده و سپس الگوریتم EDGR در بخش 5 توضیح داده شده است. در بخش 6، کارایی روش پیشنهادی با روش‌های موجود مقایسه گردیده و نهایتاً مقاله در بخش 7 جمع‌بندی شده است.

2-       مروری بر کارهای قبلی

شبکه‌های حسگر قابل شارژ در مقالات متعددی بررسی شده‌اند. روش‌های ارائه‌شده، جنبه‌های مختلف شبکه از جمله پوشش، زمان‌بندی خواب، خوشه‌بندی، کنترل نرخ ارسال و مسیریابی را مد نظر قرار داده‌اند.

مسئله زمان‌بندی خواب گره‌ها در شبکه‌های حسگر قابل شارژ در [11] و [12] بررسی شده است. مرجع [11] پوشش مرزی img0تایی با استفاده از گره‌های قابل شارژ را بررسی کرده است. در اینجا هدف، بیشینه‌کردن مقدار img0 با استفاده از زمان‌بندی خواب مناسب برای گره‌ها است. روش پیشنهادی در [12] مسئله پوشش تعدادی هدف را مطالعه کرده است. در این تحقیق فرض شده که شبکه شامل گره‌های معمولی و قابل شارژ می‌باشد و هدف، پوشش اهداف با استفاده حداکثری از حسگر‌های قابل شارژ است. مسئله مورد نظر با استفاده از الگوریتم جستجوی هارمونی20 مدل و حل شده است. الگوریتم ارائه‌شده در [13]، مسئله زمان‌بندی خواب در شبکه‌های حسگر قابل شارژ مبتنی بر لایه پیوند داده 21CSMA/CD را مطالعه کرده است. در این روش، دوره‌های زمانی خواب حسگرها به نحوی تنظیم می‌شوند که میزان مصرف انرژی گره‌ها متعادل باشد و همچنین نرخ ارسال هم‌زمان گره‌های متداخل22 کاهش یابد. مدیریت لایه پیوند داده در شبکه‌های حسگر قابل شارژ در [22] و [23] نیز بررسی شده است. هدف روش‌های ارائه‌شده در این مقالات، مدیریت مصرف انرژی و کاهش نرخ گم‌شدن بسته‌ها23 است.

مراجع [14] تا [18] و [24] تا [28] مسیریابی در شبکه‌های حسگر قابل شارژ را مطالعه نموده‌اند. الگوریتم‌های ارائه‌شده را می‌توان به دو دسته کلی تقسیم نمود. در دسته اول، نرخ تولید داده ثابت در نظر گرفته شده است. در این الگوریتم‌ها هدف، مدیریت مصرف انرژی و کمینه‌نمودن نرخ گم‌شدن داده است. در [16] برای ساخت مسیر از الگوریتم 24DSR استفاده شده است. در این روش، هزینه یک مسیر با توجه به دو معیار مشخص می‌شود: بیشینه‌نمودن انرژی گره‌ها با احتساب انرژی برداشتی پیش‌بینی شده و کمینه‌کردن میزان انرژی برداشت‌نشده به دلیل محدودیت ظرفیت باتری گره‌ها. مسیریابی فرصت‌طلبانه25 در [17] و [28] مطالعه شده است. در [17] برای تعیین گره گام بعدی26 از معیارهای میزان انرژی و فاصله از چاهک استفاده شده است. روش پیشنهادی در [28] زمان‌بندی خواب را با مسیریابی فرصت‌طلبانه ترکیب نموده است. در اینجا حالت گره‌ها (خواب یا بیداربودن) در دور بعدی با توجه به میزان انرژی برداشتی پیش‌بینی شده تعیین گردیده است.

دسته دوم الگوریتم‌های مسیریابی، نرخ تولید داده را با توجه به مقدار انرژی برداشت‌شده تنظیم می‌کنند. روش ارائه‌شده در [14] نرخ برداشت انرژی را ثابت در نظر گرفته است. در اینجا نرخ تولید داده با استفاده از چهارچوب بهینه‌سازی 27NUM تنظیم شده است. با استفاده از این چهارچوب، نرخ تولید داده توسط گره‌ها به صورت توزیع‌شده مشخص می‌شود. در [25] نیز فرض گردیده که نرخ برداشت انرژی در دورهای مختلف ثابت بوده و از قبل مشخص است. بر این اساس، یک مدل بهینه برای بیشینه‌کردن نرخ داده تولیدشده توسط حسگرها ارائه گردیده است. مرجع [26] تنظیم نرخ تولید داده در شبکه‌های مبتنی بر لایه پیوند داده CSMA/CD را بررسی کرده است. نحوه حل مسئله در این مقاله مشابه [14] است. در [15] ابتدا یک درخت پوشا بر روی حسگرها ساخته شده است. این درخت به گونه‌ای ساخته می‌شود که نرخ تولید داده حسگرها که مشخص‌کننده نرخ مصرف انرژی آنها است، در شرایط مختلف قابل قبول باشد. در ادامه با توجه به نرخ برداشت انرژی در دور کنونی، نرخ تولید داده با استفاده از برنامه‌ریزی تصادفی28 تنظیم شده است.

خوشه‌بندی گره‌های قابل شارژ در [19]، [29] و [30] مورد مطالعه قرار گرفته است. در این الگوریتم‌ها، سرخوشه‌ها به صورت مستقیم داده‌ها را به چاهک ارسال می‌کنند. الگوریتم خوشه‌بندی ارائه‌شده در [19] پروتکل LEACH [35] را توسعه داده است. احتمال انتخاب گره‌ها به عنوان سرخوشه با توجه به دو معیار میزان انرژی و همچنین مقدار پیش‌بینی شده برای انرژی برداشتی در دور کنونی تعیین شده است. روش پیشنهادی در [30] از الگوریتم بهینه‌سازی ازدحام ذرات برای خوشه‌بندی استفاده کرده است. یک ذره آرایه‌ای شامل اعضای خوشه‌ها و سرخوشه‌ها است که در آن، ابتدا اعضای هر خوشه و در انتها سرخوشه‌ها آورده شده‌اند. برای مقداردهی اولیه یک ذره، سرخوشه‌ها از گره‌های پرانرژی انتخاب شده و گره‌های دیگر به صورت تصادفی به یکی از خوشه‌ها ملحق می‌شوند. تابع برازندگی با توجه به انرژی فعلی گره‌ها و انرژی لازم برای ارسال داده‌ها تعریف شده است. ضعف عمده الگوریتم، تعریف نامناسب ذرات برای خوشه‌بندی گره‌ها است. همچنین در تعریف تابع برازندگی به میزان انرژی برداشت‌شده در دور کنونی توجه نشده است.

مراجع [21] و [29] از الگوریتم ژنتیک29 برای خوشه‌بندی استفاده کرده‌اند. در [21] ابتدا سرخوشه‌های اولیه انتخاب شده و گره‌های دیگر به صورت تصادفی به سرخوشه‌ها ملحق شده‌اند. برای تولید نسل جدید از ادغام تک‌نقطه‌ای30 استفاده شده است. الگوریتم مذکور روشی برای جهش31 کروموزوم‌ها ارائه نداده است. مرجع [29] از کدینگ دودویی استفاده کرده که برای ساخت خوشه مناسب نمی‌باشد. همچنین مقالات مذکور در تعریف تابع برازندگی به انرژی برداشت‌شده از محیط توجه نکرده‌اند. الگوریتم پیشنهادی در [20] گره‌های سرخوشه را به صورت حریصانه و بر اساس مقدار انرژی گره‌ها و میزان برداشت انرژی توسط آنها در دور قبلی، انتخاب می‌کند. در اینجا مقدار برداشت در دور قبلی به عنوان تخمینی از انرژی برداشت‌شده در دور کنونی در نظر گرفته شده است. در [20] و [21] مسیریابی به صورت حریصانه انجام شده است.

معیارهای انتخاب سرخوشه‌ها در [32] شامل میزان انرژی گره‌ها و همچنین مقدار برداشت انرژی در دور کنونی است. در الگوریتم پیشنهادی، اندازه خوشه‌ها بر مبنای فاصله آنها از چاهک تنظیم شده و بنابراین نرخ مصرف انرژی در سرخوشه‌های نزدیک چاهک کاهش می‌یابد. در روش مسیریابی پیشنهادی، گره گام بعدی بر اساس میزان انرژی مصرفی برای ارسال انرژی تعیین می‌شود. الگوریتم ارائه‌شده در [33] نیز سرخوشه‌ها را بر اساس مقدار انرژی گره‌ها و میزان برداشت در دور کنونی مشخص کرده است. همچنین اندازه خوشه‌ها بر اساس فاصله آنها از چاهک تعیین شده‌اند. در اینجا داده به صورت چندگامی به چاهک ارسال می‌شود. برای یک سرخوشه مفروض، گره گام بعدی از بین سرخوشه‌هایی که به چاهک نزدیک‌تر هستند انتخاب می‌شود. معیارهای انتخاب این گره شامل میزان انرژی سرخوشه مفروض و گره گام بعدی، میزان برداشت آنها در دور کنونی و انرژی لازم برای انتقال داده بین دو گره است.

3-       مدل سیستم

در این بخش، فرضیات و مدل شبکه حسگر قابل شارژ مفروض و نیز مدل مصرف انرژی در گره‌های حسگر توضیح داده می‌شود.

3-1 فرضیات و مدل شبکه

شبکه مورد نظر شامل img0 گره است که به صورت تصادفی در محیطی با ابعاد img0 پراکنده شده‌اند و شعاع پوشش و ارسال همه گره‌ها برابر در نظر گرفته شده است. همچنین اندازه شعاع ارسال که با نماد img0 نشان داده می‌شود، دو برابر شعاع پوشش است. مجموعه همسایگان گره img0 که در شعاع ارسال آن قرار دارند با img0 نشان داده می‌شود. ظرفیت باتری گره‌ها برای ذخیره انرژی برابر بوده و با img0 نمایش داده می‌شود. فرض شده که باتری گره‌ها در ابتدا به صورت کامل شارژ شده‌اند. هر گره حسگر دارای دو حالت فعال و خواب است. میزان مصرف انرژی در حالت خواب ناچیز و قابل صرف نظر فرض شده است. همچنین گره‌ها قابل شارژ در نظر گرفته شده‌اند. در الگوریتم پیشنهادی، زمان اجرا به یک سری دور به طول img0 تقسیم شده است. مشابه [11]، [14]، [20]، [25]، [32] و [33]، نرخ برداشت انرژی در هر دور ثابت در نظر گرفته شده که مقدار آن با نماد img0 نشان داده می‌شود. مقدار انرژی ذخیره‌شده در گره img0 در ابتدا و انتهای دور فعلی به ترتیب با نمادهای img0 و img0 نمایش داده می‌شود. ارتباط بین این دو متغیر در (1) آورده شده است

img0        (1)

گره img0 برای انتقال داده، مقداری انرژی مصرف می‌کند. انرژی گره در انتهای دور با احتساب انرژی مصرفی با نماد img0 نشان داده می‌شود. رابطه (2) نحوه محاسبه img0 را بیان می‌کند

img0        (2)

که در آن img0 نرخ مصرف انرژی گره img0 در دور فعلی است. مقدار این متغیر وابسته به مدل مصرف انرژی است و در بخش 3-2 محاسبه خواهد شد.

ليست متغیرهای استفاده‌شده در جدول 1 آورده شده است.

3-2 مدل مصرف انرژی

میزان مصرف انرژی با استفاده از مدل ارائه‌شده در [35] محاسبه می‌شود. بر اساس این مدل، میزان انرژی لازم برای ارسال و دریافت یک بسته به طول img0 به ترتیب از (3) و (4) به دست می‌آید. در این روابط img0 و img0 به ترتیب نشان‌دهنده مقدار انرژی لازم برای ارسال و دریافت بسته هستند. همچنین پارامتر img0 بیانگر فاصله بین گره فرستنده img0 و گره گیرنده img0 است. مطابق (3)، میزان انرژی مصرفی برای ارسال بسته  وابسته  به img0  است.  در  صورتی  که  این  پارامتر  کمتر  از  حد  آستانه 

 

جدول 1: متغیرهای استفاده‌شده.

 

مفهوم

متغیر

تعداد گره‌ها

img0 

ابعاد شبکه

img0 و img0

شعاع ارسال

img0 

مجموعه همسایگان گره img0

img0 

ظرفیت باتری هر گره برای ذخیره انرژی

img0 

طول هر دور

img0 

نرخ برداشت انرژی در دور فعلی

img0 

مقدار انرژی ذخیره‌شده گره img0 در ابتدای دور فعلی

img0 

مقدار انرژی ذخیره‌شده گره img0 در انتهای دور فعلی

img0 

مقدار انرژی گره img0 در انتهای دور فعلی

img0 

نرخ مصرف انرژی گره img0 در دور فعلی

img0 

 

img0 كه برابر img0 است باشد، از مدل فضای آزاد32 و در غیر این صورت از مدل محوشدگی ناشی از چندمسیرگی33 برای محاسبه img0 استفاده می‌شود. پارامترهای img0 و img0 به ترتیب بيانگر انرژی مصرفی تقویت‌کننده34 در مدل‌های فضای آزاد و محوشدگی ناشی از چندمسیرگی هستند. مقدار این پارامترها برابر 2pJ/bit/m 10 و 4pJ/bit/m 0013/0 است. پارامتر img0 نیز بیانگر انرژی مصرفی مدار بوده و مقدار آن برابر nJ/bit 50 می‌باشد

img0        (3)

img0        (4)

در ادامه مقدار متغیر img0 با استفاده از (3) و (4) محاسبه می‌شود. این متغیر برابر مجموع نرخ انرژی مصرفی برای ارسال و دریافت داده است

img0        (5)

که در آن img0 و img0 به ترتیب برابر نرخ انرژی مصرفی گره برای ارسال و دریافت داده به/ از گره همسایه img0 است. مقادیر این متغیرها به ترتیب در (6) و (7) محاسبه شده‌اند

img0        (6)

img0        (7)

که در این روابط، img0 نرخ ارسال داده از گره img0 به گره img0 است. انتقال داده از اعضای خوشه‌ها به سرخوشه‌ها و همچنین از هر گره به گام 
بعدی آن صورت می‌پذیرد و بنابراین فقط در این موارد مقدار متغیر img0 مثبت است.

4-       الگوریتم PSO-TVAC

الگوریتم بهینه‌سازی ازدحام ذرات یک روش فراابتکاری الهام‌گرفته از رفتار اجتماعی پرندگان برای حل مسایل بهینه‌سازی است. در این روش ابتدا تعدادی جواب اولیه تصادفی که ذره نامیده می‌شوند، تولید می‌گردد. این ذرات فضای جواب را جستجو کرده تا جواب بهینه را پیدا کنند. ذره img0ام شامل بردار مکان img0 و بردار سرعت img0 است. بردار سرعت، نحوه حرکت ذره در فضای جواب را مشخص می‌کند. همچنین پارامترهای img0 و img0 به ترتیب نشان‌دهنده بعد فضا و تعداد تکرار اجرای الگوریتم هستند. مقادیر بردارهای مکان و سرعت ذرات ابتدا به صورت تصادفی تعیین شده و در هر تکرار در راستای افزایش برازندگی به روز رسانی می‌شوند. ابتدا بردار img0 بر اساس بهترین جواب پیداشده توسط همه ذرات img0 و بهترین جواب پیداشده توسط خود ذره img0 به روز رسانی می‌شود (رابطه (8)). منظور از بهترین جواب پیداشده، جوابی است که بیشترین ارزش (کمترین هزینه) را با توجه به تابع برازندگی (تابع هزینه) تعریف‌شده داشته باشد. سپس مکان ذره با استفاده از (9) به روز رسانی می‌شود

img0        (8)

img0        (9)

که در آن img0 نشان‌دهنده وزن اینرسی35 است. این پارامتر تأثیر سرعت فعلی ذره img0 بر سرعت آن در تکرار بعدی را کنترل می‌کند. پارامترهای img0 و img0 به ترتیب بیانگر ضرایب خودشناختی36 و نفوذ اجتماعی37 هستند. همچنین img0 و img0 دو بردار تصادفی img0بعدی هستند که مقادیر درایه‌های آنها از بازه img0 انتخاب می‌شود. به روز رسانی ذرات تا هنگام برآورده‌شدن شرط خاتمه ادامه خواهد داشت. این شرط به صورت مشخص‌کردن تعداد تکرارهای اجرای الگوریتم، دستیابی به یک مقدار برازندگی مشخص و یا ثابت‌ماندن مقدار img0 به دست آمده در چندین تکرار متوالی تعریف می‌شود.

نقطه ضعف الگوریتم بهینه‌سازی ازدحام ذرات، احتمال گیرافتادن در بهینه محلی است. این مشکل به دلیل عدم اکتشاف38 مناسب در فضای جواب و همگرایی سریع ذرات به img0 است. برای بهبود کارایی 
این الگوریتم روش‌های بسیاری ارائه شده‌اند که از آن جمله می‌توان به PSO-TVAC [34] اشاره کرد. این الگوریتم، پارامترهای img0 و img0 را مطابق (10) و (11) به صورت خطی کاهش می‌دهد. همچنین img0 مطابق (12) در حین اجرای الگوریتم افزایش داده می‌شود. با تنظیم پارامترها توانایی اکتشاف افزایش یافته و احتمال گیرافتادن در بهینه محلی کمتر می‌شود

img0        (10)

img0        (11)

img0        (12)

در اینجا img0 تعداد تکرارهای اجرای الگوریتم است. مقادیر سایر پارامترهای استفاده‌گردیده در جدول 2 آمده است.

روندنمای الگوریتم PSO-TVAC در شکل 1 آورده شده است.

 

جدول 2: مقادیر پارامترهای الگوریتم PSO-TVAC.

 

مقدار

پارامتر

9/0

img0 

4/0

img0 

5/2

img0 

5/0

img0 

5/0

img0 

5/2

img0 

 

5-       الگوریتم EDGR

جمع‌آوری آگاه به انرژی داده یک چالش اساسی در شبکه‌های حسگر است و استفاده از حسگرهای قابل شارژ مشکل محدودیت انرژی را تا حدی برطرف می‌کند. با وجود این، با توجه به نرخ پایین برداشت انرژی در این شبکه‌ها، ارائه الگوریتم‌های جمع‌آوری داده آگاه به انرژی ضروری است. در این راستا الگوریتم EDGR در این مقاله ارائه شده است. این الگوریتم شامل سه مرحله زمان‌بندی خواب گره‌ها، خوشه‌بندی آگاه به انرژی و مسیریابی آگاه به انرژی است که به صورت متوالی اجرا می‌شوند. برای حل مراحل فوق از الگوریتم PSO-TVAC استفاده شده و مراحل الگوریتم در بخش‌های 5-1 تا 5-3 توضیح داده شده‌اند.

5-1 زمان‌بندی خواب گره‌ها

در روش پیشنهادی برای زمان‌بندی خواب حسگرها، تعدادی از گره‌ها برای پوشش و ارسال داده به چاهک فعال شده و بقیه حسگرها به حالت خواب می‌روند. در انتخاب مجموعه گره‌های فعال دو شرط باید لحاظ شوند: 1) گره‌های فعال کل شبکه را پوشش دهند و 2) هر گره فعال به چاهک متصل بوده و مسیری برای ارسال داده به چاهک داشته باشد. با توجه به این که شعاع ارسال دو برابر شعاع پوشش فرض شده است، در صورت پوشش کامل شبکه شرط اتصال نیز برآورده خواهد شد [36] و بنابراین در ادامه فقط مسئله پوشش کامل بررسی می‌شود.

الگوریتم ارائه‌شده ابتدا منطقه تحت نظارت را ناحیه‌بندی کرده و سپس مسئله پوشش را در هر ناحیه به صورت جداگانه بررسی می‌کند. دلیل این مسئله، کوچک‌کردن فضای جواب و در نتیجه کاهش پیچیدگی است. برای حل مسئله پوشش در هر بخش، از الگوریتم PSO-TVAC استفاده شده است. پس از زمان‌بندی خواب گره‌ها در هر ناحیه، قسمت کوچکی از آن پوشش داده نشده می‌ماند و بنابراین در ادامه یک روش حریصانه برای پوشش قسمت‌های باقیمانده ارائه شده است. قسمت‌های روش پیشنهادی در بخش‌های 5-1-1 تا 5-1-3 بررسی شده‌اند.

5-1-1 ناحیه‌بندی ناحیه تحت پوشش

چالشی که برای حل مسئله پوشش وجود دارد، بزرگی فضای جواب آن است. هر گره در هر دور در یکی از دو حالت فعال و خواب قرار دارد و بنابراین اندازه فضای جواب برای شبکه‌ای با img0 گره برابر img0 خواهد بود. مشخص است که یافتن مجموعه گره‌های فعال مناسب برای شبکه‌هایی با اندازه معمولی بسیار زمان‌بر خواهد بود. استراتژی به کار گرفته شده برای حل این چالش، تقسیم شبکه به ناحیه‌هایی با img0 گره و بررسی مسئله پوشش در هر ناحیه به صورت جداگانه است. اندازه فضای جواب برای مسئله پوشش یک بخش برابر img0 خواهد بود که نسبت به فضای حالت مسئله اصلی بسیار کوچک‌تر است. در شبیه‌سازی‌های انجام‌شده، گره‌ها  به  ناحیه‌های  50  گرهی  تقسیم  شده  و  هر  ناحیه  به  صورت  مستقل 

img0 

شکل 1:  روندنمای الگوریتم PSO-TVAC.

 

بررسی شده است. شکل 2 نحوه اعمال تکنیک ناحیه‌بندی پیشنهادی بر روی یک شبکه مفروض را نمایش می‌دهد.

روندنمای الگوریتم پیشنهادی برای زمان‌بندی خواب گره‌ها در شکل 3 نشان داده شده است.

5-1-2 زمان‌بندی خواب گره‌ها در ناحیه Rk

در این بخش نحوه زمان‌بندی خواب گره‌ها در ناحیه img0 توضیح داده شده است. این ناحیه شامل مجموعه گره‌های img0 می‌باشد که در آن، گره img0 معادل img0امین گره در شبکه است. در ادامه، بخش‌های مختلف الگوریتم پیشنهادی، شامل تعریف ذره، نحوه دیکدنمودن39 و تابع برازندگی بیان شده‌اند.

تعریف ذره: ذره img0 آرایه‌ای به طول img0 است که در آن، درایه img0 متناظر با گره img0 تعریف شده است و مقدار هر درایه، عددی در بازه img0 است. در روش پیشنهادی، مقداردهی اولیه ذرات به صورت تصادفی انجام می‌شود. در شکل 4 یک ذره مفروض برای مسئله زمان‌بندی خواب گره‌ها در ناحیه اول شکل 2 (شکل 2- ب) نمایش داده شده است. درایه‌های این ذره، متناظر با گره‌های ناحیه مورد نظر یعنی مجموعه img0 هستند.

دیکدکردن: دیکدکردن ذره img0 با توجه به مقدار درایه‌های آن انجام می‌شود. اگر مقدار درایه img0 کمتر از 7/0 باشد، گره img0 به حالت خواب می‌رود و در غیر این صورت گره فعال خواهد بود. برای مثال در ذره نمایش داده شده در شکل 4، مقادیر درایه‌های متناظر با گره‌های img0، img0، img0، img0 و img0 بیشتر از 7/0 است، بنابراین این گره‌ها فعال شده و بقیه گره‌ها به حالت خواب می‌روند.

تابع برازندگی: برای انتخاب گره‌های فعال، سه معیار پوشش، مقدار انرژی  و تعداد  گره‌های  فعال  مورد توجه قرار گرفته‌اند. هدف افزایش سطح 

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

شکل 2:  ناحیه‌بندی و مشخص‌کردن گره‌های فعال در یک شبکه مفروض، (الف) ناحیه‌بندی، (ب) مشخص‌کردن گره‌های فعال ناحیه اول، (ج) مشخص‌کردن گره‌های فعال در سایر ناحیه‌ها و (د) گره‌های فعال شبکه.

 

تحت پوشش، افزایش مقدار متوسط انرژی گره‌های فعال و کاهش تعداد آنها است. بر این اساس، تابع برازندگی ذره img0 به صورت ترکیب خطی این سه معیار در (13) تعریف شده است

img0 

شکل 3:  روندنمای الگوریتم زمان‌بندی خواب گره‌ها.

 

img0 

شکل 4:  ذره متناظر با ناحیه اول شکل 2 برای مسئله زمان‌بندی خواب گره‌ها.

 

img0        (13)

که در آن img0 نشان‌دهنده برازندگی ذره img0 است. متغیرهای img0 و img0 به ترتیب مساحت پوشش داده شده توسط گره‌های فعال در ناحیه img0 و مساحت کل آن هستند. همچنین img0 یک متغیر دودویی است که بیانگر حالت گره img0 است. این متغیر در صورتی که گره img0 فعال باشد برابر یک و در غیر این صورت برابر صفر خواهد بود. ضرایب img0، img0 و img0 میزان تأثیر معیارهای بررسی‌شده را مشخص می‌کنند. مقادیر این ضرایب به ترتیب برابر 2/0، 4/0 و 4/0 در نظر گرفته شده‌اند. نکته 
دیگر، نرمال‌سازی معیارهای انتخاب‌شده در تابع برازندگی است. معیارهای مساحت پوشش داده شده، مقدار متوسط انرژی گره‌های فعال و تعداد آنها به ترتیب با استفاده از مساحت img0، انرژی اولیه و تعداد گره‌ها در ناحیه مورد نظر، نرمال شده‌اند.

5-1-3 پوشش قسمت‌های باقیمانده

الگوریتم ارائه‌شده در بخش قبلی تا حد زیادی در حدود 90% الی 95% پوشش ایجاد می‌کند. دستیابی به پوشش کامل با این الگوریتم عملاً امکان‌پذیر نیست، زیرا افزایش مقدار ضریب img0 (و در نتیجه کاهش img0 و img0) مصرف انرژی را شدیداً افزایش می‌دهد. برای پوشش قسمت‌های باقیمانده یک روش حریصانه ارائه گردیده که در شکل 5 توضیح داده شده است. در اینجا ابتدا مجموعه img0 تشکیل می‌شود. این مجموعه شامل گره‌هایی است که در حالت خواب قرار گرفته‌اند و مقدار انرژی آنها که با متغیر img0 نشان داده می‌شود، از یک حد آستانه مشخص (50% ظرفیت باتری) بیشتر است. در ادامه، گام‌های زیر تا هنگامی که پوشش کامل ایجاد شود تکرار می‌شوند. ابتدا به ازای هر گره img0، مساحت قسمت پوشش داده شده توسط آن که با img0 نمایش داده می‌شود، محاسبه می‌گردد. سپس وضعیت گرهی که بیشترین مساحت تحت پوشش 

 

 

1) مجموعه img0 شامل گره‌های پرانرژی (گره‌هایی که انرژی آنها بیشتر از 50% ظرفیت باطری است) که در حالت خواب قرار دارند، تشکیل شود.

2) تا هنگامی که پوشش کامل ایجاد نشده است مراحل زیر تکرار شود:

     2-1) مقدار img0 برای هر گره img0 محاسبه شود.

     2-2) گره‌هایی که مقدار img0 آنها صفر است از img0 حذف گردد.

     2-3) وضعیت گرهی که بیشترین مقدار img0 را دارد به فعال تغییر داده شود و

     همچنین این گره از img0 حذف گردد.

3) در صورت عدم پوشش کامل، از گره‌های کم‌انرژی برای کامل‌کردن پوشش استفاده شود. برای انتخاب گره‌های مناسب مطابق گام 2 عمل گردد.

 

شکل 5:  ایجاد پوشش کامل در شبکه.

 

img0 

شکل 7:  ذره متناظر با شکل 6 برای مسئله خوشه‌بندی.

 

را دارد، از خواب به فعال تغییر داده می‌شود. در صورتی که پس از بررسی گره‌های موجود در img0 قسمت پوشش داده نشده‌ای باقی مانده باشد، از گره‌های کم‌انرژی برای کامل‌کردن پوشش استفاده خواهد شد.

شکل 6 وضعیت گره‌های شکل 2- د را پس از پوشش قسمت‌های باقیمانده نشان می‌دهد. همان طور که در این شکل دیده می‌شود، وضعیت گره img0 برای ایجاد پوشش کامل به فعال تغییر داده شده است.

5-2 خوشه‌بندی آگاه به انرژی

پس از برقراری پوشش کامل در شبکه، نحوه انتقال داده‌های جمع‌آوری شده به چاهک مشخص می‌شود. برای این منظور، ابتدا گره‌های فعال خوشه‌بندی شده و سپس یک درخت شامل گره‌های سرخوشه ساخته می‌شود. در این بخش، الگوریتم خوشه‌بندی پیشنهادی معرفی گردیده و برای خوشه‌بندی از الگوریتم PSO-TVAC استفاده شده است. در ادامه بخش‌های مختلف روش پیشنهادی، شامل تعریف ذره، نحوه دیکدنمودن و تابع برازندگی بررسی شده‌اند.

تعریف ذره: ذره img0 یک آرایه دوبعدی به طول img0 است و پارامتر img0 نشان‌دهنده تعداد گره‌های سرخوشه می‌باشد. در شبیه‌سازی‌های انجام‌شده، مقدار این پارامتر برابر img005/0 در نظر گرفته شده است. همچنین مقادیر ابعاد اول و دوم به ترتیب از بازه‌های img0 و img0 به صورت تصادفی مشخص می‌شوند.

در شکل 7 مثالی از یک ذره برای شبکه شکل 6 نمایش داده شده است. با توجه این شکل، چهار سرخوشه در شبکه انتخاب خواهند شد.

دیکدکردن: هر درایه ذره img0 متناظر با یک گره سرخوشه است. درایه img0 شامل دو مقدار عددی است که به ترتیب در بازه‌های img0 و img0 قرار دارند. این مقادیر مختصات یک نقطه در سطح شبکه را مشخص می‌کنند. گرهی که کمترین فاصله با نقطه مذکور را داشته باشد به عنوان سرخوشه انتخاب خواهد شد.

برای تکمیل فرایند خوشه‌بندی، اعضای هر خوشه باید مشخص شوند. با توجه به تابع برازندگی تعریف‌شده، این کار برای محاسبه برازندگی 
ذره img0 ضروری است. در روش پیشنهادی، گره img0 به سرخوشه‌ای می‌پیوندد که در شعاع ارسال آن قرار داشته و پیوستن به آن کمترین هزینه را داشته باشد. هزینه پیوستن گره img0 به سرخوشه img0، سرخوشه متناظر با img0، به صورت (14) محاسبه می‌گردد

img0 

شکل 6:  ایجاد پوشش کامل برای شبکه شکل 2- د.

 

img0        (14)

که در آن img0 بیانگر هزینه انتخاب سرخوشه img0 توسط گره img0 است. همچنین img0 فاصله بین گره img0 و سرخوشه img0 را نمایش می‌دهد. با توجه به مدل انرژی ارائه‌شده در بخش 3-2، img0 متناسب با مقدار انرژی مصرفی گره img0 برای ارسال داده به img0 است. همچنین img0 بیانگر تعداد اعضای img0 (خوشه img0ام متناظر با img0) و متغیر img0 نیز نشان‌دهنده تعداد گره‌های فعال است. در تابع هزینه ارائه‌شده، متغیرهای img0 و img0 به ترتیب با استفاده از img0 و متوسط تعداد اعضای خوشه‌ها که برابر img0 است، نرمال شده‌اند. همچنین مقدار ضریب img0 برابر 5/0 فرض گردیده است.

در ادامه، نحوه دیکدکردن ذره ارائه‌شده در شکل 7 بررسی گردیده است. ابتدا نقاط متناظر با درایه‌های ذره مفروض در شکل 7 بر روی شبکه مشخص شده و نزدیک‌ترین گره‌ها به این نقاط به عنوان سرخوشه انتخاب می‌شوند (شکل 8- الف) و سپس فرایند خوشه‌بندی با استفاده از (14) انجام می‌گردد. خوشه‌بندی متناظر با ذره شکل 7 در شکل 8- ب نشان داده شده است.

تابع برازندگی: برای خوشه‌بندی آگاه به انرژی، چند معیار مد نظر قرار گرفته است. معیار اول انتخاب گره‌های پرانرژی به عنوان سرخوشه است. دلیل این مسئله آن است که گره‌های سرخوشه برای تجمیع داده‌های جمع‌آوری شده و ارسال آنها به چاهک انرژی زیادی مصرف می‌کنند. معیار دوم، کاهش انرژی مصرفی برای جمع‌آوری داده در خوشه‌ها است. آخرین معیار کاهش تعداد گره‌های خوشه‌بندی نشده است. گره‌های خوشه‌بندی نشده در شعاع ارسال هیچ کدام از سرخوشه‌ها نبوده و بنابراین نمی‌توان آنها را خوشه‌بندی نمود. با توجه به معیارهای بیان‌شده، برازندگی ذره img0 به صورت زیر تعریف می‌شود

img0        (15)

در این رابطه، ضرایب img0، img0 و img0 به ترتیب میزان اهمیت معیارهای انرژی سرخوشه‌ها، انرژی اعضای خوشه‌ها و تعداد گره‌های خوشه‌بندی نشده را نشان می‌دهند. مقادیر این ضرایب به ترتیب برابر 4/0، 2/0 و 4/0 در نظر گرفته شده است.

img0 

(الف)

img0 

(ب)

 

[1] این مقاله در تاریخ 26 دی ماه 1399 دریافت و در تاریخ 11 مهر ماه 1400 بازنگری شد.

وحیده فراهانی، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، (email: v_farahani96@ms.tabrizu.ac.ir).

لیلی فرزین‌وش (نویسنده مسئول)، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، (email: l.farzinvash@tabrizu.ac.ir).

مینا زلفی لیقوان، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، (email: mzolfy@tabrizu.ac.ir).

رحیم ابری لیقوان، دانشکده مهندسی برق و کامپیوتر، دانشگاه تبریز، تبریز، ایران، (email: abri.rahim@yahoo.com).

[2] . Wireless Sensor Network

[3] . Sink

[4] . Sleep Scheduling

[5] . Clustering

[6] . Rechargeable

[7] . Harvesting

[8] . Greedy

[9] . MAC Layer

[10] . Coding

[11] . Cost Function

[12] . Cluster Head

[13] . Energy-Aware Data Gathering in Rechargeable Wireless Sensor Networks

[14] . Meta-Heuristic

[15] . Particle Swarm Optimization

[16] . Local Optimum

[17] . Solution Space

[18] . Fitness Function

[19] . Particle

[20] . Harmony Search Algorithm

[21] . Carrier Sense Multiple Access/Collision Detection

[22] . Interfering

[23] . Packet Loss Ratio

[24] . Dynamic Source Routing

[25] . Opportunistic Routing

[26] . Next Hop

[27] . Network Utility Maximization

[28] . Stochastic Programming

[29] . Genetic Algorithm

[30] . Single-Point Crossover

[31] . Mutation

[32] . Free Space Model

[33] . Multi-Path Fading Channel Model

[34] . Amplifier

[35] . Inertia Weight

[36] . Self-Cognition

[37] . Social Influence

[38] . Exploitation

[39] . Decoding

شکل 8:  دیکدکردن ذره شکل 7، (الف) مشخص‌کردن سرخوشه‌ها و (ب) مشخص‌کردن اعضای خوشه‌ها.

 

img0 

شکل 9:  ذره متناظر با شکل 8 برای مسئله مسیریابی.

 

 

1) به ازای هر سرخوشه img0 مراحل زیر انجام شود:

     1-1) img0

     1-2) تا هنگامی که چاهک ملاقات‌نشده مراحل زیر انجام شود:

          1-2-1) گره img0 با بیشترین مقدار img0 که شرایط زیر را 

          دارد به عنوان گام بعدی انتخاب شود:

               - img0

               - img0

          1-2-2) img0

 

شکل 10:  دیکدکردن ذره img0.

 

5-3 مسیریابی آگاه به انرژی

در این مرحله به منظور اتصال گره‌های سرخوشه به چاهک، یک درخت بر روی این گره‌ها و برخی از گره‌های فعال غیر سرخوشه ساخته می‌شود. الگوریتمی مبتنی بر PSO-TVAC برای ساخت درخت مسیریابی پیشنهاد شده است. در روش پیشنهادی تعریف ذره و نحوه دیکدکردن با توجه به الگوریتم پیشنهادی در [37] انجام شده است. در ادامه پس از تعریف ذره متناظر با درخت مسیریابی، نحوه دیکدکردن آن توضیح داده شده و سپس تابع برازندگی پیشنهادی جهت ساخت درخت آگاه به انرژی ارائه گردیده است.

تعریف ذره: ذره img0 آرایه‌ای به طول img0 (تعداد گره‌های فعال) است و درایه‌های این آرایه در بازه img0 قرار دارند. مقداردهی اولیه ذرات نیز به صورت تصادفی است. شکل 9 یک نمونه ذره برای مسیریابی در شبکه شکل 8- ب را نمایش می‌دهد.

دیکدکردن: درایه img0 متناظر با img0امین گره فعال است که با img0 نشان داده می‌شود و مقدار img0 میزان مطلوبیت گره img0 برای ارسال داده را مشخص می‌کند. برای تشکیل درخت مسیریابی، مسیری بین هر سرخوشه img0 و چاهک به صورت جداگانه ساخته می‌شود. بدین منظور، ابتدا گام بعدی img0 مشخص شده و این کار تا رسیدن به چاهک ادامه می‌یابد. برای تعیین گام بعدی گره img0 که بر روی مسیر بین img0 و چاهک قرار دارد، گره‌های همسایه آن که فعال بوده و به چاهک نزدیک‌تر هستند، بررسی می‌شوند. گرهی که بیشترین مقدار img0 را دارد به عنوان گام بعدی انتخاب می‌شود. تفاوت روش دیکد نمودن پیشنهادی با [37] در بررسی شرط نزدیک‌تربودن گام بعدی به چاهک است. در 
[37] همه گره‌های همسایه، بدون توجه به فاصله آنها از چاهک مورد بررسی قرار می‌گیرند. این کار باعث می‌شود که فضای مسئله به صورت کنترل‌نشده‌ای بزرگ شده و یافتن جواب مناسب دشوار گردد. به علاوه، انتخاب گره‌های دورتر از چاهک به عنوان گام بعدی مسیر را طولانی‌تر کرده و متوسط انرژی مصرفی را افزایش می‌دهد. بنابراین به احتمال زیاد انتخاب گره‌های دورتر منجر به یافتن جواب مناسب نخواهد شد. جزئیات نحوه دیکدنمودن ذره img0 در شکل 10 بیان شده است.

شکل 11 مراحل ساخت درخت مسیریابی متناظر با ذره شکل 9 را به تصویر کشیده است. ابتدا مراحل ساخت مسیر بین سرخوشه اول (گره img0) و چاهک نشان داده شده است. مطابق شکل 11- الف، گام بعدی گره img0 از بین گره‌های img0 و img0 انتخاب خواهد شد. با توجه به ساختار ذره img0، گره img0 به عنوان گام بعدی img0 انتخاب می‌شود. در ادامه با بررسی مقادیر img0 و img0، گره img0 به عنوان گام بعدی img0 انتخاب می‌شود و همین روند تا تکمیل درخت مسیریابی ادامه می‌یابد.

تابع برازندگی: تابع برازندگی ذره img0 که با img0 نشان داده می‌شود، در (16) تعریف شده است. برای محاسبه img0، دو معیار انرژی گره‌ها و تعداد گره‌های درخت مسیریابی مد نظر قرار گرفته‌اند. معیار انرژی به صورت متوسط انرژی گره‌های فعال پس از انتقال داده در دور فعلی یا به عبارت دیگر img0، تعریف می‌شود. در اینجا img0 درخت مسیریابی متناظر با img0 و img0 تعداد گره‌های این درخت هستند. معیار انرژی معرفی‌شده منجر به انتخاب گره‌های پرانرژی برای ارسال داده می‌شود. همچنین مقدار داده عبور داده شده و در نتیجه نرخ انرژی مصرفی، توسط گره‌های درخت متوازن خواهد شد

img0        (16)

در (16) معیارهای متوسط انرژی گره‌های درخت و تعداد آنها به ترتیب با img0 و img0 نرمال شده‌اند و مقدار img0 نیز 5/0 در نظر گرفته شده است.

6-       نتایج شبیه‌سازی

در این بخش مورد کارایی الگوریتم EDGR بررسی قرار گرفته است.

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

شکل 11:  دیکدکردن ذره شکل 9، (الف) مشخص‌کردن گام بعدی گره img0، (ب) مشخص‌کردن گام بعدی گره img0، (ج) ساخت مسیر بین گره img0 و چاهک و (د) ساخت درخت مسیریابی.

 

برای این منظور، روش پیشنهادی با دو الگوریتم CREST [33] و EHTEAR [20] مقایسه شده و برای پیاده‌سازی الگوریتم‌ها از نرم‌افزار متلب1 استفاده گردیده است. معیارهای ارزیابی کارایی الگوریتم‌ها شامل میانگین و انحراف از معیار انرژی ذخیره‌شده در گره‌ها و نرخ گم‌شدن بسته‌ها است. برای افزایش دقت نتایج، هر آزمایش بر روی پنج شبکه مختلف تکرار شده و مقدار متوسط به عنوان نتیجه گزارش شده است. شبیه‌سازی‌ها بر روي شبكه‌هاي 300 و 500 گرهي اجرا شده‌اند. شعاع پوشش و ارسال گره‌ها به ترتیب برابر m 20 و m 40 در نظر گرفته شده‌اند. همچنين ابعاد شبكه مفروض برابر img0 است و حسگر‌ها به صورت تصادفی در آن پخش شده‌اند. در شبيه‌سازي‌هاي انجام‌شده، ظرفیت ذخیره‌سازی حسگرها img0 J 2 فرض شده و همچنين دو نرخ تولید داده 50 بیت/ ثانیه و 100 بیت/ ثانیه مورد بررسي قرار گرفته‌اند. نرخ برداشت انرژی براي همه گره‌ها يكسان بوده و برابر µJ/s 8 می‌باشد و زمان شبیه‌سازی هشت ساعت، معادل هشت دور اجرای الگوریتم‌ها در نظر گرفته شده است.

6-1 میانگین انرژی ذخیره‌شده در گره‌ها

گره‌های حسگر برای جمع‌آوری داده از سطح شبکه و ارسال آنها به شبکه انرژی مصرف می‌کنند. بیشتربودن مقدار انرژی گره‌ها به معنای توانایی بالاتر در ایجاد پوشش کامل و اتصال در سطح شبکه است. مقادیر انرژی ذخیره‌شده توسط الگوریتم EDGR و سایر روش‌های بررسی‌شده در طی دورهای متوالی در شکل‌هاي 12 و 13 مقایسه گردیده‌اند. اين شكل‌ها به ترتيب شبکه‌های 300 و 500 گرهی را مورد بررسي قرار داده‌اند. با توجه به نتايج گزارش‌شده، میانگین انرژی ذخیره‌گردیده با افزایش نرخ ارسال کم شده و همچنین مقدار این معیار با افزایش تعداد گره‌ها کاهش یافته است. نکته دیگر آن است که میزان انرژی ذخیره‌شده به مرور زمان کاهش یافته و بعد از مدتی به مقدار ثابتی می‌رسد. در ابتدا گره‌ها از انرژی اولیه و همچنین انرژی برداشت‌شده برای جمع‌آوری داده و ارسال آن استفاده می‌کنند. در این حالت نرخ مصرف انرژی کمتر از نرخ برداشت است و بنابراین سطح انرژی ذخیره‌شده گره‌ها کاهش می‌یابد. به تدریج سیستم به حالت پایدار2 رسیده و بین میزان انرژی مصرفی و انرژی برداشت‌شده در حسگرها تعادل ایجاد می‌شود.

انرژی ذخیره‌شده توسط الگوریتم پیشنهادی در شبکه‌های 300 گرهی به ترتیب 9% و 14% بیشتر از CREST و EHTEAR است و میزان بهبود در شبکه‌های 500 گرهی به ترتیب برابر 8% و 13% می‌باشد. شایان ذکر است که در نتایج ارائه‌شده، نرخ گم‌شدن بسته‌های روش‌های مذکور در نظر گرفته نشده و هر بسته در یک مسیر چندگامی به سمت چاهک ارسال می‌شود. این کار مستلزم مصرف انرژی توسط گره‌های قرارگرفته بر روی مسیر است. بنابراین گم‌شدن بسته‌ها، میزان انرژی مصرفی را کاهش خواهد داد. همان طور که در بخش 6-3 نشان داده شده است، دو الگوریتم CREST و EHTEAR نرخ گم‌شدن بالایی دارند. این مسئله به نحو محسوسی میزان انرژی مصرفی آنها را کاهش و انرژی ذخیره‌شده در گره‌ها را افزایش می‌دهد.

نتایج به دست آمده نشان‌دهنده توانایی الگوریتم EDGR در مدیریت مصرف انرژی است. عملکرد بهتر الگوریتم پیشنهادی به دلیل طراحی آگاه به انرژی آن است. عوامل مختلفی کارایی EDGR را افزایش داده‌اند 
که از آن جمله می‌توان به استفاده از الگوریتم PSO-TVAC برای خوشه‌بندی  و  مسیریابی  اشاره  کرد.  این  الگوریتم  به  دلیل  استفاده  از 

img0 

(الف)

img0 

(ب)

 

[1] . MATLAB

[2] . Stable

شکل 12:  مقایسه انرژی ذخيره‌شده در شبکه‌های 300 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

img0 

(الف)

img0 

(ب)

 

شکل 13:  مقایسه انرژی ذخيره‌شده در شبکه‌های 500 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

روش‌های بهینه‌سازی، دید جامعی از فضای جواب دارد و بنابراین می‌تواند جواب‌های مناسب را پیدا کند. از طرف دیگر، الگوریتم‌های CREST و EHTEAR به صورت حریصانه خوشه‌بندی و مسیریابی را انجام می‌دهند و در نتیجه کارایی این روش‌ها در مقایسه با EDGR کمتر است. همچنین در نظر گرفتن میزان انرژی مصرفی در توابع برازندگی روش‌های پیشنهادی برای خوشه‌بندی (روابط (14) و (15)) و مسیریابی (رابطه (16))، میزان انرژی مصرفی را کاهش داده است. عامل بعدی استفاده از تکنیک زمان‌بندی خواب گره‌ها می‌باشد. در هر دور، فقط تعدادی از گره‌ها فعال خواهند بود و گره‌هایی که به حالت خواب رفته‌اند انرژی مصرف نمی‌کنند. همچنین تعداد گره‌های بیدار در تابع برازندگی روش زمان‌بندی خواب پیشنهادی لحاظ شده است و بنابراین میزان مصرف انرژی کاهش می‌یابد.

6-2 انحراف از معیار انرژی گره‌ها

این معیار نشان‌دهنده میزان تعادل در انرژی ذخیره‌شده در گره‌ها است. اگر ذخیره انرژی در حسگرها متوازن نباشد، ممکن است باتری برخی گره‌ها موقتاً خالی شود و در این حالت ممکن است علی‌رغم وجود گره‌های پرانرژی، پوشش کامل و یا اتصال در سطح شبکه به صورت مقطعی دچار مشکل گردد. هرچه میزان ذخیره انرژی گره‌ها متعادل‌تر باشد، مقدار انحراف از معیار کمتر خواهد بود و بنابراین الگوریتمی عملکرد بهتری دارد که انحراف از معیار آن کمتر باشد. مقدار انحراف از معیار حاصل از الگوریتم‌های بررسی‌شده در شکل‌های 14 و 15 آورده شده است. بر اساس نتایج ارائه‌شده در شکل 14، انحراف از معیار الگوریتم EDGR در شبکه‌های حسگر 300 گرهی به ترتیب 370% و 470% نسبت به CREST و EHTEAR کمتر است. با توجه به شکل 15، در شبکه‌های 500 گرهی، مقدار بهبود این معیار توسط الگوریتم پیشنهادی نسبت به دو روش دیگر به ترتیب برابر 220% و 280% است. همچنین مشابه نمودارهای بخش 6-1، در اینجا نیز ابتدا مقدار انحراف از معیار افزایش یافته و بعد از مدتی به حالت پایدار می‌رسد.

توازن بالاتر الگوریتم پیشنهادی به علت در نظر گرفتن معیار انرژی در توابع برازندگی مراحل مختلف آن است. در روش زمان‌بندی خواب پیشنهادی، در هر دور گره‌های کم‌انرژی به حالت خواب رفته و انرژی مصرف نمی‌کنند. این گره‌ها با برداشت انرژی از محیط، میزان انرژی خود را بالا برده و بنابراین میزان اختلاف در انرژی ذخیره‌شده گره‌های مختلف کاهش می‌یابد. در روش ارائه‌شده برای خوشه‌بندی، گره‌های پرانرژی به عنوان سرخوشه انتخاب می‌شوند. همچنین میزان انرژی در پایان دور که با متغیر img0 نشان داده می‌شود، در انتخاب سرخوشه و گره‌های درخت مسیریابی لحاظ شده است. استفاده از این معیار باعث متوازن‌شدن انرژی مصرفی گره‌ها و کاهش انحراف از معیار می‌گردد.

img0 

(الف)

img0 

(ب)

 

شکل 14:  انحراف از معیار انرژی ذخیره‌شده در شبکه‌های 300 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

img0 

(الف)

img0 

(ب)

 

شکل 15:  انحراف از معیار انرژی ذخیره‌شده در شبکه‌های 500 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

6-3 نرخ گم‌شدن بسته‌ها

نرخ برداشت انرژی در شبکه‌های قابل شارژ به طور معمول پایین است و بنابراین در صورتی که مصرف انرژی در گره‌ها مدیریت نشود، ذخیره انرژی برخی از گره‌ها سریعاً تمام می‌شود. در این حالت این گره‌ها قادر به جمع‌آوری داده از محیط و ارسال داده‌های خود و سایرین نخواهند بود. در نتیجه قسمتی از داده‌های جمع‌آوری شده از سطح شبکه به چاهک نمی‌رسند و یا اصطلاحاً گم می‌شوند. نرخ گم‌شدن الگوریتم‌های EDGR، CREST و EHTEAR در شکل‌های 16 و 17 مورد بررسی قرار گرفته است. همان طور که در این شکل‌ها دیده می‌شود، نرخ گم‌شدن الگوریتم EDGR تقریباً برابر صفر است. همچنین این معیار براي الگوريتم‌هاي CREST و EHTEAR در شبكه‌هاي 300 گرهي به ترتيب برابر 58% و 30% است. در شبکه‌های 500 گرهی، نرخ گم‌شدن بسته توسط روش‌هاي مذكور به ترتيب برابر 75% و 46% است.

معیار نرخ گم‌شدن بسته‌ها وابسته به میانگین و انحراف از معیار انرژی ذخیره‌شده در گره‌ها است. با توجه به نتایج ارائه‌شده در بخش‌های 6-1 و 6-2، الگوریتم پیشنهادی مقدار انرژی گره‌ها را در سطح بالایی نگه داشته و همچنین نرخ مصرف انرژی در آنها را تا حد زیادی متوازن نموده است. بنابراین احتمال تخلیه باتری گره‌ها، مخصوصاً گره‌های مستقر در مکان‌های بحرانی مانند اطراف چاهک به شدت کاهش یافته است. در نتیجه همان طور که در شکل‌های 16 و 17 نشان داده شده است، نرخ گم‌شدن داده توسط الگوریتم EDGR به نحو قابل ملاحظه‌ای کمتر از سایر روش‌های بررسی‌شده و نزدیک صفر است.

7-       نتیجه‌گیری

در این مقاله، الگوریتم EDGR برای جمع‌آوری آگاه به انرژی داده در شبکه‌های حسگر قابل شارژ ارائه شده است. روش پیشنهادی از سه مرحله مبتنی بر الگوریتم PSO-TVAC، شامل زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی تشکیل شده است. در مرحله اول برای افزایش کیفیت جواب به دست آمده، محیط تحت نظارت به چند بخش تقسیم شده و هر بخش به صورت جداگانه بررسی شده است. تابع برازندگی برای مشخص‌نمودن گره‌های روشن در هر بخش با استفاده از معیارهای سطح تحت پوشش و مقدار انرژی ذخیره‌شده در انتهای دور و تعداد گره‌های فعال تعریف شده است. در مرحله بعدی، گره‌های فعال خوشه‌بندی شده‌اند. در این مرحله، خوشه‌ها با توجه به مقدار انرژی سرخوشه‌ها در پایان دور، میزان انرژی مصرفی برای ارسال داده به آنها و تعداد اعضای خوشه‌ها ساخته شده‌اند. در مرحله نهایی، مسیریابی آگاه به انرژی برای انتقال داده از سرخوشه‌ها به چاهک انجام شده است. بر اساس نتایج شبیه‌سازی، الگوریتم EDGR کارایی قابل توجهی نسبت به روش‌های پیشین دارد. دلیل این مسئله دید جامع روش پیشنهادی نسبت به جنبه‌های 

img0 

(الف)

img0 

(ب)

 

شکل 16:  نرخ گم‌شدن بسته در شبکه‌های 300 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

img0 

(الف)

img0 

(ب)

 

شکل 17:  نرخ گم‌شدن بسته در شبکه‌های 500 گرهی، (الف) نرخ ارسال 50 بيت/ ثانيه و (ب) نرخ ارسال 100 بيت/ ثانيه.

 

 

مختلف مسئله جمع‌آوری داده، مانند زمان‌بندی خواب گره‌ها، خوشه‌بندی و مسیریابی است. همچنین استفاده از الگوریتم PSO-TVAC در مراحل مختلف، کارایی روش پیشنهادی را افزایش داده است. راه حل‌های به دست آمده به دلیل حرکت در راستای توابع برازندگی معرفی‌شده، کیفیت بالایی خواهند داشت.

مراجع

[1]       M. K. Singh, S. I. Amin, S. A. Imam, V. K. Sachan, and A. Choudhary, "A survey of wireless sensor network and its types," in Proc. of IEEE Int. Conf. on Advances in Computing, Communication Control and Networking, ICACCCN’18, pp. 326-330, Greater Noida, India, 12-13 Oct. 2018.

[2]       Z. Jiao, L. Zhang, M. Xu, C. Cai, and J. Xiong, "Coverage control algorithm-based adaptive particle swarm optimization and node sleeping in wireless multimedia sensor networks," IEEE Access,
vol. 7, pp. 170096-170105, Nov. 2019.

[3]       P. Visu, T. S. Praba, N. Sivakumar, R. Srinivasan, and T. Sethukarasi, "Bio-inspired dual cluster heads optimized routing algorithm for wireless sensor networks," J. of Ambient Intelligence and Humanized Computing, vol. 12, no. 3, pp. 3753-3761, Mar. 2021.

[4]       ن. نوروزی، ﻫ. طباطبایی ملاذی و م. فضلعلی، "EBONC: يک روش جديد خوشه‌بندي آگاه از انرژي، مبتني بر تعداد خوشه بهينه براي شبکه حسگر بي‌سيم متحرک،" نشریه مهندسی برق و کامپیوتر ایران، ب- مهندسي كامپيوتر، سال 14، شماره 4 ، صص. 310-299، زمستان 1395.

[5]       M. Shafiq, H. Ashraf, A. Ullah, and S. Tahira, "Systematic literature review on energy efficient routing schemes in WSN-a survey," Mobile Networks and Applications, vol. 25, pp. 882-895, Jun. 2020.

[6]       و. ستاري نائيني و ف. موحدي، "به کارگیری منطق فازی در انتخاب مناسب گره بعدی برای پیکربندی مسیر با پروتکل LEAP در شبکه‌های حسگر بی‌سیم،" نشریه مهندسی برق و کامپیوتر ایران، ب- مهندسي كامپيوتر، سال 15، شماره 4، صص. 304-295، زمستان 1396.

[7]       K. S. Adu-Manu, N. Adam, C. Tapparello, H. Ayatollahi, and W. Heinzelman, "Energy-harvesting wireless sensor networks (EH-WSNs): a review," ACM Trans. on Sensor Networks, vol. 14, no. 2, Article No.: 10, 50 pp., May 2018.

[8]       Q. Chen, et al., "Harvest energy from the water: a self-sustained wireless water quality sensing system," ACM Trans. on Embedded Computing Systems, vol. 17, no. 1, Article No.: 3, 24 pp., Jan. 2017.

[9]       S. Kosunalp, "An energy prediction algorithm for wind-powered wireless sensor networks with energy harvesting," Energy, vol. 139, pp. 1275-1280, Nov. 2017.

[10]       A. Bakar and J. Hester, "Making sense of intermittent energy harvesting," in Proc. of Int. Workshop on Energy Harvesting & Energy-Neutral Sensing Systems, SenSys’18, pp. 32-37, Shenzhen, China, 4-4 Nov. 2018.

[11]       J. DeWitt and H. Shi, "Barrier coverage in energy harvesting sensor networks," Ad Hoc Networks, vol. 56pp. 72-83, 1 Mar. 2017.

[12]       C. C. Lin, Y. C. Chen, J. L. Chen, D. J. Deng, S. B. Wang, and S. Y. Jhong, "Lifetime enhancement of dynamic heterogeneous wireless sensor networks with energy-harvesting sensors," Mobile Networks and Applications, vol. 22, no. 5, pp. 931-942, Oct. 2017.

[13]       A. Bengheni, F. Didi, and I. Bambrik, "EEM-EHWSN: enhanced energy management scheme in energy harvesting wireless sensor networks," Wireless Networks, vol. 25, no. 6, pp. 3029-3046, Aug. 2019.

[14]       T. Lu, G. Liu, W. Li, S. Chang, and W. Guo, "Distributed sampling rate allocation for data quality maximization in rechargeable sensor networks," J. of Network and Computer Applications, vol. 80, pp. 1-9, 15 Feb. 2017.

[15]       S. Liu and Y. C. Chen, "Robust data collection for energy-harvesting wireless sensor networks," Computer Networks, vol. 167, Article ID: 107025, 11 Feb. 2020.

[16]       G. Martinez, S. Li, and C. Zhou, "Wastage-aware routing in energy-harvesting wireless sensor networks," IEEE Sensors J., vol. 14,
no. 9, pp. 2967-2974, Sep. 2014.

[17]       H. Shafieirad, R. S. Adve, and S. Shahbazpanahi, "Opportunistic routing in large-scale energy harvesting sensor networks," in Proc. of IEEE GLOBECOM Workshops, 6 pp., Washington, DC, USA, 4-8 Dec. 2016.

[18]       F. Li, M. Xiong, L. Wang, H. Peng, J. Hua, and X. Liu, "A novel energy-balanced routing algorithm in energy harvesting sensor networks," Physical Communication, vol. 27, no. C, pp. 181-187, Apr. 2018.

[19]       J. Li and D. Liu, "An energy aware distributed clustering routing protocol for energy harvesting wireless sensor networks," in Proc. of IEEE/CIC Int. Conf. on Communications in China, ICCC’16, 6 pp., Chengdu, China, 27-29 Jul. 2016.

[20]       D. Sharma and A. P. Bhondekar, "An improved cluster head selection in routing for solar energy-harvesting multi-heterogeneous wireless sensor networks," Wireless Personal Communications,
vol. 108, no. 4, pp. 2213-2228, Oct. 2019.

[21]       Y. Wu and W. Liu, "Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks," IET Wireless Sensor Systems, vol. 3, no. 2, pp. 112-118, Jun. 2013.

[22]       S. Sarang, M. Drieberg, A. Awang, and R. Ahmad, "A QoS MAC protocol for prioritized data in energy harvesting wireless sensor networks," Computer Networks, vol. 144, pp. 141-153, 24 Oct. 2018.

[23]       P. Zhong, Y. Zhang, S. Ma, J. Gao, and Y. Chen, "An adaptive MAC protocol for wireless rechargeable sensor networks," in Proc. of Int. Conf. on Wireless Algorithms, Systems, and Applications, WASA17, Lecture Notes in Computer Science, Springer, vol. 10251, 5 pp., May 2017.

[24]       A. Pal and A. Nasipuri, "Joint power control and routing for rechargeable wireless sensor networks," IEEE Access, vol. 7, pp. 123992-124007, Aug. 2019.

[25]       R. S. Liu, K. W. Fan, Z. Zheng, and P. Sinha, "Perpetual and fair data collection for environmental energy harvesting sensor networks," IEEE/ACM Trans. on Networking, vol. 19, no. 4, pp. 947-960, Nov. 2011.

[26]       T. Lu, G. Liu, and S. Chang, "Energy-efficient data sensing and routing in unreliable energy-harvesting wireless sensor network," Wireless Networks, vol. 24, no. 2, pp. 611-625, Feb. 2018.

[27]       R. R. Rout, M. S. Krishna, and S. Gupta, "Markov decision process-based switching algorithm for sustainable rechargeable wireless sensor networks," IEEE Sensors J., vol. 16, no. 8, pp. 2788-2797, Apr. 2016.

[28]       X. Zhang, C. Wang, and L. Tao, "An opportunistic packet forwarding for energy-harvesting wireless sensor networks with dynamic and heterogeneous duty cycle," IEEE Sensors Letters,
vol. 2, no. 3, 4 pp., Sept. 2018.

[29]       H. Darji and H. B. Shah, "Genetic algorithm for energy harvesting-wireless sensor networks," in Proc. of IEEE Int. Conf.
on Recent Trends in Electronics, Information & Communication Technology, RTEICT’16, pp. 1398-1402, Bangalore, India, 20-21 May 2016.

[30]       J. Li and D. Liu, "DPSO-based clustering routing algorithm for energy harvesting wireless sensor networks," in Proc. of Int. Conf. on Wireless Communications & Signal Processing, WCSP’15, 5 pp., Nanjing, China, 15-17 Oct. 2015.

[31]       M. Deb and S. Roy, "Harvested profile aware multi hop routing protocol for wireless sensor network," in Proc. of Int.
Conf. on Emerging Applications of Information Technology, EAIT’18, 4 pp., Kolkata, India, 12-13 Jan. 2018.

[32]       S. M. Bozorgi, A. S. Rostami, A. A. R. Hosseinabadi, and V. E. Balas, "A new clustering protocol for energy harvesting-wireless sensor networks," Computers & Electrical Engineering, vol. 64, 
pp. 233-247, Nov. 2017.

[33]       M. M. Afsar and M. Youni, "A load-balanced cross-layer design for energy-harvesting sensor networks," J. of Network and Computer Applications, vol. 145, Article ID:. 102390, 1Nov. 2019.

[34]       A. Ratnaweera, S. Halgamuge, and H. Watson, "Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients," IEEE Trans. on Evolutionary Computation, vol. 8, 
no. 3, pp. 240-255, Jun. 2004.

[35]       W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 660-670, Oct. 2002.

[36]       H. Zhang and J. C. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Ad Hoc & Sensor Wireless Networks, vol. 1, pp. 89-124, Jan. 2005.

[37]       R. S. Y. Elhabyan and M. C. E. Yagoub, "Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network," J. of Network and Computer Applications, vol. 52, no. C, pp. 116-128, Jun. 2015.

 

وحیده فراهانی تحصیلات خود را در مقاطع کارشناسی و کارشناسی ارشد در رشته مهندسی کامپیوتر در دانشگاه تبریز در سال‌های 1396 و 1398 به پایان رسانده است. زمینه‌های تحقیقاتی مورد علاقه ایشان شامل شبکه‌های بی‌سیم و کاربردهای بهینه‌سازی در شبکه‌های کامپیوتری است.

 

لیلی فرزین‌وش تحصیلات خود را در مقاطع کارشناسی و کارشناسی ارشد در رشته مهندسی کامپیوتر در دانشگاه تهران در سال‌های 1386 و 1388 به پایان رسانده است. همچنین مدرک دکتری خود در رشته مهندسی کامپیوتر را در سال 1393 از دانشگاه صنعتی امیرکبیر دریافت نمود. ایشان در حال حاضر استادیار گروه مهندسی فناوری اطلاعات در دانشکده مهندسی برق و کامپیوتر دانشگاه تبریز است. زمینه‌های تحقیقاتی مورد علاقه ایشان شامل شبکه‌های بی‌سیم، بهینه‌سازی و کاربردهای مهندسی آن و امنیت شبکه است.

 

مینا زلفی لیقوان تحصیلات خود را در مقاطع کارشناسی و کارشناسی ارشد در رشته مهندسی کامپیوتر در دانشگاه تهران در سال‌های 1378 و 1381 به پایان رسانده است. همچنین مدرک دکتری خود در رشته مهندسی برق را در سال 1391 از دانشگاه تبریز دریافت نمود. ایشان در حال حاضر استادیار گروه مهندسی کامپیوتر در دانشکده مهندسی برق و کامپیوتر دانشگاه تبریز است. زمینه‌های تحقیقاتی مورد علاقه ایشان شامل معماری کامپیوتر و شبکه‌های بی‌سیم است.

 

رحیم ابری لیقوان تحصیلات خود را در مقاطع کارشناسی و کارشناسی ارشد در رشته مهندسی کامپیوتر در دانشگاه تبریز در سال‌های 1396 و 1398 به پایان رسانده است. زمینه‌های تحقیقاتی مورد علاقه ایشان شامل مدل‌سازی سیستم‌های کامپیوتری با استفاده از شبکه پتری و شبکه‌های بی‌سیم است.

 

 

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]