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

اشتراک گذاری

آدرس مقاله


کد مقاله : 201912308704 بازدید : 9626 صفحه: 39 - 54

20.1001.1.27170414.1399.12.43.3.4

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

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

محورهای موضوعی : عمومى

احسان خراطی 1

1 - دانشکده فنی و مهندسی، گروه کامپیوتر، دانشگاه آزاد اسلامی واحد قم

تاریخ دریافت : 1398/10/09 تاریخ پذیرش : 1399/04/16 تاریخ انتشار : 1399/07/07

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

چکیده مقاله :

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

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

The wireless sensor network includes a number of fixed sensor nodes that move sink nodes to collect data between nodes. To reduce energy consumption and increase the value of collected data, it is necessary to determine the optimum route and residence location of mobile sinks, which increases the life of wireless sensor networks. Using network coding, this paper presents a Mixed Integer Linear Programming Model to determine the optimal multicast routing of source sensor nodes to mobile sinks in wireless sensor networks, which determines the time and location of sinks to collect maximum coded data and reduces the delay in sink movement and energy consumption. Solving this problem in polynomial time is not possible due to the involvement of various parameters and the constrained resources of wireless sensor networks. Therefore, several exploratory and greedy and fully distributed algorithms are proposed to determine the movement of sinks and their residence location based on maximizing the value of coded data and the type of data dead time. By simulating, the optimal method and the use of coding and proposed algorithms, reduce the runtime and energy consumption and increase the value of collected data and network lifetime than non-coding methods.

منابع و مأخذ:

[1] P. Gjanci, C. Petrioli, S. Basagni, C. A. Phillips, L. Bölöni, and D. Turgut, “Path finding for maximum value of information in multi-modal underwater wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 17, no. 2, pp. 404-418, 2018.
[2] N. Sabor, S. Sasaki, M. Abo-Zahhad, and S. M. Ahmed, “A comprehensive survey on hierarchical-based routing protocols for mobile wireless sensor networks: review, taxonomy, and future directions,” Wireless Communications and Mobile Computing, vol. 2017, 2017.
[3] Z. Fei, B. Li, S. Yang, C. Xing, H. Chen, and L. Hanzo, “A survey of multi-objective optimization in wireless sensor networks: Metrics, algorithms, and open problems,” IEEE Communications Surveys & Tutorials, vol. 19, no. 1, pp. 550-586, 2017.
[4] A. Mehrabi, and K. Kim, “Maximizing data collection throughput on a path in energy harvesting sensor networks using a mobile sink,” IEEE Transactions on Mobile Computing, no. 3, pp. 690-704, 2016.
[5] F. Tashtarian, M. H. Y. Moghaddam, K. Sohraby, and S. Effati, “On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks,” IEEE Transactions on Vehicular Technology, vol. 64, no. 7, pp. 3177-3189, 2015.
[6] R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on information theory, vol. 46, no. 4, pp. 1204-1216, 2000.
[7] S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang, "A New MILP Formulation and Distributed Protocols for Wireless Sensor Networks Lifetime Maximization." pp. 3517-3524.
[8] W. Cai, M. Chen, T. Hara, and L. Shu, "GA-MIP: genetic algorithm based multiple mobile agents itinerary planning in wireless sensor networks." pp. 1-8.
[9] M. Chen, S. Gonzalez, Y. Zhang, and V. C. Leung, "Multi-agent itinerary planning for wireless sensor networks." pp. 584-597.
[10] S. R. Gandham, M. Dawande, R. Prakash, and S. Venkatesan, "Energy efficient schemes for wireless sensor networks with multiple mobile base stations." pp. 377-381.
[11] D. Jea, A. Somasundara, and M. Srivastava, "Multiple controlled mobile elements (data mules) for data collection in sensor networks." pp. 244-257.
[12] J. Luo, and J.-P. Hubaux, "Joint mobility and routing for lifetime elongation in wireless sensor networks." pp. 1735-1746.
[13] W. Wang, V. Srinivasan, and K.-C. Chua, "Using mobile relays to prolong the lifetime of wireless sensor networks." pp. 270-283.
[14] W. Rehan, S. Fischer, and M. Rehan, “Anatomizing the robustness of multichannel MAC protocols for WSNs: An evaluation under MAC oriented design issues impacting QoS,” Journal of Network and Computer Applications, vol. 121, pp. 89-118, 2018/11/01/, 2018.
[15] P. Gjanci, C. Petrioli, S. Basagni, C. A. Phillips, L. Bölöni, and D. J. I. T. o. M. C. Turgut, “Path finding for maximum value of information in multi-modal underwater wireless sensor networks,” vol. 17, no. 2, pp. 404-418, 2018.
[16] C. Lv, Q. Wang, W. Yan, and J. Li, “A sparsity feedback-based data gathering algorithm for Wireless Sensor Networks,” Computer Networks, vol. 141, pp. 145-156, 2018/08/04/, 2018.
[17] R. Logambigai, S. Ganapathy, and A. Kannan, “Energy–efficient grid–based routing algorithm using intelligent fuzzy rules for wireless sensor networks,” Computers & Electrical Engineering, vol. 68, pp. 62-75, 2018/05/01/, 2018.
[18] C. Li, J. Bai, J. Gu, X. Yan, and Y. Luo, “Clustering routing based on mixed integer programming for heterogeneous wireless sensor networks,” Ad Hoc Networks, vol. 72, pp. 81-90, 2018/04/01/, 2018.
[19] O. M. Al-Kofahi, and A. E. Kamal, "Transmissions Scheduling in Network Coding-Based Resilient WSNs," Resilient Wireless Sensor Networks, pp. 53-65: Springer, 2015.
[20] M. Khalily-Dermany, and M. J. Nadjafi-Arani, “Itinerary planning for mobile sinks in network-coding-based wireless sensor networks,” Computer Communications, vol. 111, pp. 1-13, 2017/10/01/, 2017.
[21] C. Abreu, F. Miranda, and P. M. Mendes, “Smart context-aware QoS-based admission control for biomedical wireless sensor networks,” Journal of Network and Computer Applications, vol. 88, pp. 134-145, 2017/06/15/, 2017.
[22] N. Javaid, S. Hussain, A. Ahmad, M. Imran, A. Khan, and M. Guizani, “Region based cooperative routing in underwater wireless sensor networks,” Journal of Network and Computer Applications, vol. 92, pp. 31-41, 2017/08/15/, 2017.
[23] I. L. C. Vasconcelos, I. C. Martins, C. M. S. Figueiredo, and A. L. L. Aquino, “A data sample algorithm applied to wireless sensor network with disruptive connections,” Computer Networks, vol. 146, pp. 1-11, 2018/12/09/, 2018.
[24] A. Abuarqoub, M. Hammoudeh, B. Adebisi, S. Jabbar, A. Bounceur, and H. Al-Bashar, “Dynamic clustering and management of mobile wireless sensor networks,” Computer Networks, vol. 117, pp. 62-75, 2017/04/22/, 2017.
[25] Z. Fei, B. Li, S. Yang, C. Xing, H. Chen, L. J. I. C. S. Hanzo, and Tutorials, “A survey of multi-objective optimization in wireless sensor networks: Metrics, algorithms, and open problems,” vol. 19, no. 1, pp. 550-586, 2017.
[26] F. Tashtarian, M. H. Y. Moghaddam, K. Sohraby, and S. J. I. T. o. V. T. Effati, “On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks,” vol. 64, no. 7, pp. 3177-3189, 2015.
[27] M. Koç, and I. J. I. J. o. D. S. N. Korpeoglu, “Controlled sink mobility algorithms for wireless sensor networks,” vol. 10, no. 4, pp. 167508, 2014.
[28] M. K. Dermany, and S. Sharifian, “Effect of various topology control mechanisms on maximum information flow in wireless sensor networks,” SmartCR, vol. 5, no. 1, pp. 10-18, 2015.
[29] T. Ho, B. Leong, R. Koetter, M. Médard, M. Effros, and D. R. Karger, “Byzantine modification detection in multicast networks with random network coding,” IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2798-2803, 2008.
[30] M. Khalily-Dermany, and M. Nadjafi-Arani, “Itinerary planning for mobile sinks in network-coding-based wireless sensor networks,” Computer Communications, vol. 111, pp. 1-13, 2017.
[31] T. Ho, and D. Lun, Network coding: an introduction: Cambridge University Press, 2008.
[32] M. Khalily-Dermany, M. Shamsi, and M. J. Nadjafi-Arani, “A convex optimization model for topology control in network-coding-based-wireless-sensor networks,” Ad Hoc Networks, vol. 59, pp. 1-11, 2017.
[33] G. A. Shah, and O. B. Akan, “Timing-based mobile sensor localization in wireless sensor and actor networks,” Mobile Networks and Applications, vol. 15, no. 5, pp. 664-679, 2010.
[34] B. Khodabakhshi, and M. Khalily, “An energy efficient network coding model for wireless sensor networks,” Procedia Computer Science, vol. 98, pp. 157-162, 2016.
[35] X. Wang, M. Chen, T. Kwon, and H.-C. Chao, “Multiple mobile agents' itinerary planning in wireless sensor networks: survey and evaluation,” IET communications, vol. 5, no. 12, pp. 1769-1776, 2011.
[36] H. Kaushal, and G. Kaddoum, “Underwater optical wireless communication,” IEEE access, vol. 4, pp. 1518-1547, 2016.
[37] C. Petrioli, R. Petroccia, J. R. Potter, and D. Spaccini, “The SUNSET framework for simulation, emulation and at-sea testing of underwater wireless sensor networks,” Ad Hoc Networks, vol. 34, pp. 224-238, 2015.
[38] A. Darehshoorzadeh, N. T. Javan, and M. Dehghan, "LBAODV: a new load balancing multipath routing algorithm for mobile ad hoc networks." pp. 344-349.
[39] F. Bai, K. S. Munasinghe, and A. Jamalipour, “A novel information acquisition technique for mobile-assisted wireless sensor networks,” IEEE Transactions on Vehicular Technology, vol. 61, no. 4, pp. 1752-1761, 2012.
[40] W. Liang, J. Luo, and X. Xu, "Prolonging network lifetime via a controlled mobile sink in wireless sensor networks." pp. 1-6.
[41] C. Konstantopoulos, G. E. Pantziou, D. Gavalas, A. Mpitziopoulos, and B. Mamalis, “A Rendezvous-Based Approach Enabling Energy-Efficient Sensory Data Collection with Mobile Sinks,” IEEE Trans. Parallel Distrib. Syst., vol. 23, no. 5, pp. 809-817, 2012.
[42] C. Gkantsidis, J. Miller, and P. Rodriguez, "Comprehensive view of a live network coding P2P system." pp. 177-188.
[43] M. K. Dermany, M. Sabaei, and M. Shamsi, “Topology control in network–coding–based–multicast wireless sensor networks,” International Journal of Sensor Networks, vol. 17, no. 2, pp. 93-104, 2015.
[44] B. Behdani, Y. S. Yun, J. Cole Smith, and Y. Xia, “Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks,” Computers & Operations Research, vol. 39, no. 5, pp. 1054-1061, 2012/05/01/, 2012.
[45] J. A. Khan, H. K. Qureshi, and A. Iqbal, “Energy management in Wireless Sensor Networks: A survey,” Computers & Electrical Engineering, vol. 41, pp. 159-176, 2015/01/01/, 2015.
متن کامل:


دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال دوازدهم، شماره‌هاي 43 و 44، زمستان 1399

صفحات: 39-54

iicta Logo0 

 

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

 

احسان خراطی        

استادیار دانشکده فنی و مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی واحد اراک، اراک

تاریخ دریافت: 09/10/1398 تاریخ پذیرش: 16/04/1399

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

چکیده

 

 

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

 

واژگان کلیدی: شبکه‌های حسگر بی‌سیم، کدگذاری شبکه، مسیر بهینه سینک متحرک، پهنای باند مصرف شده

 

 

1- مقدمه

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

در روش‌های سنتی مسیریابی، نمی‌توان به حداکثر جریان قابل ارسال رسید، زیرا جریان‌های داده درون شبکه را مانند جریان مایعات در لوله‌های انتقال درنظر گرفته می‌گیرند اما با استفاده از کدگذاری شبکه، گره‌های میانی می‌توانند بسته‌های وارد شده را پردازش و ترکیب کرده تا به‌صورت چندپخشی ارسال کنند و از حداکثر ظرفیت شبکه استفاده می‌شود [4]. چون در شبکه‌های حسگر بی‌سیم، کانال‌های بی‌سیم دارای ویژگی پخش همگانی هستند، کدگذاری شبکه سبب افزایش بهبود عملکرد شبکه می‌شود. شکل الف 1، نمونه‌ای از شبکه پروانه‌ای را نشان داده که ظرفیت و پهنای باند هر یال برابر یک است و درنتیجه حداکثر جریان قابل ارسال بین گره مبدا S1 و گره‌های مقصد S6 و S7 برابر دو است و لذا حداکثر می‌توان دو بسته در هر واحد زمانی به هر دو گره مقصد S6 و S7 ارسال کرد.

اما با استفاده از مسیریابی سنتی نمی‌توان به حداکثر جریان دو بسته در هر واحد زمانی رسید. برای این منظور مطابق شکل ب 1، گره S4 به جای ارسال بسته‌های P1 و P2 به‌صورت جداگانه و به‌ترتیب، آنها را به‌صورت P1⨁P2 با یکدیگر کدگذاری و XOR کرده تا گره S5 همزمان به هر دو گره مقصد S6 و S7 ارسال کند. درنتیجه با استفاده از کدگذاری شبکه می‌توان به حداکثر جریان دو بسته در هر واحد زمانی رسید [1].

 

img0 

شکل 1: یک شبکه پروانه‌ای [1]. الف: پهنای باند هر یال برابر یک است، ب: استفاده از کدگذاری شبکه و حداکثر جریان دو بسته

 

در این مقاله، ما یک مدل برنامه‌ریزی خطی صحیح 1ILP یا مدل 2MILP برای تعادل در مصرف پهنای باند یال‌ها با استفاده از کدگذاری شبکه ارایه می‌کنیم. این مدل، نسبت کل حداکثر مقدار پهنای باند به پهنای باند موجود یال‌ها را حداقل کرده و برای ‌حل این مدل از روش دوگان استفاده می‌کنیم. همچنین برای محاسبه یک کران پایین و یافتن جواب و نقطه بهینه در مدل بهینه‌سازی از شرایط 3KKT استفاده می‌کنیم که برای این منظور نیاز به محاسبه مشتق تابع لاگرانژین نسبت به متغیر‌های آن است تا شرایط به‌صورت یک دستگاه چند معادله چند مجهول بدست آید. اما چون حل معادلات کروش-کان-تاکر به‌صورت متمرکز برای شبکه‌های حسگر بی‌سیم با تعداد زیادی گره بسیار مشکل و زمان‌بر و تقریبا غیرعملی است و یک مساله 4NP-hard است، یک الگوریتم توزیع‌شده و تکرارشونده برای حل مدل پیشنهادی ارائه می‌کنیم که در آن بجای انجام مشتق‌ها از ترکیب روش زیرگرادیان و روش تفکیک جریان شبکه استفاده می‌شود.

به‌طوری که هر گره به‌صورت محلی و براساس اطلاعات گره‌های همسایه خود، مسیریابی بهینه را انجام داده و مصرف پهنای باند در شبکه را متعادل می‌کند [5].

مهمترین کارهایی که در این مقاله نسبت به مقاله‌های قبلی انجام شده است، شامل موارد زیر است.

1.       هدف مدل بهینه‌سازی پیشنهادی ایجاد تعادل و کاهش مصرف پهنای باند است که تعمیم‌یافته مدل برنامه‌ریزی خطی صحیح ILP در [2] است.

2.       مدل پیشنهادی مستقل از تراکم و استقرار و دامنه ارسال و مدل انرژی گره‌های حسگر است و پارامترهای آن شامل نرخ تولید و ارسال داده‌ها و دامنه ارسال گره‌های حسگر است.

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

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

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

 

1_2 سهم این مقاله

مرجع [4]، معماری COPE را برای ارسال بسته‌های کدگذاری شده در شبکه‌های بی‌سیم معرفی کرده که می‌تواند به‌صورت قابل توجهی کارایی شبکه‌های بی‌سیم ایستا را افزایش دهد. این معماری، از کدگذاری شبکه بین جلسه‌ای بین لایه IP و MAC استفاده کرده و بسته‌ها را به‌صورت چندپخشی ارسال می‌کند و جریان‌های داده را با یکدیگر XOR کرده و لذا پیاده‌سازی آن آسان است. در [5] از ترکیب کدگذاری شبکه و کنترل توپولوژی استفاده کرده که سبب افزایش بهره‌وری در شبکه‌های حسگر بی‌سیم شده و در مرجع [6] از ترکیب کدگذاری شبکه و کنترل مسیر حرکت سینک متحرک استفاده کرده که سبب افزایش بهره‌وری در شبکه‌های حسگر بی‌سیم خواهد شد.

در مقاله [7] نشان داده که استفاده از کدگذاری شبکه سبب حداکثر شدن جریان قابل ارسال در شبکه می‌شود. در [8] نشان داده که برای دستیابی به حداکثر ظرفیت جریان چندپخشی به هر مقصد، باید از کدگذاری شبکه استفاده کرد. کدگذاری شبکه سبب کاهش حجم ترافیک عبوری و سهیم شدن تمام گره‌ها در ارسال بسته‌ها می‌شود و درنتیجه حجم بار ترافیکی متعادل شده و سبب کاهش مصرف انرژی و افزایش طول عمر شبکه‌های حسگر بی‌سیم می‌شود. همچنین چون در کدگذاری شبکه، بسته‌ها از مسیرهای مختلفی ارسال می‌شوند، سبب افزایش قابلیت اطمینان و امنیت می‌شود.

چون انرژی لازم برای انجام محاسبات و ترکیب بسته‌ها در گره‌های حسگر میانی بسیار کمتر از انرژی لازم برای ارسال و دریافت بسته‌ها است، کدگذاری شبکه سبب افزایش بهره‌وری یا کارآیی و کاهش مصرف پهنای باند، تاخیر، پیچیدگی و هزینه‌ها در شبکه می‌شود. شکل 2، انواع روش‌های کدگذاری شبکه در شبکه‌های حسگر بی‌سیم را نشان می‌دهد [9].

نقطه ضعف کدگذاری شبکه، محدودیت حافظه و سرریز بافر در گره‌های شبکه حسگر بی‌سیم و افزایش ترافیک در پهنای باند شبکه به سبب ارسال بسته‌ها از مسیرهای مختلف است. در کدگذاری شبکه، گره‌های میانی یکسری بسته‌های کدشده تولید می‌کنند و گره‌های مقصد باید بتوانند به روش حذفی گاوس این بسته‌ها را تشخیص و کدگشایی کنند [10]. پیچیدگی روش حذفی گاوس از درجه سه است و لذا هرچه تعداد گره‌های حسگر منبع در شبکه بیشتر باشند، انجام کدگذاری شبکه غیرممکن و غیرعملی است. مشکل دیگر روش حذفی گاوس، محدود بودن تعداد بسته‌های کدشده است و اگر تعداد بسته‌های کدشده کمتر از این محدوده باشد، تعداد بسته‌های کدگشایی شده تقریباً صفر خواهد بود [11]. برای رفع مشکلات فوق و انجام بهینه کدگذاری شبکه باید از گره‌هایی با قدرت محاسباتی بیشتر استفاده کرد یا تعداد گره‌های میانی کدکننده را محدود کرد که انتخاب تعداد حداقل گره با توانایی کدگذاری شبکه، یک مساله NP-hard است [12]. جدول 1، شامل مقالات نویسنده است که به‌طور خلاصه مزایا و معایب و محدودیت‌ها و تابع هدف و الگوریتم و روش استفاده شده را بیان می‌کند.

 

img0 

شکل 2: انواع روش‌های کدگذاری شبکه در شبکه‌های حسگر بی‌سیم [6-1]

 

جدول 1: خلاصه مقایسه روش‌های بررسی شده [4-1]

 

مقاله

[1]

[2]

[3]

[4]

این مقاله

تابع

هدف

کاهش

انرژی

افزایش

داده

کاهش

تاخیر

افزایش

بازدهی

کاهش

مصرف

پهنای‌باند

محدود

يت‌ها

نرخ داده

ارسالي

جریان

چندپخشی

حجم

ترافیک

رای

گیری

تعداد

گره‌های

حسگرمنبع

الگوریتم

حل مسئله

الگوریتم

ژنتیک

الگوریتم

خوشه‌بندی

الگوریتم

ازدحام‌ذرات

الگوریتم

حریصانه

الگوریتم

توزیع‌شده

تصادفی

زیرگرادیان

مزايا

بازدهی‌و

بلادرنگ

سینک‌های

متحرک

بازدهی

وعدالت

اتصالات

قوی

ایجادتعادل

درمصرف

پهنای‌باند

معايب

عدم‌پوشش

‌شبکه

چندگره

میانی

اتصالات

ضعیف

کاهش

طول عمر

محاسبات‌فراوان

و کندی

مسیریابی

نوآوري

کدگذاری

محلی

کدگذاری

سراسری

کدگذاری

باینری

کدگذاری

تصادفی

مستقل از

تراکم و

استقرارو

دامنه‌ارسال‌

گره‌های‌حسگر

3- مدل بهینه‌سازی پیشنهادی

در این مقاله برای ساده شدن مدل بهینه‌سازی پیشنهادی و مساله، فرض می‌کنیم که محیط باز و مسطح بوده و پوشش رادیویی کاملاً منظم است، که در کار در آینده می‌توان این مدل را در شرایط واقعی مانند داخل ساختمان یا تحت شرایط سخت و پوشش‌های رادیویی بسیار نامنظم و همراه با تداخل مورد استفاده قرار داد. برای مدل کردن شبکه مانند مقالات [1-6] از مدل گراف 𝐺=(𝑁,𝐸) و ابرگراف 𝐺=(𝑁,𝐴) استفاده کرده که 𝑁 مجموعه متناهی گره‌ها، 𝐸 مجموعه متناهی یال‌ها و 𝐴 مجموعه ابریال‌ها هستند. یک یال از یک گره مانند 𝑖 شروع شده و به گرهی دیگر مانند 𝑗 ختم می‌شود و با (𝑖, 𝑗) نمایش داده می‌شود [13]. ابریال شامل مجموعه‌ای از یال‌ها است که از یک گره مانند 𝑖 شروع شده و به 𝒥𝑖 یا مجموعه‌ای از همسایه‌ها یا گره‌هایی که در محدوده دامنه ارسال گره 𝑖 هستند ختم می‌شود که با (𝑖, 𝒥𝑖) نشان داده می‌شود. جدول 2، شامل نماد‌ها و تعاریف مورد نیاز برای مدل بهینه‌سازی و الگوریتم پیشنهادی است.

 

جدول 2: علایم استفاده شده در مدل و الگوریتم پیشنهادی

تعریف

نماد

مجموعه‌ای از همسایه‌ها یا گره‌هایی که در محدوده دامنه ارسال گره 𝑖 هستند

𝒥𝑖

مقدار پهنای باند موجود در یال (𝑖,𝑗)

𝐵(𝑖,𝑗)

حداکثر مقدار پهنای باند در هر یال در شبکه

𝐵𝑀𝑎𝑥

مقدار جریان مجازی روی یال (𝑖,𝑗) 

𝑉(𝑖,𝑗)

مقدار جریان واقعی از گره 𝑖 روی ابریال (𝑖,𝒥𝑖)

𝑅(𝑖,𝒥𝑖)

مقدار ثابت و غیرمنفی عرضه و تقاضا در گره 𝑖

𝛥𝑖

یک نقطه از فضای شدنی در مرحله 𝑛ام

𝑥[𝑛]

اندازه گام در نقطه 𝑥[𝑛]

𝜃[𝑛]

زیرگرادیان تابع لاگرانژین در نقطه 𝑥[𝑛]

𝜔[𝑛]

نقطه مرحله بعد

𝑥[𝑛+1]

نقطه جواب و بهینه

 

 

ارسال داده‌ها با استفاده از کدگذاری شبکه شامل دو مرحله کدگذاری و مسیریابی است [14]. در مرحله کدگذاری، داده‌ها در قالب بسته در گره‌های میانی شبکه ذخیره شده و سپس ترکیب خطی آنها به یال‌های خروجی ارسال می‌شود [15]. در مرحله مسیریابی، بهترین زیرگراف برای ارسال بسته‌های چندپخشی کدگذاری شده انتخاب می‌شود.

مسیریابی بهینه بدون استفاده از کدگذاری شبکه برای جریان‌های چندپخشی یک مساله Np-hard است [16]، درحالی‌که با استفاده از کدگذاری شبکه به‌صورت یک مساله بهینه‌سازی بیان می‌شود [17]. در کدگذاری شبکه، دو نوع جریان مجازی و واقعی وجود دارد که جریان مجازی، یک متغیر میانی بوده و برای بدست آوردن جریان واقعی استفاده می‌شود. فرض می‌کنیم که 𝑉(𝑖,𝑗) مقدار جریان مجازی عبوری روی یال (𝑖,𝑗) و 𝑅(𝑖,𝒥𝑖) مقدار جریان واقعی عبوری از گره 𝑖 به همسایه‌های آن یا 𝒥𝑖 باشد. مدل بهینه‌سازی زیر نحوه ارسال جریان چندپخشی براساس کدگذاری شبکه با حداقل هزینه در شبکه است [1-6]. 

 

 

در این مدل، تابع هدف (1)، هزینه جریان‌های واقعی یا 𝑓(𝑅) را در همه گره‌های شبکه حداقل کرده که 𝑎(𝑖,𝑗) مقدار تابع هزینه یا انرژی لازم برای ارسال یک بسته روی یال (𝑖,𝑗) است که وابسته به دامنه ارسال آن گره است. محدودیت (2)، بیان کرده که همواره مقدار جریان واقعی که از یک گره عبور می‌کند بیشتر از مقدار مجموع همه جریان‌های مجازی است که از آن گره عبور می‌کند و چون آنتن همه گره‌ها به‌صورت تمام جهته است، با ارسال یک جریان از گره 𝑖، تمام همسایگان 𝑖 یا 𝒥𝑖، جریان ارسالی را دریافت می‌کنند. محدودیت (3)، بیان کرده که جریان‌های واقعی و مجازی مثبت هستند. محدودیت (4)، بیان کرده که حداکثر جریان واقعی که از یک یال عبور می‌کند باید کمتر یا مساوی مقدار پهنای باند در آن یال باشد. محدودیت (5)، قانون بقای جریان‌های چندپخشی را مانند جریان تک پخشی بیان کرده که تفاضل مجموع جریان‌های ورودی و خروجی در گره‌های حسگر میانی برابر صفر و در گره‌های منبع برابر مقدار ثابت و غیرمنفی عرضه و تقاضا یا 𝛥𝑖 و در گره‌های مقصد برابر -𝛥𝑖 است.

در [14] یک مدل بهینه‌سازی مشابه محدودیت‌های فوق برای ارسال جریان چندپخشی با حداقل مصرف انرژی در زیرگرافی از شبکه حسگر بی‌سیم ارائه داده است که برای این منظور مقدار تابع هزینه 𝑎(𝑖,𝑗) را برابر مربع فاصله بین دو گره درنظر گرفته است. اگر دامنه ارسال گره از فاصله بین دو گره کمتر باشد، آنگاه جریانی بین آن دو گره برقرار نخواهد شد. در [15] ثابت کرده است که مدل بهینه‌سازی فوق یک مدل بهینه‌سازی خطی با زمان اجرای نمایی است و راه‌حل این مدل، مقدار بهینه 𝑅(𝑖,𝒥𝑖) است. در این مقاله چون پهنای باند یال‌ها محدود است، برای کاهش مصرف انرژی و هزینه، تابع هدف و هزینه اصلی مساله را ایجاد تعادل در مصرف پهنای باند درنظر می‌گیریم.

اگر 𝐵𝑀𝑎𝑥 حداکثر مقدار پهنای باند در هر یال در شبکه و 𝐵(𝑖,𝑗) مقدار پهنای باند موجود در یال (𝑖,𝑗) باشد، تابع هزینه را به‌صورت 𝑎(𝑖,𝑗)=𝐵𝑀𝑎𝑥/𝐵(𝑖,𝑗) درنظر می‌گیریم تا یال‌هایی که پهنای باند آزاد بیشتری دارند، اولویت بیشتری برای انتخاب شدن در مسیریابی براساس کدگذاری شبکه داشته باشند. همچنین به‌دلیل استفاده از چندپخشی در گره‌های حسگر، محدودیت (4) را به‌صورت  تغییر می‌دهیم. همچنین برای اینکه بتوانیم فقط مقدار جریان مجازی را جایگزین مقدار جریان واقعی در سایر محدودیت‌ها کنیم، محدودیت (2) را به‌صورت  تغییر می‌دهیم. اما چون این محدودیت گسسته است لذا باید آن را به فرم پیوسته تبدیل کرد. برای این منظور از تقریب نرم 𝑙𝑚 به‌صورت زیر استفاده می‌کنیم [2].

 

 

 

 

 

 

(1)

 

 

 

 

 

 

(2)

 

 

 

(3)

 

 

 

(4)

 

 

 

 

(5)

 

همچنین برای اینکه مدل پیشنهادی به‌صورت محدب و در قالب یک مساله مینیمم‌سازی خطی باشد، محدودیت‌ها را در یک سمت نامساوی قرار می‌دهیم. بنابر توضیحات فوق، مدل بهینه‌سازی ریاضی محدب پیشنهادی برای ارسال جریان چندپخشی براساس کدگذاری شبکه و کاهش هزینه در یک شبکه حسگر بی‌سیم به‌صورت زیر است. ما در این مقاله این مدل را به مدل بهینه‌سازی ایجاد تعادل در مصرف پهنای باند با استفاده از کدگذاری شبکه یا 5BNCOM نامگذاری می‌کنیم.

 

 

 

(6)

 

3-1- دوگان مدل

مسایل مینیمم‌سازی خطی، زیرکلاسی از مسائل بهینه‌سازی محدب هستند و روش‌های متعددی برای حل آنها وجود دارد [16]. یکی از روش‌های حل مسائل بهینه‌سازی ریاضی، استفاده از دوگان مدل است [17]. برای این منظور و محاسبه یک کران پایین و بهینه برای مدل، نیاز به تابع محدب لاگرانژین مدل و یک ضریب برای هر محدودیت است [18]. چون متغیر 𝑅(𝑖,𝒥𝑖) برحسب متغیر کمکی 𝑉(𝑖,𝑗) است، می‌توان آن را در تابع هدف جایگزین و یک مدل بهینه‌سازی با تابع هدفی برحسب متغیر 𝑉(𝑖,𝑗) بدست آورد [19]. تابع لاگرانژین برای تابع هدف و محدودیت‌های مدل فوق به‌صورت زیر است که 𝑉 متغیر بهینه‌سازی جریان مجازی در شبکه و 𝛼 و 𝛽 و 𝛾 و 𝛿 ضرایب لاگرانژین برحسب متغیرهای 𝑖 و 𝑗 برای محدودیت‌ها هستند. 

 

 

 

 

 

 

(7)

 

 

 

 

 

 

 

(8)

 

 

 

(9)

 

 

 

(10)

 

 

 

 

(11)

 

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

 

 

 

 

 

 

(12)

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒: 𝐿(𝑉, 𝛼, 𝛽, 𝛾, 𝛿) 

Subject to

∀ 𝑖∈𝑁, 𝑗∈𝒥𝑖, 𝛼𝑖≥0, 𝛽𝑖≥0, 𝛾(𝑖,𝑗)≥0, 𝛿(𝑖,𝑗)≥0

(13)

 

اگر  مقدار بهینه مدل پیشنهادی و  مقدار بهینه متغیر 𝑉 باشد، آنگاه  است. همچنین اگر  مقدار بهینه دوگان مدل پیشنهادی باشد،
آنگاه  است که  و  و  و  مقادیر بهینه ضرایب لاگرانژین 𝛼 و 𝛽 و 𝛾 و 𝛿 هستند. به اختلاف بین  و  فاصله دوگانی می‌گویند [20].

درحالت کلی برای مساله‌های محدب و غیرمحدب،  است اما اگر مساله بهینه‌سازی محدب با حداقل یک نقطه، شدنی باشد، آنگاه  است، که در این حالت اصطلاحا به دوگانی قوی یا شرایط اسلاتر معروف است [21]. در این مقاله نیز چون می‌خواهیم بهترین نقطه بهینه را برای مساله بیابیم، باید شرایط اسلاتر یا دوگانی قوی برآورده شود. یعنی باید جواب و نقطه بهینه مدل بهینه‌سازی پیشنهادی و دوگان مدل آن یکسان باشد. برای این منظور از شرایط کاروش-کان-تاکر استفاده می‌کنیم [22].

 

3-2- شرایط کاروش-کان-تاکر 

از شرایط کاروش-کان-تاکر برای یافتن جواب و نقطه بهینه در مدل بهینه‌سازی استفاده می‌شود. برای این منظور لازم است ابتدا مشتق تابع لاگرانژین نسبت به متغیر‌ها و ضرایب آن محاسبه شود تا شرایط به‌صورت یک دستگاه چند معادله چند مجهول بدست آید. حل این دستگاه منجر به یافتن جواب و نقطه بهینه برای متغیر 𝑉 یا مقدار جریان مجازی در شبکه خواهد شد. مشتق تابع لاگرانژین نسبت به متغیر‌ها و ضرایب آن به‌صورت زیر است:

 

دستگاه چند معادله چند مجهول این مدل به‌صورت زیر است که چون مدل پیشنهادی محدب است، لذا یک پاسخ بهینه و کمینه برای متغیر 𝑉 برحسب ضرایب لاگرانژین 𝛼 و 𝛽 و 𝛾 و 𝛿 وجود دارد که باید شرایط زیر را برآورده کنند. 

 

 

 

 

 

 

 

 

 

(14)

 

(15)

 

(16)

 

(17)

 

(18)

 

(19)

 

4- الگوریتم توزیع‌شده برای حل مدل بهینه‌سازی

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

همچنین برای محاسبه یک کران پایین و یافتن جواب و نقطه بهینه در مدل بهینه‌سازی از شرایط کاروش-کان-تاکر یا KKT استفاده کردیم که برای این منظور نیاز به محاسبه مشتق تابع لاگرانژین نسبت به متغیر‌های آن بود تا شرایط به‌صورت یک دستگاه چند معادله چند مجهول بدست آید. حل این دستگاه منجر به یافتن جواب و نقطه بهینه برای متغیر 𝑉 یا مقدار جریان مجازی در شبکه می‌شود. حل شرایط کروش-کان-تاکر به‌صورت متمرکز برای شبکه‌های حسگر بی‌سیم با تعداد زیادی گره بسیار مشکل و زمان‌بر و تقریبا غیرعملی است زیرا نیاز است اطلاعات همه گره‌ها در یک گره مرکزی جمع شده و محاسبات انجام شود و سپس جواب حل این معادلات به سایر گره‌ها ارسال شود.

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

روش زیرگرادیان در الگوریتم‌های بهینه‌سازی غیرخطی کاربرد دارد. در روش زیرگرادیان، مقدار تابع هدف همیشه کاهش پیدا نمی‌کند، بلکه ممکن است افزایش یابد. هر نقطه که در مراحل اجرای الگوریتم جستجو تولید می‌شود، شدنی بوده و می‌توان از این نقاط به‌عنوان یک راه‌حل میانی استفاده کرد. اگر فرآیند حل مساله، قبل از رسیدن به راه‌حل متوقف شود، آنگاه نقطه نهایی یک راه‌حل شدنی و احتمالاً راه‌حل بهینه برای مساله اصلی است. سرعت همگرایی روش نیوتن بیشتر از روش زیرگرادیان است اما چون روش زیرگرادیان نسبت به روش نیوتن ساده‌تر و دارای محاسبات کمتری است، اغلب از روش زیرگرادیان برای گره‌های حسگر بی‌سیم با توان محاسباتی کم استفاده می‌شود [22].

در ریاضیات، زیرگرادیان مفهومی است که مشتق را برای توابعی مشتق‌ناپذیر تعمیم می‌دهد. مقدار زیرگرادیان یک نقطه مانند 𝑥0 از یک مجموعه باز محدب، برابر بردار 𝑣 است که به‌ازای هر نقطه 𝑥‌، رابطه 𝑓(𝑥)-𝑓(𝑥0)≥𝑣⨂(𝑥-𝑥0) برقرار باشد که در آن 𝑓 یک تابع محدب روی یک مجموعه باز محدب بوده و الزاما در همه نقاط مشتق‌پذیر نیست و عملگر ⨂ بیانگر ضرب داخلی است. مجموعه همه زیرگرادیان‌های 𝑥0 برای یک تابع محدب را زیرگرادیان در 𝑥0 گویند و با ∂𝑓(𝑥0) نمایش می‌دهند که یک مجموعه غیرتهی، بسته و محدب است. مقدار زیرگرادیان ∂𝑓(𝑥0) در بازه بسته و ناتهی [𝑎, 𝑏] قرار دارد که  و  است [23].

مدل بهینه‌سازی پیشنهادی در بخش سوم مقاله، یک مدل محدب است و اگر فرض کنیم که 𝑋 مجموعه‌ای از نقاط بهینه و جواب باشد، مجموعه 𝑋 باید بسته و محدب و غیرتهی باشد. با فرض وجود نقطه بهینه برای مدل پیشنهادی فوق، می‌توان این مدل پیشنهادی را با استفاده از روش زیرگرادیان حل کرد. در روش زیرگرادیان، در مرحله 𝑛ام، اگر 𝑥[𝑛]∈𝑋 یک نقطه از فضای شدنی و 𝜃[𝑛] اندازه گام و 𝜔[𝑛] زیرگرادیان تابع لاگرانژین در نقطه 𝑥[𝑛] باشد، آنگاه 𝑥[𝑛+1]∈𝑋 نقطه مرحله بعد و  نقطه جواب و بهنیه خواهد بود. درنتیجه ما با استفاده از تابع نگاشت 𝑃𝑋، نزدیکترین نقطه به  را به‌عنوان نقطه 𝑥[𝑛+1] درنظر می‌گیریم که روابط آنها به‌صورت زیر است. بنابراین در هر مرحله از روش زیرگرادیان، در جهت منفی زیرگرادیان، مقدار تابع کاهش داده می‌شود.

 

 

(20)

 

(21)

 

(22)

 

(23)

 

(24)

 

(25)

 

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

= 𝑥[𝑛]- 𝜃[𝑛].𝜔[𝑛]

(26)

𝑃𝑋() = 𝑎𝑟𝑔𝑚𝑖𝑛{‖𝑥-‖: 𝑥∈𝑋} 

(27)

𝑥[𝑛+1] = 𝑃𝑋([𝑛+1])

(28)

 

مجموع تابع لاگرانژین فوق برای همه گره‌ها، برابر تابع لاگرانژین مدل بهینه‌سازی است.

 

 

 

 

(29)

اما ممکن است در بعضی مواقع، مقدار تابع هدف کاهش پیدا نکند و مقدار  متعلق به 𝑋 نباشد. لذا لازم است بهترین مقدار 𝑥[𝑛] تا مرحله 𝑛ام در متغیر  ذخیره شده و مقدار متناظر تابع لاگرانژین در این نقطه و به‌ازای آن مقدار، در حد بالا یا 𝑈𝐵 به‌صورت زیر ذخیره شود.

 

 

 

(30)

 

در این مرحله، تابع لاگرانژین را به چند تابع کوچکتر تجزیه و گسسته کرده و هر تابع را به یک گره اختصاص می‌دهیم. محاسبه هر تابع در هر گره به‌صورت همزمان انجام شده و در هر مرحله، گره‌ها باید مقدار جریان مجازی عبوری بین دو گره 𝑖 و 𝑗 در مرحله 𝑛ام یا 𝑉(𝑖,𝑗)[𝑛] و ضریب لاگرانژین مساله در مرحله 𝑛ام یا 𝛿𝑖[𝑛] را محاسبه کرده و نگهداری کنند و مقدار این متغیر‌ها را با همسایه‌های خود رد و بدل کرده و درنهایت به‌روز کنند تا مجموع توابع لاگرانژین نیز بهبود یابد. برای این منظور یکبار فرض کرده مقدار متغیر 𝑉(𝑖,𝑗)[𝑛] ثابت است و سپس مقدار متغیر 𝛿𝑖[𝑛+1] محاسبه و به‌روز می‌کنیم و یکبار فرض کرده مقدار متغیر 𝛿𝑖[𝑛] ثابت است و سپس مقدار متغیر 𝑉(𝑖,𝑗)[𝑛+1] را محاسبه و به‌روز می‌کنیم.

در حالت اول، اگر فرض کنیم مقدار متغیر 𝑉(𝑖,𝑗)[𝑛] ثابت باشد، مقدار متغیر 𝛿𝑖[𝑛+1] به‌صورت زیر با روش زیرگرادیان محاسبه و به‌روز می‌شود که در آن، 𝜃𝛿[𝑛] اندازه گام و (𝜔𝛿)𝑖[𝑛] زیرگرادیان یا مشتق تابع لاگرانژین نسبت به متغیر 𝛿𝑖 در 𝑥[𝑛] است و ()+، تابع نگاشت است که نزدیک‌ترین نقطه نامنفی را به‌صورت  محاسبه می‌کند [4]. 

 

 

 

(31)

 

درحالت دوم، اگر مقدار متغیر 𝛿𝑖[𝑛] ثابت باشد، مقدار متغیر 𝑉(𝑖,𝑗)[𝑛+1] توسط هر گره مانند 𝑖 برای هر یال (𝑖,𝑗) به‌صورت مستقل و جداگانه به‌صورت زیر محاسبه و به‌روز می‌شود که 𝑥 متغیر تصمیم بوده و 𝑎𝑟𝑔𝑚𝑖𝑛 به معنای یافتن حداقل مقدار برای متغیر تصمیم 𝑥 است و مقادیر متغیرهای 𝛿𝑖[𝑛] و 𝑉(𝑖,𝑡)[𝑛] ثابت هستند که متغیر 𝑉(𝑖,𝑡) همان 𝑉(𝑖,𝑗) بوده با این تفاوت که مقدار جریان مجازی از گره 𝑖 به گیرنده یا مقصد متفاوتی مانند گره 𝑡 است. این معادله، یک مساله تک متغیره محدب بوده که پیچیدگی محاسباتی کمی برای هر گره حسگر دارد. 

 

 

 

(32)

 

(33)

 

چون الگوریتم پیشنهادی به‌صورت تصادفی، زیرگرادیان تابع یا (𝜔𝛿)𝑖[𝑛] را انتخاب می‌کند، ممکن است شرط خاتمه الگوریتم، حتی با وجود نقطه بهینه  هرگز رخ ندهد و الگوریتم همگرا نشود. برای همگرا شدن الگوریتم پیشنهادی باید رابطه  برقرار باشد. همگرایی الگوریتم زیرگرادیان، وابسته به انتخاب اندازه گام یا 𝜃 است.

اگر اندازه گام در هر مرحله کاهشی یابد، همگرایی الگوریتم افزایش می‌یابد؛ به‌طوری‌که ابتدا اندازه گام را یک مقدار متوسط انتخاب می‌کنیم و به تدریج با نزدیک شدن به جواب بهینه مساله، مقدار آن را کاهش می‌دهیم. اثبات شده است که اگر اندازه گام سه شرط زیر را داشته باشد، الگوریتم یا به نقطه بهینه ختم می‌شود و یا بعد از تعداد محدودی مرحله، مقدار 𝑈𝐵𝑖 نزدیک به 𝐿𝑖(, ) خواهد شد [23]. 

 

 

 

(34)

 

شرط (𝑖) تضمین کرده که مقدار اندازه گام باید مثبت باشد و شرط (𝑖𝑖) تضمین کرده که مقدار اندازه گام یا 𝜃[𝑛] خیلی سریع کاهش پیدا نکند و تعداد تکرار خیلی کم نشود و شرط (𝑖𝑖𝑖) تضمین کرده که با افزایش تعداد تکرارها، احتمال رسیدن به جواب بهینه افزایش یابد و اندازه گام می‌تواند تا صفر کاهش یابد. به‌عنوان مثال اگر اندازه گام به‌صورت  با 𝑙 و 𝑘 مثبت باشد، آنگاه سری به‌صورت همساز واگرا خواهد بود و هرچه مقدار 𝑙 بزرگتر انتخاب شود، اندازه گام بزرگتر شده و هرچه مقدار 𝑘 بزرگتر انتخاب شود، اندازه گام کوچکتر می‌شود [14].

شکل 3، فلوچارت الگوریتم توزیع‌شده و تکرارشونده پیشنهادی براساس کدگذاری شبکه برای مسیریابی و متعادل کردن مصرف پهنای باند یال‌ها در شبکه‌های حسگر بی‌سیم را نشان می‌دهد. 

 

 

 

شکل 3: فلوچارت الگوریتم پیشنهادی توزیع‌شده BNCDA

 

 

 

 

شکل 4، الگوریتم پیشنهادی یا 6BNCDA را نشان داده که یک الگوریتم توزیع‌شده براساس کدگذاری شبکه و برای ایجاد تعادل در مصرف پهنای باند در شبکه است. این الگوریتم توسط هر گره حسگر اجرا شده و در هر مرحله یک رشته از نقاط را برای مسیریابی داده‌های کدگذاری شده تولید می‌کند و هر نقطه براساس نقاط قبلی محاسبه می‌شود. هرچه تعداد مراحل برای رسیدن به جواب بهینه و اصلی کمتر باشد، همگرایی الگوریتم بیشتر خواهد بود.

 

 

 

Algorithm BNCDA

Begin                 

n⃪1;

Select an initial point and select the current point as the optimal point;

∀ (𝑖, 𝑗)∈𝐸 :         

∀ 𝑖∈𝑁 :                 

Calculating the upper bound of the objective function or 𝑈𝐵𝑖 using equation (31); 

While (∀ 𝑖∈𝑁 ||(𝜔𝛿)𝑖[𝑛]|| != 0)        

Begin

Each node calculates the values of variables [𝑛] and 𝛿[𝑛] and (𝜔𝛿)𝑖[𝑛] using equations (32) and (33) and (34) and

Sends its output to all the edges;                𝑛++;

Each node calculates the value of the variables [𝑛] and [𝑛+1] using equations (33), (34) and (6);

If ([𝑛+1], [𝑛+1]) < 𝑈𝐵𝑖, then         

Begin

Update the optimal values of  and  and as

;                ;

;         

End if

End while

Return the value of as the optimal and minimum solution value;

End.

 

شکل 4: شبه‌کد الگوریتم پیشنهادی توزیع‌شده BNCDA

 

 

 


5- شبیه‌سازی و ارزیابی کارآیی

در این بخش، کارایی و عملکرد مدل بهینه‌سازی پیشنهادی یا BNCOM در بخش سوم مقاله و الگوریتم توزیع‌شده پیشنهادی یا BNCDA در بخش چهارم مقاله را ازنظر مصرف پهنای باند و کل مقدار جریان مجازی در یال‌ها یا 𝑉 براساس پارامترهای اندازه گام یا 𝜃 و ضریب لاگرانژین یا 𝛿 در مراحل مختلف را ارزیابی کرده و سپس آنها را با مدل بهینه‌سازی SIPNec در مقاله [8] و مدل بهینه‌سازی OPT در مقاله [12] مقایسه و ارزیابی می‌کنیم. مدل بهینه‌سازی SIPNec از کدگذاری شبکه استفاده کرده و برای ارسال داده‌های کدگذاری شده از گره‌های میانی و حمال‌های داده‌ استفاده می‌کند اما ایجاد تعادل در پهنای باند را درنظر نمی‌گیرد.

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

شبیه‌سازی‌ها در محیط MATLAB روی رایانه‌ای با پردازنده 5 هسته‌ای اینتل 2.5 گیگاهرتز و حافظه رم 6 گیگا بایت اجرا شده است و برای مدل‌سازی مدل‌های بهینه‌سازی از نرم‌افزار AMPL و برای حل مدل‌های بهینه‌سازی از نرم‌افزار CPLEX و کتابخانه Pulp استفاده می‌کنیم. همچنین برای حل مدل بهینه‌سازی BNCOM می‌توانیم از حل معادلات مربوط به شرایط کاروش-کان-تاکر استفاده کنیم.

برای اجرا و پیاده‌سازی الگوریتم توزیع‌شده پیشنهادی BNCDA از زبان پایتون استفاده کرده و برای حل معادلات و نمایش نمودارها از همان نرم‌افزار متلب استفاده می‌کنیم. مقادیر اندازه‌گیری شده، حاصل میانگین 20 بار اجرا و تکرار شبیه‌سازی است و یا شبیه‌سازی را آنقدر تکرار کرده تا انرژی اولین گره حسگر خاتمه یابد و لذا نتایج با اطمینان 95٪ و دقت 5٪ هستند. 

 

ما در مدل شبیه‌سازی شبکه فرض کرده که هر گره حسگر حداکثر چهار همسایه دارد و گره‌های حسگر همزمان هستند و نحوه ارسال و دسترسی گره‌ها به پهنای باند بدون تداخل است و مکان رخ دادن رویدادها به‌صورت تصادفی و یکنواخت است و نقطه شروع حرکت سینک‌ها به مرکز شبکه نزدیک است و کانال ایده‌آل بوده و ارسال بین گره‌های حسگر به‌صورت هماهنگ از لایه کنترل دسترسی رسانه یا MAC کنترل شده است و هیچ برخورد و خطای داده‌ای رخ نمی‌دهد. همچنین در شبیه‌سازی این مقاله مانند منابع [3-5]، [43]فرض کرده 50 گره حسگر به‌صورت تصادفی در یک شبکه 100×100 متر مربع مستقر هستند و انرژی اولیه هر گره حسگر برابر 𝑒0=10 ژول و دامنه ارسال هر گره برابر 𝑟=10 متر و حداکثر پهنای باند اولیه هر یال برابر 𝐵𝑀𝑎𝑥=10 کیلو بایت و اندازه هر بسته برابر 10 بایت و نرخ تولید بسته در هر گره حسگر برابر 10 بسته در هر ثانیه و اندازه بافر هر گره حسگر برابر 100 کیلوبایت است. 

شکل 5، میزان پهنای باند موجود و پهنای باند مصرف شده برحسب بایت در شبکه را در حین اجرای الگوریتم توزیع‌شده پیشنهادی BNCDA به‌صورت پویا نشان می‌دهد.

 

img0 

شکل 5: میزان پهنای باند موجود و پهنای باند مصرف شده در شبکه در حین اجرای الگوریتم توزیع‌شده پیشنهادی BNCDA


 

5-1- تاثیر اندازه گام یا 𝜃 روی کل مقدار جریان مجازی در یال‌ها یا 𝑉 در الگوریتم توزیع‌شده پیشنهادی BNCDA

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

شکل 6، تاثیر افزایش اندازه گام روی متغیر اصلی مساله یا 𝑉 یا کل مقدار جریان مجازی در یال‌ها را در الگوریتم توزیع‌شده پیشنهادی BNCDA برای چهار مجموعه مختلف گره‌های حسگر نشان می‌دهد. این چهار مجموعه گره‌های حسگر برحسب انرژی اولیه یا 𝑒0، دامنه ارسال داده یا 𝑟، ضریب لاگرانژین یا 𝛿 و اندازه گام یا 𝜃 هستند. نقاط نشان داده شده بیانگر مقدار بهینه اندازه گام برای هر مجموعه است که از معادلات (26 و 33) با استفاده از نرم‌افزار متلب محاسبه شده است.

img0 

شکل 6: تاثیر اندازه گام یا 𝜃 روی کل مقدار جریان مجازی در یال‌ها یا 𝑉 در الگوریتم توزیع‌شده پیشنهادی BNCDA و نقاط آستانه اندازه گام برای 4 مجموعه مختلف از گره‌های حسگر

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

 

5-2- تاثیر ضریب لاگرانژین 𝛿 روی کل مقدار جریان مجازی در یال‌ها یا 𝑉 در الگوریتم توزیع‌شده پیشنهادی BNCDA 

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

img0 

شکل 7: تاثیر ضریب لاگرانژین 𝛿 روی کل مقدار جریان مجازی در یال‌ها یا 𝑉 در الگوریتم پیشنهادی BNCDA 

5-3- مجموع پهنای باند مصرف شده در شبکه

شکل‌های 8 و 9، نتایج ارزیابی و بررسی تاثیر تعداد گره‌های منبع حسگر روی مصرف پهنای باند شبکه برحسب بایت را به‌ترتیب برای دامنه ارسال گره‌های حسگر 10 و 20 متر نشان می‌دهد. در حالت 4 گره حسگر منبع، 4 گره حسگر منبع در چهار گوشه شبکه قرار دارند و داده‌های حس شده را تولید کرده و سایر گره‌های میانی، داده‌ها را کدگذاری می‌کنند. حالت 5 گره حسگر منبع، مانند حالت 4 گره حسگر منبع بوده با این تفاوت که گره منبع پنجم در مرکز شبکه قرار دارد. 

 

img0 

شکل 8: تاثیر تعداد گره‌های حسگر منبع روی مجموع پهنای باند مصرف شده در شبکه برحسب بایت با دامنه ارسال 10 متر

 

img0 

شکل 9: تاثیر تعداد گره‌های حسگر منبع روی مجموع پهنای باند مصرف شده در شبکه برحسب بایت با دامنه ارسال 20 متر

 

تعداد گره‌های همسایه یک گره حسگر منبع با دامنه ارسال 10 متر، بین 2 تا 4 و با دامنه ارسال 20 متر، بین 5 تا 12 است. مشاهده می‌شود که با افزایش تعداد گره‌های حسگر منبع، داده‌های بیشتری تولید شده و پهنای باند بیشتری مصرف می‌شود. استفاده از کدگذاری شبکه سبب کاهش تعداد ارسال‌ها و ترافیک داده‌ها و درنتیجه کاهش مصرف پهنای باند در شبکه می‌شود. در مدل بهینه‌سازی BNCOM، چون مسیریابی داده‌های کدگذاری شده از یال‌هایی است که پهنای باند آزاد بیشتری دارند، لذا کمترین پهنای باند در شبکه مصرف شده است. همچنین مشاهده شده که با افزایش تعداد گره‌های حسگر منبع، تفاوت بین مدل بهینه‌سازی OPT با سایر مدل‌های بهینه‌سازی بیشتر مشخص می‌شود.

با افزایش دامنه ارسال گره‌های حسگر منبع، تعداد گره‌های همسایه یک گره حسگر منبع افزایش یافته و مصرف پهنای باند در شبکه افزایش می‌یابد. اما با افزایش تعداد همسایه‌ها، فرصت کدگذاری در شبکه نیز افزایش یافته و درنتیجه در مدل‌های بهینه‌سازی BNCOM و SIPNec و الگوریتم توزیع‌شده پیشنهادی BNCDA که از کدگذاری شبکه استفاده می‌کنند، سبب کاهش مصرف پهنای باند در شبکه نسبت به مدل بهینه‌سازی OPT که فاقد کدگذاری شبکه است می‌شود.

 

5-4- ارزیابی مجموع انرژی مصرف شده در شبکه

شکل‌های 10 و 11، نتایج ارزیابی و بررسی تاثیر تعداد گره‌های حسگر منبع روی مجموع انرژی مصرف شده برحسب میلی ژول را به‌ترتیب برای دامنه ارسال گره‌های حسگر 10 و 20 متر نشان می‌دهند. هرچه تعداد گره‌های حسگر منبع کمتر باشد، داده‌های کمتری تولید شده و انرژی کمتری مصرف می‌شود و با افزایش تعداد گره‌های حسگر منبع، داده‌های بیشتری تولید شده و انرژی بیشتری مصرف می‌شود اما از کدگذاری شبکه بیشتر می‌توان استفاده کرد که سبب کاهش تعداد ارسال‌ها و ترافیک داده‌ها و درنتیجه کاهش مصرف انرژی در شبکه می‌شود. با افزایش دامنه ارسال گره‌های حسگر، تعداد همسایگان افزایش یافته و مصرف انرژی افزایش می‌یابد اما با افزایش تعداد همسایه‌ها، فرصت کدگذاری شبکه افزایش یافته و درنتیجه سبب کاهش مصرف انرژی در الگوریتم توزیع‌شده پیشنهادی BNCDA نسبت به روش‌های فاقد کدگذاری می‌شود.

 

 

img0 

شکل 10: تاثیر تعداد گره‌های حسگر منبع روی مجموع انرژی مصرف شده در شبکه برحسب بایت با دامنه ارسال 10 متر

 

img0 

شکل 11: تاثیر تعداد گره‌های حسگر منبع روی مجموع انرژی مصرف شده در شبکه برحسب بایت با دامنه ارسال 20 متر

 

مشاهده شده که با افزایش تعداد گره‌های حسگر منبع، تفاوت بین مدل‌هایی بهینه‌سازی که از کدگذاری شبکه استفاده می‌کنند با مدل بهینه‌سازی OPT که فاقد کدگذاری شبکه است بیشتر مشخص می‌شود. مدل بهینه‌سازی SIPNec نیز چون تعادل در مصرف پهنای باند را درنظر نمی‌گیرد، عملکرد ضعیف‌تری نسبت به مدل بهینه‌سازی BNCOM دارد. همچنین چون الگوریتم توزیع‌شده پیشهادی BNCDA، مسیریابی بسته‌های کدگذاری شده را بین گره‌های حسگر در هر مرحله به‌صورت پیوسته و توزیع‌شده انجام می‌دهد، طول عمر کوتاه‌تری نسبت به مدل‌های بهینه‌سازی دارد. مدل بهینه‌سازی OPT نیز چون فقط به تعیین مسیر بهینه برای ارسال داده‌ها می‌پردازد و از کدگذاری شبکه استفاده نمی‌کند، به دلیل کوتاه بودن مسیر ارسال بسته‌ها، طول عمر بیشتری نسبت به سایر مدل‌ها دارد.

 

5-5- ارزیابی و بررسی طول عمر شبکه

یکی از مهمترین اهداف در شبکه‌های حسگر بی‌سیم، طولانی‌تر شدن عمر شبکه است. در این مقاله، مانند منابع [6, 7]، عمر شبکه را از زمان استقرار گره‌های حسگر تا تخلیه انرژی اولین گره حسگر تعریف می‌کنیم. چون مصرف انرژی برای ارسال بسته‌ها در گره‌های حسگر خیلی بیشتر از مصرف انرژی برای کدگذاری بسته‌ها در گره‌ها است، لذا طول عمر گره‌های حسگر نسبت معکوس با نرخ تولید بسته‌ها توسط گره‌های حسگر دارد. شکل 12، تاثیر افزایش تعداد گره‌های حسگر منبع روی طول عمر شبکه برحسب ثانیه را نشان می‌دهد. مشاهده شده که چون همه مدل‌های بهینه‌سازی از تعیین مسیر بهینه استفاده می‌کنند، تقریبا روند مشابهی دارند و با افزایش تعداد گره‌های حسگر منبع، میزان ارسال داده‌ها افزایش یافته و درنتیجه مصرف انرژی نیز در آنها افزایش یافته و درنتیجه طول عمر شبکه در آنها کاهش می‌یابد. همچنین مشاهده شده که چون مدل بهینه‌سازی BNCOM فقط به ایجاد تعادل در مصرف پهنای باند یال‌ها می‌پردازد و بسته‌ها را از یال‌هایی ارسال می‌کند که پهنای باند خالی بیشتری دارند، لذا شانس کدگذاری شبکه در این مدل کمتر از مدل بهینه‌سازی SIPNec بوده و طول عمر مدل بهینه‌سازی SIPNec بیشتر از مدل بهینه‌سازی BNCOM است.

img0 

شکل 12: تاثیر تعداد گره‌های حسگر منبع روی میانگین عمر شبکه برحسب ثانیه

 

5-6- ارزیابی و بررسی میانگین تاخیر انتها به انتها 

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

مشاهده شده که با افزایش تعداد گره‌های حسگر منبع، میزان داده‌ها در سطح شبکه افزایش یافته و میزان تاخیر برای ارسال داده‌های کدگذاری شده افزایش می‌یابد. اما چون مدل بهینه‌سازی BNCOM و الگوریتم توزیع‌شده پیشنهادی BNCDA از کدگذاری شبکه و ایجاد تعادل روی مصرف پهنای باند یال‌ها استفاده می‌کنند، سبب کاهش بسته‌های کدگذاری شده و تداخل و برخورد داده‌ها در لایه فیزیکی کمتر شده و درنتیجه نسبت به مدل‌های بهینه‌سازی SIPNec و OPT تاخیر انتها به انتها کمتری دارند. همچنین چون الگوریتم توزیع‌شده پیشنهادی BNCDA یک الگوریتم تکرارشونده است و برای مسیریابی بسته‌ها نیاز به چندین مرحله دارد، تاخیر آن بیشتر از مدل بهینه‌سازی BNCOM است.

اما چون مدل‌های بهینه‌سازی BNCOM و SIPNec و OPT به‌صورت متمرکز حل می‌شوند نیاز است که اطلاعات همه گره‌ها در یک گره مرکزی جمع شده و سپس مدل‌های بهینه‌سازی حل شوند و محاسبات انجام شده و آنگاه جواب محاسبات به سایر گره‌ها ارسال شود. بنابراین روش حل متمرکز برای شبکه‌های حسگر بی‌سیم با تعداد زیاد گره بسیار مشکل و زمان‌بر و تقریبا غیرعملی است.

img0 

شکل 13: تاثیر تعداد گره‌های حسگر منبع روی میانگین تاخیر انتها به انتها شبکه برحسب ثانیه

5-7- پیچیدگی زمانی برای رسیدن به جواب بهینه 

از عوامل دیگر در ایجاد تاخیر، پیچیدگی زمانی برای حل مدل و رسیدن به جواب بهینه است. انرژی لازم برای انجام محاسبات در گره‌های حسگر خیلی کمتر از انرژی مورد نیاز برای ارسال بسته‌ها است. اما گره‌های حسگر، توانایی محاسبات ضعیفی دارند و نمی‌توانند محاسبات پیچیده را انجام دهند. لذا هرچه پیچیدگی محاسبات کمتر باشد، کارایی مسیریابی بسته‌ها بهتر خواهد بود. شکل 14، نتایج ارزیابی و بررسی تاثیر تعداد گره‌های حسگر منبع روی میانگین زمان لازم برای یافتن مسیر بهینه را برحسب ثانیه نشان می‌دهد. 

مشاهده شده که زمان لازم برای یافتن مسیر بهینه در الگوریتم توزیع‌شده پیشنهادی BNCDA به مراتب کمتر از مدل‌های بهینه‌سازی BNCOM و SIPNec و OPT است. زیرا این الگوریتم، توزیع‌شده بوده و نیاز به جمع‌آوری اطلاعات کل شبکه در یک نقطه متمرکزی نیست و محاسبات ساده‌ای دارد، لذا گره‌های حسگر به‌راحتی و همزمان می‌توانند این الگوریتم را اجرا کنند. بنابراین این الگوریتم در شبکه‌های حسگر بی‌سیم با تعداد زیادی گره قابل اجرا و مقیاس‌پذیر است. البته تعداد تکرار الگوریتم توزیع‌شده پیشنهادی BNCDA وابسته به سرعت همگرایی است.

 

img0 

شکل 14: تاثیر تعداد گره‌های حسگر منبع روی میانگین زمان لازم برای یافتن مسیر بهینه را برحسب ثانیه

 

 

 

5-8- ارزیابی کل مقدار جریان مجازی در یال‌ها یا 𝑉

کل مقدار جریان مجازی در یال‌ها نسبت عکس با فاصله بین گره‌های حسگر دارد و هرچه فاصله بین گره‌های حسگر کمتر شود، مقدار جریان مجازی بیشتری روی یال‌ها در جریان خواهد بود. شکل 15، نتایج ارزیابی و بررسی تاثیر تعداد گره‌های حسگر منبع روی کل مقدار جریان مجازی در یال‌ها برحسب بایت تا دقیقه 20 را نشان می‌دهد. مشاهده شده که با افزایش تعداد گره‌های حسگر منبع، کل مقدار جریان مجازی در یال‌ها یا 𝑉 در همه مدل‌ها و الگوریتم توزیع‌شده پیشنهادی BNCDA افزایش می‌یابد. چون مدل‌های بهینه‌سازی BNCOM و SIPNec و OPT متمرکز و بهینه هستند و از مسیریابی آگاهانه داده‌های کدگذاری شده در شبکه استفاده می‌کنند، سبب کاهش طول مسیریابی بین گره‌های حسگر و کاهش کل مقدار جریان مجازی در یال‌ها می‌شوند. هرچه تعداد گره‌های حسگر منبع کمتر باشد، طول مسیر ارسال داده‌ها افزایش یافته که سبب کاهش کل مقدار جریان مجازی در یال‌ها می‌شود. اما با افزایش تعداد گره‌های حسگر منبع، استقرار گره‌های حسگر منبع در مرکز بیشتر شده و طول مسیریابی داده‌های کدگذاری شده کاهش یافته و کل مقدار جریان مجازی در یال‌ها افزایش می‌یابد.

 

img0 

شکل 15: تاثیر تعداد گره‌های حسگر منبع روی کل مقدار جریان مجازی در یال‌ها یا 𝑉 برحسب بایت

 

همچنین مشاهده شده که کل مقدار جریان مجازی در یال‌ها در الگوریتم توزیع‌شده پیشنهادی BNCDA بیشتر از مدل‌های بهینه‌سازی است. به‌طوری‌که‌ اگر تعداد گره‌های حسگر منبع برابر 4 باشد، فاصله بین الگوریتم توزیع‌شده پیشنهادی BNCDA با دو مدل بهینه‌سازی BNCOM و SIPNec تقریبا یک کیلو بایت و با مدل بهینه‌سازی OPT تقریبا دو کیلو بایت است و اگر تعداد گره‌های حسگر منبع برابر 35 باشد، فاصله بین الگوریتم توزیع‌شده پیشنهادی BNCDA و دو مدل بهینه‌سازی BNCOM و SIPNec تقریبا تغییر نمی‌کند اما فاصله بین الگوریتم توزیع‌شده پیشنهادی BNCDA و مدل بهینه‌سازی OPT بسیار بیشتر (15 برابر) می‌شود که دلیل آن عدم استفاده مدل بهینه‌سازی OPT از کدگذاری شبکه و ایجاد تعادل در مصرف پهنای باند است.

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

یکی از محدودیت‌ها در شبکه‌های حسگر بی‌سیم، میزان پهنای باند موجود در شبکه است. مساله یافتن مسیر بهینه برای ارسال داده‌ها و ایجاد تعادل در مصرف پهنای باند شبکه، یک مساله NP-hard است. در این مقاله، یک مدل بهینه‌سازی با هدف تعیین مسیر بهینه برای ارسال داده‌ها و ایجاد تعادل در مصرف پهنای باند با استفاده از کدگذاری شبکه در شبکه‌های حسگر بی‌سیم ارائه شد. چون برای حل مدل بهینه‌سازی باید اطلاعات به یک گره مرکزی ارسال شود، برای حل این مشکل یک الگوریتم توزیع‌شده و تکرارشونده ارائه شده که براساس روش زیرگرادیان و روش تفکیک جریان‌های شبکه است و به‌صورت پویا و پیوسته و براساس پهنای باند باقیمانده گره‌های حسگر، مسیر بهینه را برای ارسال داده‌های کدگذاری شده تعیین می‌کند.

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

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

مراجع

[1]        E. Kharati, M. Khalily-D, and H. Kermajani, “Increasing the Value of Collected Data and Reducing ‎Energy ‎Consumption Using Network Coding and Mobile Sinks in Wireless Sensor Networks”, AUT Journal of ‎Modeling and ‎Simulation, 2019.‎

[2]        E. Kharati, M. Khalily-Dermany, and H. Karmajani, “Increasing the Amount of Collected Data using Network Coding and Continuous Movement of Mobile Sinks in Wireless Sensor Networks,” IET Networks, 2019.

[3]        E. Kharati, “Mobile Sink Routing Control to Maximize the Amount of Collected Data and Lifetime in ‎Underwater ‎Wireless Sensor Networks,” TABRIZ JOURNAL OF ELECTRICAL ENGINEERING (TJEE), vol. ‎‎50, no. Computer, 2020.

[4]        E. Kharati, M. Khalily-D, and H. Kermajani, “Optimized sink control to increase the lifetime ‎of ‎underwater ‎wireless sensor networks”, Computer and Knowledge Engineering‎, 2019. 9.‎

[5]        E. Kharati, “Decrease round-trip time in Reno TCP,” 6th International Symposium on Telecommunications (IST), IEEE, pp 733-736, 2012.

[6]        E. Kharati, and M. Khalily-Dermany, “Determination of the Multicast Optimal Route for Mobile Sinks in a Specified Deadline Using Network Coding and Tabu Search Algorithm in Wireless Sensor Networks,” Iranian Journal of Science and Technology, Transactions of Electrical Engineering, 2020/08/17, 2020.

[7]        S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang, "A New MILP Formulation and Distributed Protocols for Wireless Sensor Networks Lifetime Maximization." pp. 3517-3524.

[8]        N. Sabor, S. Sasaki, M. Abo-Zahhad, and S. M. Ahmed, “A comprehensive survey on hierarchical-based routing protocols for mobile wireless sensor networks: review, taxonomy, and future directions,” Wireless Communications and Mobile Computing, vol. 2017, 2017.

[9]        Z. Fei, B. Li, S. Yang, C. Xing, H. Chen, and L. Hanzo, “A survey of multi-objective optimization in wireless sensor networks: Metrics, algorithms, and open problems,” IEEE Communications Surveys & Tutorials, vol. 19, no. 1, pp. 550-586, 2017.

[10]        W. Rehan, S. Fischer, and M. Rehan, “Anatomizing the robustness of multichannel MAC protocols for WSNs: An evaluation under MAC oriented design issues impacting QoS,” Journal of Network and Computer Applications, vol. 121, pp. 89-118, 2018/11/01/, 2018.

[11]        E. Kharati, “Creating Balance on Bandwidth Consumption using Network Coding in Wireless Sensor Networks,” Majlesi Journal of Electrical Engineering, vol. 14, no. 3, pp. 23-38, 2020.

[12]        C. Lv, Q. Wang, W. Yan, and J. Li, “A sparsity feedback-based data gathering algorithm for Wireless Sensor Networks,” Computer Networks, vol. 141, pp. 145-156, 2018/08/04/, 2018.

[13]        R. Logambigai, S. Ganapathy, and A. Kannan, “Energy–efficient grid–based routing algorithm using intelligent fuzzy rules for wireless sensor networks,” Computers & Electrical Engineering, vol. 68, pp. 62-75, 2018/05/01/, 2018.

[14]        C. Li, J. Bai, J. Gu, X. Yan, and Y. Luo, “Clustering routing based on mixed integer programming for heterogeneous wireless sensor networks,” Ad Hoc Networks, vol. 72, pp. 81-90, 2018/04/01/, 2018.

[15]        O. M. Al-Kofahi, and A. E. Kamal, "Transmissions Scheduling in Network Coding-Based Resilient WSNs," Resilient Wireless Sensor Networks, pp. 53-65: Springer, 2015.

[16]        C. Abreu, F. Miranda, and P. M. Mendes, “Smart context-aware QoS-based admission control for biomedical wireless sensor networks,” Journal of Network and Computer Applications, vol. 88, pp. 134-145, 2017/06/15/, 2017.

[17]        N. Javaid, S. Hussain, A. Ahmad, M. Imran, A. Khan, and M. Guizani, “Region based cooperative routing in underwater wireless sensor networks,” Journal of Network and Computer Applications, vol. 92, pp. 31-41, 2017/08/15/, 2017.

[18]        I. L. C. Vasconcelos, I. C. Martins, C. M. S. Figueiredo, and A. L. L. Aquino, “A data sample algorithm applied to wireless sensor network with disruptive connections,” Computer Networks, vol. 146, pp. 1-11, 2018/12/09/, 2018.

[19]        A. Abuarqoub, M. Hammoudeh, B. Adebisi, S. Jabbar, A. Bounceur, and H. Al-Bashar, “Dynamic clustering and management of mobile wireless sensor networks,” Computer Networks, vol. 117, pp. 62-75, 2017/04/22/, 2017.

[20]        خراطی احسان (2020). "کنترل مسیریابی چاهک‌های متحرک برای حداکثر کردن مقدار داده جمع‌آوری شده و طول عمر در شبکه‌های حسگر بی‌سیم زیرآب." مجله مهندسی برق دانشگاه تبریز.

[21]        M. Koç, and I. J. I. J. o. D. S. N. Korpeoglu, “Controlled sink mobility algorithms for wireless sensor networks,” vol. 10, no. 4, pp. 167508, 2014.

[22]        T. Ho, B. Leong, R. Koetter, M. Médard, M. Effros, and D. R. Karger, “Byzantine modification detection in multicast networks with random network coding,” IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2798-2803, 2008.

[23]        H. Kaushal, and G. Kaddoum, “Underwater optical wireless communication,” IEEE access, vol. 4, pp. 1518-1547, 2016. 

 

[1]  Integer Linear Programming

[2]  Mixed-integer linear programming

[3]  Karush–Kuhn–Tucker conditions

[4]  Non-deterministic Polynomial-time hard

[5]  Bandwidth Network Coding Optimization Model

[6]  Bandwidth Network Coding Distributed Algorithm

[7]  Mixed-integer linear programming

Increasing the Amount of Data and Reducing the Cost of Using Network Coding in Wireless Sensor Networks

 

 

Abstract:

This paper presents an optimization model to increase the amount of data collected and balance the bandwidth consumption of the edges and uses network coding. To solve this model, the dual method is used and to calculate a lower bound and find the optimal answer and point in the optimization model, the Karush-Kun-Tucker condition is used, which requires calculating the derivative of the Lagrangian function with respect to its variables. Solving this problem and equations in polynomial time is very difficult, time consuming and almost impractical due to the involvement of different parameters and limited resources of wireless sensor networks with a large number of nodes, so to solve this problem, a distributed and iterative algorithm is proposed. It uses the sub gradient method and the network flow separation method. The effectiveness of the proposed model and algorithm has been investigated by simulation in terms of number of source sensor nodes, Lagrangian coefficient and step size. Up to 23% of bandwidth consumed, average network life and energy consumed.

 

Keywords: Wireless Sensor Networks, Network Coding, Optional Route, Bandwidth.

نویسنده مسئول: احسان خراطی ehsan.kharati@gmail.com

43


رایمگ

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

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی

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

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

 

(𝑖)

 

(𝑖𝑖)

 

(𝑖𝑖𝑖)