دو الگوریتم نیروی مجازی فازی برای بهبود چیدمان حسگرها در شبکه‌های حسگر بی‌سیم
محورهای موضوعی :
1 - استادیار گروه مهندسی کامپیوتر، دانشگاه بجنورد، بجنورد، ایران
کلید واژه: پوشش حداکثری, جایابی حسگر, الگوریتم نیروی مجازی, سیستم فازی,
چکیده مقاله :
پوشش حداکثری منطقه یک هدف مهم در چیدمان حسگرهای شبکه حسگر بی‌سیم است که تحقق آن به افزایش توان نظارتی شبکه کمک می‌کند. در بسیاری از کاربردها حسگرها ابتدا به صورت تصادفی در منطقه تحت نظارت توزیع می‌شوند، سپس چیدمان آن‌ها باید طوری اصلاح شود که پوشش شبکه حداکثر گردد. الگوریتم نیروی مجازی (VFA) سعی می‌کند تا با در نظر گرفتن نیروهای دافعه و جاذبه بین حسگرها از یک چیدمان اولیه به یک چیدمان مطلوب‌تر برسد. در این مقاله از ترکیب سیستم فازی تاکاشی-سوگنو با الگوریتم نیروی مجازی برای دستیابی به چیدمان مجدد بهتری از حسگرها استفاده می‌شود. برای تنظیم وفقی پارامتر فاصله بهینه حسگرها در این مقاله دو روش فازی مطرح و اثر هر یک از آن‌ها بر افزایش کارآمدی الگوریتم نیروی مجازی بررسی خواهد شد. مقایسه عملکرد روش‌های پیشنهادی با روش‌های رقیب نشان می‌دهد که تنظیم هوشمندانه و وفقی فاصله بهینه به کمک سیستم فازی باعث دستیابی به نرخ پوشش بالاتر نسبت به الگوریتم نیروی مجازی سنتی (VFA)، الگوریتم نیروی مجازی بهبودیافته (IVFA)، الگوریتم توزیع مجدد فازی (FRED)، و روش‌های متاهیورستیک GA و PSO خواهد شد. همچنین، روش‌های پیشنهادی مبتنی بر نیروی مجازی نسبت به GA و PSO به زمان بسیار کمتری نیز برای حل مسئله نیاز دارند.
Maximizing area coverage is an important issue in the placement of wireless network sensors, the realization of which helps to improve the network monitoring power. In many applications, the sensors are first randomly distributed in the sensing filed and then their placement is modified. The virtual force algorithm (VFA) tries to achieve a more desirable deployment from an initial sensing deployment by considering repulsive and attractive forces between the sensors. In this paper, the combination of Takashi-Sugeno fuzzy system with VFA is used to achieve a better redeployment of the sensors. To adaptively adjust optimal distance value of the sensors, two fuzzy methods are proposed in this paper and their role in improving performance of the virtual force algorithm is analyzed. Comparison of the performance of the proposed methods with the state-of-the-art reveals that intelligent and adaptive adjustment of the optimal distance using a fuzzy system leads to higher final coverage ratio over traditional virtual force algorithm (VFA), improved virtual force algorithm (IVFA), fuzzy redeployment algorithm (FRED), and two metaheuristics GA, and PSO. On the other hand, the proposed VF-based methods require much less time to solve the problem than GA and PSO metaheuristic methods.
S. Fattah, A. Gani, I. Ahmedy, M. Y. I. Idris, and I. A. Targio Hashem, “A Survey on Underwater Wireless Sensor Networks: Requirements, Taxonomy, Recent Advances, and Open Research Challenges,” Sensors, vol. 20, no. 18, Art. no. 18, Jan. 2020, doi: 10.3390/s20185393.
D. Kandris, C. Nakas, D. Vomvas, and G. Koulouras, “Applications of Wireless Sensor Networks: An Up-to-Date Survey,” Appl. Syst. Innov., vol. 3, no. 1, 2020, doi: 10.3390/asi3010014.
S. Loganathan and J. Arumugam, “Clustering Algorithms for Wireless Sensor Networks Survey,” Sens. Lett., vol. 18, no. 2, pp. 143–149, Feb. 2020, doi: 10.1166/sl.2020.4193.
A. Singh, S. Sharma, and J. Singh, “Nature-inspired algorithms for Wireless Sensor Networks: A comprehensive survey,” Comput. Sci. Rev., vol. 39, p. 100342, Feb. 2021, doi: 10.1016/j.cosrev.2020.100342.
A. Boulmaiz, N. Doghmane, S. Harize, N. Kouadria, and D. Messadeg, “Chapter 9 - The use of WSN (wireless sensor network) in the surveillance of endangered bird species,” in Advances in Ubiquitous Computing, A. Neustein, Ed. Academic Press, 2020, pp. 261–306. doi: 10.1016/B978-0-12-816801-1.00009-8.
J.-A. Jiang et al., “A WSN-based automatic monitoring system for the foraging behavior of honey bees and environmental factors of beehives,” Comput. Electron. Agric., vol. 123, pp. 304–318, Apr. 2016, doi: 10.1016/j.compag.2016.03.003.
S. Cao and A. Sanchez-Azofeifa, “Modeling seasonal surface temperature variations in secondary tropical dry forests,” Int. J. Appl. Earth Obs. Geoinformation, vol. 62, pp. 122–134, Oct. 2017, doi: 10.1016/j.jag.2017.06.008.
J. Amutha, J. Nagar, and S. Sharma, “A Distributed Border Surveillance (DBS) System for Rectangular and Circular Region of Interest with Wireless Sensor Networks in Shadowed Environments,” Wirel. Pers. Commun., vol. 117, no. 3, pp. 2135–2155, Apr. 2021, doi: 10.1007/s11277-020-07963-2.
N. Jeyakkannan, P. Manimegalai, and G. P. Venkatesan, “Systematic CO2 monitoring using machine learning enabled WSN to develop the anti-hazard strategies for the future,” Int. J. Biomed. Eng. Technol., vol. 34, no. 1, pp. 31–44, 2020.
A. Ali, Y. K. Jadoon, S. A. Changazi, and M. Qasim, “Military Operations: Wireless Sensor Networks based Applications to Reinforce Future Battlefield Command System,” in 2020 IEEE 23rd International Multitopic Conference (INMIC), Nov. 2020, pp. 1–6. doi: 10.1109/INMIC50486.2020.9318168.
S. M. Mohamed, H. S. Hamza, and I. A. Saroit, “Coverage in mobile wireless sensor networks (M-WSN): A survey,” Comput. Commun., vol. 110, pp. 133–150, Sep. 2017, doi: 10.1016/j.comcom.2017.06.010.
R. Priyadarshi, B. Gupta, and A. Anurag, “Deployment techniques in wireless sensor networks: a survey, classification, challenges, and future research issues,” J. Supercomput., vol. 76, no. 9, pp. 7333–7373, Sep. 2020, doi: 10.1007/s11227-020-03166-5.
G. P. Gupta and S. Jha, “Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks,” Wirel. Netw., vol. 25, no. 6, pp. 3167–3177, Aug. 2019, doi: 10.1007/s11276-018-1709-0.
H. T. T. Binh, N. T. Hanh, L. V. Quan, N. D. Nghia, and N. Dey, “Metaheuristics for maximization of obstacles constrained area coverage in heterogeneous wireless sensor networks,” Appl. Soft Comput., vol. 86, p. 105939, 2020, doi: https://doi.org/10.1016/j.asoc.2019.105939.
D. Liang, H. Shen, and L. Chen, “Maximum Target Coverage Problem in Mobile Wireless Sensor Networks,” Sensors, vol. 21, no. 1, p. 184, Dec. 2020, doi: 10.3390/s21010184.
Z. Dong, C. Shang, C.-Y. Chang, and D. S. Roy, “Barrier Coverage Mechanism Using Adaptive Sensing Range for Renewable WSNs,” IEEE Access, vol. 8, pp. 86065–86080, 2020, doi: 10.1109/ACCESS.2020.2992867.
W. Barkhoda and H. Sheikhi, “Immigrant imperialist competitive algorithm to solve the multi-constraint node placement problem in target-based wireless sensor networks,” Ad Hoc Netw., vol. 106, p. 102183, Sep. 2020, doi: 10.1016/j.adhoc.2020.102183.
H. ZainEldin, M. Badawy, M. Elhosseini, H. Arafat, and A. Abraham, “An improved dynamic deployment technique based-on genetic algorithm (IDDT-GA) for maximizing coverage in wireless sensor networks,” J. Ambient Intell. Humaniz. Comput., vol. 11, no. 10, pp. 4177–4194, Oct. 2020, doi: 10.1007/s12652-020-01698-5.
M. Abo-Zahhad, S. M. Ahmed, N. Sabor, and S. Sasaki, “Rearrangement of Mobile Wireless Sensor Nodes for Coverage Maximization Based on Immune Node Deployment Algorithm,” Comput Electr Eng, vol. 43, no. C, pp. 76–89, Apr. 2015, doi: 10.1016/j.compeleceng.2015.04.003.
A. K. Paul and T. Sato, “Localization in Wireless Sensor Networks: A Survey on Algorithms, Measurement Techniques, Applications and Challenges,” J. Sens. Actuator Netw., vol. 6, no. 4, Art. no. 4, Dec. 2017, doi: 10.3390/jsan6040024.
K. Tarnaris, I. Preka, D. Kandris, and A. Alexandridis, “Coverage and k-Coverage Optimization in Wireless Sensor Networks Using Computational Intelligence Methods: A Comparative Study,” Electronics, vol. 9, no. 4, Art. no. 4, Apr. 2020, doi: 10.3390/electronics9040675.
B. Al-Fuhaidi, A. M. Mohsen, A. Ghazi, and W. M. Yousef, “An Efficient Deployment Model for Maximizing Coverage of Heterogeneous Wireless Sensor Network Based on Harmony Search Algorithm,” J. Sens., vol. 2020, p. 8818826, Nov. 2020, doi: 10.1155/2020/8818826.
Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Trans Embed Comput Syst, vol. 3, no. 1, pp. 61–91, Feb. 2004, doi: 10.1145/972627.972631.
C.-C. Yang and J.-H. Wen, “A Hybrid Local Virtual Force Algorithm for Sensing Deployment in Wireless Sensor Network,” in 2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Jul. 2013, pp. 617–621. doi: 10.1109/IMIS.2013.109.
Y. Li, B. Zhang, and S. Chai, “An energy balanced-virtual force algorithm for Mobile-WSNs,” in 2015 IEEE International Conference on Mechatronics and Automation (ICMA), Aug. 2015, pp. 1779–1784. doi: 10.1109/ICMA.2015.7237755.
X. Deng, Z. Yu, R. Tang, X. Qian, K. Yuan, and S. Liu, “An Optimized Node Deployment Solution Based on a Virtual Spring Force Algorithm for Wireless Sensor Network Applications,” Sensors, vol. 19, no. 8, p. 1817, Apr. 2019, doi: 10.3390/s19081817.
J. Xie, D. Wei, S. Huang, and X. Bu, “A Sensor Deployment Approach Using Improved Virtual Force Algorithm Based on Area Intensity for Multisensor Networks,” Math. Probl. Eng., vol. 2019, p. 8015309, Feb. 2019, doi: 10.1155/2019/8015309.
S. Liu, R. Zhang, and Y. Shi, “Design of coverage algorithm for mobile sensor networks based on virtual molecular force,” Comput. Commun., vol. 150, pp. 269–277, Jan. 2020, doi: 10.1016/j.comcom.2019.11.001.
W. Jun and G. Haoyang, “Virtual force field coverage algorithms for wireless sensor networks in water environments,” Int. J. Sens. Netw., vol. 32, no. 3, pp. 174–181, Jan. 2020, doi: 10.1504/IJSNET.2020.105564.
X. Wang, S. Wang, and D. Bi, “Virtual Force-Directed Particle Swarm Optimization for Dynamic Deployment in Wireless Sensor Networks,” in Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues, Berlin, Heidelberg, 2007, pp. 292–303. doi: 10.1007/978-3-540-74171-8_29.
M. Song, L. Yang, W. Li, and T. A. Gulliver, “Improving wireless sensor network coverage using the VF-BBO algorithm,” in 2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Aug. 2013, pp. 318–321. doi: 10.1109/PACRIM.2013.6625496.
S. Wang, X. Yang, X. Wang, and Z. Qian, “A Virtual Force Algorithm-Lévy-Embedded Grey Wolf Optimization Algorithm for Wireless Sensor Network Coverage Optimization,” Sensors, vol. 19, no. 12, Art. no. 12, Jan. 2019, doi: 10.3390/s19122735.
M. Li, J. Hu, and X. Cao, “A Two-Phase Coverage Control Algorithm for Self-Orienting Heterogeneous Directional Sensor Networks,” IEEE Access, vol. 8, pp. 88215–88226, 2020, doi: 10.1109/ACCESS.2020.2993554.
X. Qi, Z. Li, C. Chen, and L. Liu, “A wireless sensor node deployment scheme based on embedded virtual force resampling particle swarm optimization algorithm,” Appl. Intell., Sep. 2021, doi: 10.1007/s10489-021-02745-0.
O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” in Autonomous Robot Vehicles, I. J. Cox and G. T. Wilfong, Eds. New York, NY: Springer, 1990, pp. 396–404. doi: 10.1007/978-1-4613-8997-2_29.
L.-X. Wang, A course in fuzzy systems and control. Prentice-Hall, Inc., 1996.
A. Osmani, M. Dehghan, H. Pourakbar, and P. Emdadi, “Fuzzy-Based Movement-Assisted Sensor Deployment Method in Wireless Sensor Networks,” in 2009 First International Conference on Computational Intelligence, Communication Systems and Networks, Jul. 2009, pp. 90–95. doi: 10.1109/CICSYN.2009.97.
D. Izadi, J. Abawajy, and S. Ghanavati, “An Alternative Node Deployment Scheme for WSNs,” IEEE Sens. J., vol. 15, no. 2, pp. 667–675, Feb. 2015, doi: 10.1109/JSEN.2014.2351405.
D. Šoštarić and G. Mester, “Drone localization using ultrasonic TDOA and RSS signal: Integration of the inverse method of a particle filter,” FME Trans., vol. 48, no. 1, pp. 21–30, 2020, doi: 10.5937/fmet2001021S.
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههای 51 و 52 ، بهار و تابستان 1401 صص: 1_16 |
|
دو الگوریتم نیروی مجازی فازی برای بهبود چیدمان حسگرها در شبکه‌های حسگر بی‌سیم
وحید کیانی*
*استادیار گروه مهندسی کامپیوتر، دانشگاه بجنورد، بجنورد، ایران
تاریخ دریافت: 24/11/1399 تاریخ پذیرش: 12/10/1400
نوع مقاله: پژوهشی
چكیده
پوشش حداکثری منطقه یک هدف مهم در چیدمان حسگرهای شبکه حسگر بی‌سیم است، که تحقق آن به افزایش توان نظارتی شبکه کمک می‌کند. در بسیاری از کاربردها حسگرها ابتدا به صورت تصادفی در منطقه تحت نظارت توزیع می‌شوند، سپس چیدمان آن‌ها باید طوری اصلاح شود که پوشش شبکه حداکثر گردد. الگوریتم نیروی مجازی (VFA) سعی می‌کند تا با در نظر گرفتن نیروهای دافعه و جاذبه بین حسگرها از یک چیدمان اولیه به یک چیدمان مطلوب‌تر برسد. در این مقاله از ترکیب سیستم فازی تاکاشی-سوگنو با الگوریتم نیروی مجازی برای دستیابی به چیدمان مجدد بهتری از حسگرها استفاده می‌شود. برای تنظیم وفقی پارامتر فاصله بهینه حسگرها در این مقاله دو روش فازی مطرح و اثر هر یک از آن‌ها بر افزایش کارآمدی الگوریتم نیروی مجازی بررسی خواهد شد. مقایسه عملکرد روش‌های پیشنهادی با روش‌های رقیب نشان می‌دهد که تنظیم هوشمندانه و وفقی فاصله بهینه به کمک سیستم فازی باعث دستیابی به نرخ پوشش بالاتر نسبت به الگوریتم نیروی مجازی سنتی (VFA)، الگوریتم نیروی مجازی بهبودیافته (IVFA)، الگوریتم توزیع مجدد فازی (FRED)، و روش‌های متاهیورستیک GA و PSO خواهد شد. همچنین، روش‌های پیشنهادی مبتنی بر نیروی مجازی نسبت به GA و PSO به زمان بسیار کمتری نیز برای حل مسئله نیاز دارند.
واژگان کلیدی: پوشش حداکثری، اصلاح چیدمان حسگرها، الگوریتم نیروی مجازی، سیستم فازی
1. مقدمه
شبکه‌های حسگر بی‌سیم برای شناسایی اهداف، نظارت بر محیط، و شناسایی مکان اهداف در محیط‌های تحت نظارت به کار می‌روند [1] تا [4].
نویسنده مسئول: وحید کیانی v.kiani@ub.ac.ir
در سال‌های اخیر، از شبکه‌های حسگر بی‌سیم در کاربردهای مختلف نظارت بر محیط زیست و حیوانات [5] و [6]، نظارت بر جنگل‌ها و مراتع [7]، نظارت بر نواحی مرزی کشورها [8]، شناسایی بحران [9]، نظارت بر میدان نبرد [10]، شناسایی اشیاء پرنده از طریق امواج ماوراء صوت [11]، و بسیاری کاربردهای دیگر استفاده شده است. در تمام این کاربردها، یک هدف مهم حداکثرسازی پوشش شبکه حسگر است تا منطقه تحت نظارت به خوبی پوشش داده شود. مروری بر شبکه‌های حسگر بی‌سیم و کاربردهای آن‌ها در [2] ارائه شده است.
یک شبکه حسگر بی‌سیم شامل تعدادی حسگر است که در یک منطقه جغرافیایی توزیع می‌شوند تا بر آن منطقه نظارت داشته باشند. هر حسگر از یک باتری با انرژی محدود برخوردار است و توانایی ادراک محیط تا شعاعی محدود، برقراری ارتباط با سایر حسگرها در شعاعی محدود، و جابجایی به مکان جدید را دارد. دستیابی به یک چیدمان مناسب از حسگرها که منطقه تحت نظارت را به خوبی پوشش دهد یک مسئله مهم در شبکه حسگر بی‌سیم است [12] و [13].
مسئله جایابی حسگرها در سه شکل پوشش منطقه1، پوشش اهداف2، و پوشش مرز3 قابل بررسی است [14]. در مسئله پوشش منطقه، هدف تعیین مکان حسگرها در یک منطقه است طوری که شناسایی حضور اشیاء در آن منطقه با اطمینان بالایی ممکن باشد [15]. در مسئله پوشش اهداف، هدف تعیین مکان حسگرها در یک ناحیه برای پوشش تعدادی هدف است و مکان حسگرها باید طوری تعیین شود که تعدادی هدف مشخص با اطمینان بالایی تحت نظارت قرار گیرند [16]. در مسئله پوشش مرز، هدف چیدمان حسگرها برای نظارت بر مرز است که در آن حسگرها باید در طول یک مرز طوری توزیع شوند که عبور اشیاء از آن مرز با اطمینان بالایی شناسایی شود [17]. این مقاله بر مسئله جایابی حسگرهای شبکه بی‌سیم برای پوشش منطقه تمرکز دارد.
مسئله جایابی حسگرها با هدف پوشش منطقه، خود می‌تواند به دو شکل پوشش کامل یا تام 4، و پوشش حداکثری 5 مطرح شود. در پوشش کامل منطقه هدف، از نظر تعداد حسگر قابل استفاده محدودیتی نداریم، و هدف رسیدن به پوشش 100 درصدی منطقه هدف با استفاده از کمترین تعداد حسگر است [18]. در مسئله پوشش حداکثری، تعداد حسگرها از قبل مشخص است، و هدف تعیین مکان p حسگر است طوری که نرخ پوشش منطقه حداکثر شود [15]. در این مقاله ما بر پوشش حداکثری منطقه هدف با تعداد محدودی حسگر تمرکز داریم.
در مسئله پوشش حداکثری منطقه، ممکن است فرضی در مورد مکان اولیه حسگرها نداشته باشیم، یا این که جایابی حسگرها از یک چیدمان اولیه آغاز شود. از شکل اول این مسئله با عنوان حداکثرسازی پوشش منطقه [19]، و از شکل دوم با عنوان بهبود پوشش منطقه6 [20] یا چیدمان مجدد حسگرها7 [21] یاد می‌شود. یک نمونه از کاربردهایی که بهبود پوشش منطقه می‌تواند برای آن مناسب باشد، نظارت بر جنگل‌ها و محیط زیست است که در آن توزیع p حسگر متحرک در منطقه تحت نظارت تنها می‌تواند به کمک بالگرد یا هواپیما به صورت تصادفی انجام شده و کنترل کاملی بر نحوه توزیع اولیه حسگرها وجود ندارد [22]. در چنین کاربردهایی بعد از توزیع اولیه تصادفی، چیدمان اولیه p حسگر باید طوری اصلاح شود که شبکه حسگر به نرخ پوشش بیشتری دست یابد، و ضمناً میزان جابجایی حسگرها نیز کم باشد تا انرژی زیادی از حسگرها مصرف نشود. در این مقاله ما بر اصلاح چیدمان حسگرها برای دستیابی به حداکثر نرخ پوشش تمرکز داریم و فرض می‌کنیم که چیدمان اولیه‌ای از حسگرها جهت بهبود به الگوریتم داده شده است.
مروری بر تحقیقات پیشین در زمینه پوشش حداکثری منطقه در جدول 1 ارائه شده است. ما تحقیقات پیشین را در سه گروه بررسی خواهیم کرد. گروه اول، مطالعاتی که به حداکثرسازی پوشش منطقه هدف پرداخته‌اند و فرضی در مورد وجود یک چیدمان اولیه ندارند. گروه دوم، مطالعاتی که به اصلاح چیدمان حسگرها پرداخته‌اند و برای این منظور از الگوریتم نیروی مجازی یا نسخه‌های بهبودیافته آن استفاده کرده‌اند. گروه سوم، مطالعاتی که برای اصلاح چیدمان از الگوریتم‌های دیگری بهره گرفته‌اند.
بعضی تحقیقات تنها بر تولید چیدمان مناسبی که حداکثر پوشش را داشته باشد تمرکز کرده‌اند، و فرض می‌کنند که چیدمان اولیه‌ای وجود ندارد. به عنوان مثال، در [19] از یک الگوریتم ژنتیک با جواب‌های طول متغیر و یک عملگر تقاطع خاص برای حداکثرسازی پوشش منطقه در چیدمان حسگرها استفاده شده است. در [15] مسئله حداکثر پوشش با در نظر گرفتن موانع در محیط حل شده و در روش پیشنهادی از ترکیب الگوریتم توده ذرات و الگوریتم ژنتیک با الگوریتم نیروی مجازی، یک روش مقداردهی اولیه جدید، کاهش یکنواخت وزن اینرسی در الگوریتم توده ذرات، و مکانیزیم خاصی برای اثرگذاری بهترین جواب‌های جمعیت بر سایر جواب‌ها استفاده شده است. در [23] عملکرد الگوریتم ژنتیک و الگوریتم توده ذرات در ارائه چیدمانی با حداکثر نرخ پوشش مقایسه شده است. مسئله در دو حالت پوشش عادی و پوشش k تایی در نظر گرفته شده، و شبکه حسگر نیز در دو حالت همگن و ناهمگن مدل‌سازی شده است. در حالت ناهمگن فرض شده که شعاع ادراک حسگرهای مختلف در شبکه حسگر متفاوت باشد. در [24] فرض شده است که تعداد زیادی حسگر از قبل در منطقه هدف به صورت تصادفی توزیع شده باشند، سپس کمترین تعداد حسگر ممکن طوری از بین این حسگرها انتخاب شده‌اند که نرخ پوشش منطقه نیز حداکثر شود. در پژوهش مذکور، از الگوریتم جستجوی هارمونی برای انتخاب حسگرها استفاده شده، و علاوه بر حداکثرسازی پوشش، حداقل‌سازی هزینه مالی شبکه نیز لحاظ شده است.
[1] area coverage
[2] targets coverage
[3] barrier coverage
[4] complete coverage
[5] maximum coverage
[6] coverage improvement
[7] sensors redeployment
جدول1. مقایسه مطالعات انجام شده در زمینه پوشش حداکثری منطقه توسط شبکه‌های حسگر بی‌سیم
مرجع | نویسنده اول | سال | مسئله | الگوریتم پایه | روش حل |
[19] | ZainEldin | 2020 | حداکثرسازی پوشش | الگوریتم ژنتیک | بازنمایی طول متغیر کروموزوم، عملگر تقاطع جدید |
[15]
| Binh | 2020 | حداکثرسازی پوشش | الگوریتم ژنتیک، الگوریتم توده ذرات | مقداردهی اولیه جدید، تابع برازندگی جدید، عملگر نیروی مجازی، کاهش یکنواخت وزن اینرسی، اثرگذاری بهترین جواب‌ها، در نظر گرفتن موانع در محیط |
[23] | Tarnaris | 2020 | حداکثرسازی پوشش | الگوریتم ژنتیک، الگوریتم توده ذرات | مقایسه الگوریتم ژنتیک و الگوریتم توده ذرات |
[24] | Al-Fuhaidi | 2020 | حداکثرسازی پوشش | الگوریتم جستجوی هارمونی | استفاده از الگوریتم جستجوی هارمونی برای حداکثرسازی نرخ پوشش منطقه، انتخاب تعدادی حسگر از بین مجموعه حسگرها، در نظر گرفتن هزینه مالی شبکه |
[26] | Zou | 2004 | اصلاح چیدمان | الگوریتم نیروی مجازی سنتی | در نظر گرفتن نیروهای جاذبه و دافعه بین حسگرها، هدایت محلی هر حسگر به مکان جدید بر اساس نیروی کل وارده بر آن |
[27] | Yang | 2013 | اصلاح چیدمان | الگوریتم نیروی مجازی | استفاده از یک نیروی اضافه مبتنی بر چگالی برای توزیع یکنواخت حسگرها در منطقه هدف |
[28] | Li | 2015 | اصلاح چیدمان | الگوریتم نیروی مجازی | در نظر گرفتن توازن در انرژی مصرفی حسگرها، وزن دهی به نیروهای مجازی بر اساس میزان مشارکت آن‌ها در ایجاد توازن در انرژی باقیمانده کلیه حسگرها |
[29] | Deng | 2019 | اصلاح چیدمان | الگوریتم نیروی مجازی فنری | تنظیم نیروهای بین حسگرها بر اساس قوانین نیروی نیوتن و نیروی مرکزی خارجی، حداکثرسازی پوشش منطقه ضمن پرکردن حفره‌ها، استفاده از یک نیروی خارجی مرکزی |
[30] | Xie | 2019 | اصلاح چیدمان | الگوریتم نیروی مجازی | تنظیم مستقل فاصله بهینه بین حسگرها برای هر حسگر بر اساس چگالی حسگرها در ناحیه اطراف آن |
[31] | Liu | 2019 | اصلاح چیدمان | الگوریتم نیروی مجازی ملکولی | در نظر گرفتن شبکه نیرویی بین حسگرها و هدایت حسگرها برای پر کردن حفره‌ها |
[32] | Jun | 2020 | اصلاح چیدمان | الگوریتم نیروی مجازی متمرکز | بخش‌بندی فضا بر اساس ناحیه پوشش داده شده توسط هر حسگر، نظارت بر محیط‌های آبی و دریایی، تنظیم پارامترهای الگوریتم نیروی مجازی |
[33] | Wang | 2007 | اصلاح چیدمان | الگوریتم توده ذرات | بهره‌گیری از نیروی مجازی در بردار سرعت الگوریتم توده ذرات برای هدایت حسگرها در هر جواب به مکانی بهتر |
[21] | عثمانی | 2009 | اصلاح چیدمان | یک الگوریتم فازی | استفاده از یک سیستم فازی و نمودار ورونوی برای هدایت هر حسگر به مکانی بهتر |
[34] | Song | 2013 | اصلاح چیدمان | الگوریتم جغرافیای زیستی | در نظر گرفتن الگوریتم نیروی مجازی به عنوان یک عملگر جستجوی محلی در الگوریتم جغرافیای زیستی |
[35] | ایزدی | 2015 | اصلاح چیدمان | یک الگوریتم فازی | تعمیر چیدمان حسگرها پس از غیرفعال شدن بعضی حسگرها، استفاده از یک روش فازی برای انتخاب حسگری که باید جابجا شود |
[36] | Wang | 2019 | اصلاح چیدمان | الگوریتم گرگ خاکستری | به کار گیری پرواز لوی و عملگر نیروی مجازی در الگوریتم گرگ خاکستری |
[37] | Li | 2020 | اصلاح چیدمان | الگوریتم تکامل تفاضلی | در نظر گرفتن جهت برای حسگرها، تنظیم جهت حسگرها به کمک یک روش هیورستیک، حداکثرسازی پوشش ضمن حداقل سازی انرژی مصرفی حسگرها به کمک ترکیب الگوریتم نیروی مجازی با الگوریتم تکامل تفاضلی |
[38] | Qi | 2021 | اصلاح چیدمان | الگوریتم توده ذرات مبتنی بر نمونه‌گیری مجدد | در نظر گرفتن نیروی مجازی دافعه در نواحی مرزی منطقه هدف، ارائه یک الگوریتم نیروی مجازی بهبود یافته، ترکیب الگوریتم نیروی مجازی به عنوان یک عملگر جستجو با الگوریتم توده ذرات مبتنی بر نمونه‌گیری مجدد |
گروهی دیگر از محققین از الگوریتم نیروی مجازی و نسخه‌های بهبودیافته آن استفاده کرده‌اند تا یک چیدمان اولیه را اصلاح کرده و به چیدمان جدیدی برسند که نرخ پوشش را حداکثر نماید. الگوریتم نیروی مجازی با در نظر گرفتن محدودیت‌های مسئله، کار خود را از یک چیدمان اولیه به عنوان ورودی آغاز کرده و در تکرارهای متوالی با لحاظ کردن نیروهای مجازی بین حسگرها سعی می‌کند مکان حسگرها را طوری تغییر دهد که نرخ پوشش منطقه افزایش یابد. الگوریتم نیروی مجازی اولین بار توسط Khatib برای مسیریابی ربات‌ها و اجتناب از موانع مطرح شد [25]. این الگوریتم بر دو نظریه نیروی مجازی و نظریه بسته‌بندی دیسک استوار است، و با عناصری که باید جایابی شوند مشابه مولکول‌ها و الکترون‌ها رفتار می‌کند. توسعه الگوریتم نیروی مجازی برای حل مسئله اصلاح چیدمان حسگرها در شبکه حسگر بی‌سیم، با هدف افزایش نرخ پوشش منطقه، اولین بار در [26] انجام شد. ارزیابی‌های انجام شده در [26] نشان داد که این الگوریتم می‌تواند ضمن حفظ نیروی باتری، موقعیت حسگرها را طوری اصلاح کند که نرخ پوشش شبکه حسگر بی‌سیم بهبود یابد.
الگوریتم نیروی مجازی یک الگوریتم سریع و کارآمد است که در زمانی کوتاه ما را از یک چیدمان اولیه به چیدمان جدیدی با نرخ پوشش بالا می‌رساند. از آنجایی که در الگوریتم نیروی مجازی جابجایی هر حسگر به صورت محلی و در ناحیه اطراف آن انجام می‌شود، این الگوریتم برای بهبود چیدمان حسگرها به جابجایی کمتری نسبت به الگوریتم‌های دیگر نیاز دارد و انرژی باتری کمتری صرف اصلاح جایابی خواهد شد. این مزایا باعث شده است که الگوریتم نیروی مجازی توسط محققین مختلف مورد استفاده قرار گیرد و نسخه‌های بهبودیافته آن مطرح شوند. به عنوان مثال، در الگوریتم ترکیبی محلی نیروی مجازی HLVFA در کنار نیروهای مجازی مطرح در الگوریتم نیروی مجازی سنتی، از یک نیروی دافعه مبتنی بر چگالی نیز برای یکنواخت کردن توزیع حسگرها در منطقه استفاده شده است [27]. همجنین، الگوریتم نیروی مجازی بهبودیافته‌ای در [28] با هدف توزیع بهتر انرژی باقیمانده بین حسگرها مطرح شده است، که به نیروهای مختلف بر اساس میزان تأثیر آن‌ها در یکنواخت‌سازی انرژی مصرفی حسگرها وزن می‌دهد. الگوریتم Spring Virtual Force در [29] مطرح شده است، که در آن برای اصلاح چیدمان حسگرها از نیروهای کشسانی فنر، نیروی اصطلکاک، و نیروی کشش از مرکز در مکانیک نیوتنی استفاده شده است. در [30] از چگالی محلی ناحیه اطراف هر حسگر برای تعیین فاصله بهینه آن حسگر استفاده شده و برای تعیین ضرایب جاذبه و دافعه نیز روابط جدیدی پیشنهاد شده‌اند. در [31] الگوریتم نیروی مجازی مولکولی 1 VMFA مطرح شده است که در آن هر حسگر به عنوان یک مولکول در نظر گرفته شده و از شبکه نیرویی بین مولکول‌ها برای هدایت آن‌ها به مکان‌های بهتر و پر کردن حفره‌ها استفاده شده است. در [32] نسخه جدیدی از الگوریتم نیروی مجازی با عنوان الگوریتم میدان مجازی متمرکز2 FVFF مطرح شده است که فرض می‌کند منطقه هدف توسط حسگرهای مختلف بخش‌بندی شده و هر حسگر یک بخش از فضا را تحت پوشش قرار داده است. این روش با تنظیم پارامترهای الگوریتم نیروی مجازی و ضرایب جاذبه و دافعه توانسته است به نتایج خوبی برای پوشش محیط‌های آبی و دریایی دست یابد.
بعضی محققین نیز از الگوریتم‌های دیگری برای اصلاح چیدمان حسگرها استفاده کرده‌اند. در [33] الگوریتم توده ذرات PSO با نیروی مجازی ترکیب شده، و در محاسبه بردار سرعت هر ذره علاوه بر gbest و pbest از نیروی مجازی نیز استفاده شده است. در [21] یک سیستم فازی برای هدایت حسگرها به مکان‌های بهتر با بخش‌بندی ورونوی3 ترکیب شده است، و روش پیشنهادی الگوریتم توزیع مجدد فازی گره‌ها4 FRED نامیده شده است. در روش مذکور، منطقه هدف بر اساس مکان فعلی حسگرها توسط بخش‌بندی ورونوی به نواحی مجزایی تقسیم می‌شود. سپس هر حسگر بر اساس چندضعلی ورونوی محاطی آن به مکان جدیدی هدایت می‌شود، طوری که میزان پوشش آن ناحیه توسط حسگر افزایش یابد. در این روش از مجموعه‌های فازی برای انتخاب حسگرهایی که باید حرکت کنند و ارزیابی وضعیت هر حسگر استفاده شده است. الگوریتم VFBBO در [34] مطرح شده است، که در آن از نیروی مجازی به عنوان یک عملگر جستجوی محلی در الگوریتم جغرافیای زیستی BBO استفاده شده تا سرعت همگرایی افزایش یافته و چیدمان بهتری از حسگرها تولید شود. در [35] از یک سیستم فازی برای تصمیم‌گیری و انتخاب مناسب‌ترین حسگر جهت انتقال به مکانی جدید استفاده شده است تا یک چیدمان تخریب شده با جابجایی حسگرها بهبود داده شده و تعمیر شود. با رویکردی مشابه، در [36] عملگر نیروی مجازی با پرواز لوی و الگوریتم گرگ خاکستری GWO ترکیب شده‌اند تا سرعت همگرایی الگوریتم پایه افزایش یافته و چیدمان بهتری تولید شود. در [37] مسئله اصلاح چیدمان حسگرها برای حسگرهای جهت‌دار حل شده است، و از یک الگوریتم تکامل تفاضلی DE مبتنی بر نیروی مجازی برای بهبود نرخ پوشش چیدمان اولیه استفاده شده است. در [38] الگوریتم توده ذرات مبتنی بر نمونه‌گیری RPSO با نسخه بهبودیافته‌ای از الگوریتم نیروی مجازی ترکیب شده است که با تنظیم پارامترهایش می‌تواند به چیدمان‌های بهتری نسبت به الگوریتم نیروی مجازی سنتی دست یابد.
پارامترهای مختلف الگوریتم نیروی مجازی روی عملکرد این الگوریتم و جایابی نهایی تولید شده توسط آن اثرگذار هستند. یک پارامتر بسیار مهم، فاصله بهینه بین هر حسگر با حسگرهای همسایه آن است. الگوریتم نیروی مجازی سنتی سعی می‌کند جایابی حسگرها را طوری اصلاح کند که هر حسگر در فاصله بهینه نسبت به حسگرهای همسایه‌اش قرار گیرد [26]. مقدار فاصله بهینه در الگوریتم نیروی مجازی سنتی برای تمام حسگرها یکسان است. اگر فاصله بهینه بزرگ انتخاب شود، حسگرهای همسایه از هم فاصله می‌گیرند، و حفره‌های کوچکی بین آن‌ها ایجاد می‌شود. اگر فاصله بهینه کوچک انتخاب شود، حسگرهای همسایه بیش از حد در هم فرو می‌روند و مساحت ناحیه پوشش یافته کوچک خواهد شد. به همین دلیل، انتخاب مقدار فاصله بهینه باید بنا به شرایط مسئله انجام شود. در همین راستا، در این مقاله دو روش فازی مطرح خواهند شد که اولی مقدار فاصله بهینه را به صورت مشترک برای تمام حسگرها تنظیم می‌کند، در حالیکه روش پیشنهادی دوم مقدار فاصله بهینه هر حسگر را مستقل از سایر حسگرها تنظیم می‌کند. در بخش 2، مسئله اصلاح چیدمان حسگرها تشریح می‌گردد. در بخش 3، الگوریتم نیروی مجازی سنتی VFA تشریح خواهد شد. در بخش 4، اولین الگوریتم فازی پیشنهادی این مقاله با عنوان الگوریتم نیروی مجازی فازی FVFA برای تنظیم مقدار فاصله بهینه حسگرها مطرح خواهد شد. در بخش 5، دومین الگوریتم فازی پیشنهادی این مقاله با عنوان الگوریتم نیروی مجازی بهبودیافته فازی FIVFA مطرح خواهد شد. بخش 6 به ارزیابی عملکرد روش‌های پیشنهادی و مقایسه با روش‌های دیگر می‌پردازد. درنهایت، بخش 7 به نتیجه‌گیری از مقاله و مطرح کردن کارهای آینده اختصاص دارد.
2. مسئله اصلاح چیدمان حسگرها
در مسئله اصلاح چیدمان حسگرها5 برای پوشش منطقه، یک مکان‌یابی اولیه از p حسگر باید طوری در یک فضای پیوسته دو بعدی مستطیل شکل بهبود داده شود که تا حد امکان نرخ پوشش بیشتری به دست آید [26] و [30]. هر حسگر یک شعاع ادراک دارد که توسط پارامتر r مشخص می‌شود، و اشیائی را که در ناحیه دایره‌ای اطرافش به شعاع r مشاهده شوند با قطعیت کامل شناسایی خواهد کرد. هر حسگر متحرک فرض شده، و می‌تواند آزادانه به نقاط اطرافش روی صفحه (X,Y) حرکت کند. معمولا تمام حسگرها از یک نوع در نظر گرفته می‌شوند و شعاع ادراک یکسانی دارند. هدف مسئله، اصلاح مکان حسگرها است، طوری که نرخ پوشش شبکه افزایش یابد. هر جواب مسئله یک چیدمان از p حسگر است که می‌تواند به صورت یک p تایی مرتب به شکل S={(x1,y1 ),(x2,y2 ),…,(xp,yp)} نمایش یابد.
شکل 1 (الف) نمونه‌ای از چیدمان اولیه تصادفی 20 حسگر را در یک منطقه مربعی نشان می‌دهد که نرخ پوشش 42 درصد را فراهم ساخته است. در این شکل، چیدمان نامناسب حسگرها باعث شده است تا حسگرها در مکان‌هایی قرار گیرند که هم‌پوشانی زیادی داشته باشند و از طرف دیگر بخش‌های زیادی از فضا بدون پوشش باقی بمانند. در مقابل در چیدمان بهبودیافته که در شکل 1 (ب) نمایش داده شده است، از هم‌پوشانی‌های زاید بین حسگرها اجتناب شده و نرخ پوشش به 54 درصد افزایش یافته است.
به طور خلاصه ما فرضیات و خصوصیات زیر را برای مسئله اصلاح چیدمان حسگرها در نظر می‌گیریم:
1. تعداد حسگرها از قبل مشخص و برابر با p است.
2. ورودی مسئله یک چیدمان اولیه ازحسگرها در منطقه هدف است.
3. هدف مسئله افزایش نرخ پوشش چیدمان حسگرها در منطقه هدف است.
4. خروجی مسئله یک چیدمان بهبودیافته از حسگرها است.
5. شبکه حسگر همگن است. حسگرها همگی از یک نوع بوده و شعاع ادراک یکسان و خصوصیات مشابهی دارند.
6. میزان جابجایی حسگرها برای انتقال از چیدمان اولیه به چیدمان نهایی باید حتی الامکان کم باشد تا انرژی باتری حفظ شود.
شكل1 . مقایسه دو چیدمان از 20 حسگر: (الف) چیدمان نامناسب، (ب) چیدمان مناسب
3. الگوریتم نیروی مجازی سنتی
در کاربردهای نظارت بر محیط زیست و بعضی کاربردهای نظامی که جایابی حسگرها باید از یک چیدمان اولیه آغاز شده و سپس بهبود یابد، مسئله اصلاح چیدمان حسگرها می‌تواند با جستجوی محلی در فضای جستجو حل شود تا میزان جابجایی حسگرها نیز کم باشد. الگوریتم نیروی مجازی در سال 2004 در [26] توسط Zou برای اصلاح چیدمان حسگرها مورد استفاده قرار گرفته است. این الگوریتم اولین بار توسط Khatib برای مسیریابی ربات‌ها در محیط‌های دارای مانع مطرح شد [25]. این الگوریتم بر دو نظریه نیروی مجازی و نظریه بسته‌بندی دیسک استوار است، و با عناصری که باید جایابی شوند مشابه مولکول‌ها و الکترون‌ها رفتار می‌کند.
الگوریتم نیروی مجازی یک الگوریتم با تعدادی تکرار است که در هر تکرار هر حسگر را به میزان محدودی نسبت به تکرار قبلی جابجا می‌کند و در نهایت مسیرهایی کوتاه و هموار را برای حسگرها تولید می‌کند که آن‌ها را از چیدمان اولیه به چیدمان بهتر می‌رساند. این الگوریتم در تکرارهای متوالی از چیدمان اولیه S0 کار خود را آغاز کرده و در تکرار شماره k چیدمان بهبودیافته Sk+1 را از روی چیدمان Sk می‌سازد، و در طول n تکرار دنباله چیدمان‌های S0→S1→S2→⋯→Sn را تولید می‌کند. این دنباله از جواب‌ها یک دنباله جستجوی محلی در فضای چیدمان‌های ممکن را نشان می‌دهد. در نهایت، چیدمان نهایی Sn به عنوان جواب نهایی در نظر گرفته خواهد شد.
هدف الگوریتم نیروی مجازی شروع کار از یک چیدمان اولیه و بهبود آن برای پوشش بیشتر است. برای این منظور الگوریتم نیروی مجازی از نیروهای جاذبه، دافعه، و تجمیع آن‌ها برای هدایت هر حسگر به مکان جدید استفاده می‌کند. شبه کد الگوریتم نیروی مجازی سنتی در شکل 2 نمایش داده شده است. در این الگوریتم هر حسگر بر اساس نیروی کل وارده بر آن به موقعیت جدیدی حرکت می‌کند. هدف الگوریتم آن است که موقعیت حسگرها را طوری اصلاح کند که در یک فاصله بهینه dth نسبت به یکدیگر قرار گیرند. پارامتر فاصله بهینه مهم‌ترین پارامتر در الگوریتم نیروی مجازی است. استفاده از فاصله بهینه dth≥2r مانع از در هم روی حسگرها خواهد شد. در مقابل استفاده از فاصله بهینه dth<2r باعث می‌شود حسگرهای همسایه هم‌پوشانی پیدا کنند. در صورت استفاده از dth=√3r و تعداد لازم از حسگرها، امکان پوشش بدون حفره منطقه هدف ممکن می‌شود. معمولا مقدار فاصله بهینه در بازه r<dth<2r انتخاب می‌شود.
نیروی دافعه در الگوریتم نیروی مجازی باعث می‌شود تا حسگرهایی که بیش از حد در یکدیگر فرو رفته‌اند از هم فاصله بگیرند. چنانچه فاصله دو حسگر از dth کمتر باشد، نیروی دافعه توسط هر یک از آن‌ها بر دیگری اعمال می‌شود. از طرف دیگر وقتی دو حسگر همسایه فاصله زیادی از یکدیگر دارند، باید به هم نزدیک شوند تا به فاصله بهینه برسند. با این هدف، اطراف هر حسگر یک ناحیه جذب یا ناحیه همسایگی به شعاع R تعریف می‌شود. چنانچه فاصله دو حسگر از dth بیشتر و از R کمتر باشد، نیروی جاذبه توسط هر یک از آن‌ها بر دیگری اعمال می‌شود. وقتی دو حسگر در فاصله بهینه dth نسبت به یکدیگر قرار می‌گیرند، هیچ نیروی بین آن دو اعمال نمی‌شود. بر این اساس، نیروی وارده از حسگر si به حسگر sj در دستگاه مختصات قطبی به شکل زیر تعریف می‌شود [26]:
(1) |
|
که در آن dij فاصله مرکز دو حسگر را نشان می‌دهد، و dth فاصله بهینه دو حسگر است. wA ضریب جاذبه و wR ضریب دافعه است. پارامتر R حداکثر فاصله جذب بین دو حسگر همسایه را تعیین کرده و نقش شعاع همسایگی را بازی می‌کند. زاویه αij نیز زوایه خطی است که مرکز حسگر j را به مرکز حسگر i وصل می‌کند و نسبت به محور y ها محاسبه می‌شود.
بعد از این که نیروی وارده از هر حسگر به حسگر دیگر محاسبه شد، میانگین نیروهای وارده به حسگر i به عنوان نیروی کل وارده بر آن حسگر محاسبه و موقعیت جدید حسگر i بر اساس نیروی وارده به آن و موقعیت قبلی‌اش تعیین می‌شود. جابجایی حسگرها در تکرارهای متوالی بر اساس نیروهای جاذبه و دافعه وارد بر آن‌ها باعث می‌شود تا حسگرهای هم‌پوشان از یکدیگر فاصله بگیرند و حسگرهایی که از هم دور هستند به یکدیگر نزدیک شوند. موقعیت نهایی حسگرها نسبت به یکدیگر به پارامتر فاصله بهینه dth وابسته است و به همین دلیل فاصله بهینه نقش مهمی در کیفیت جایابی نهایی خواهد داشت.
شكل2. الگوریتم نیروی مجازی سنتی
4. الگوریتم نیروی مجازی فازی
کارایی الگوریتم نیروی مجازی در جایابی مناسب حسگرها به تنظیم مقادیر مناسب برای پارامترهای ورودی این الگوریتم وابسته است. پارامتر فاصله بهینه dth مهم‌ترین پارامتر الگوریتم نیروی مجازی است که چنانچه مقدار آن زیاد در نظر گرفته شود، حسگرها از یکدیگر فاصله می‌گیرند و فاقد هم‌پوشانی خواهند بود. در این
صورت حفره‌هایی بین حسگرها تشکیل خواهد شد. از طرف دیگر، اگر مقدار پارامتر فاصله بهینه کم باشد، حسگرها به شدت در هم فرو خواهند رفت و محدوده جغرافیایی کوچکی را پوشش خواهند داد.
مقدار مناسب پارامتر فاصله بهینه به تعداد حسگرها وابسته است. زیرا زمانی که تعداد حسگرها کم باشد، برای دستیابی به پوشش بالا باید از در هم روی آن‌ها اجتناب کنیم. در مقابل، زمانی که تعداد حسگرها زیاد است، باید اجازه دهیم که حسگرها با یکدیگر هم پوشانی پیدا کنند تا نواحی خالی باقیمانده بین حسگرهای همسایه نیز پوشش پیدا کنند. در این بخش ما از یک سیستم فازی تاکاشی-سوگنو [39]، برای تعیین وفقی مقدار مناسب فاصله بهینه بر اساس میزان کفایت تعداد حسگرها استفاده می‌کنیم. از آنجایی که در این روش پیشنهادی از یک سیستم فازی برای بهبود الگوریتم نیروی مجازی استفاده شده است، ما روش پیشنهادی خود را الگوریتم نیروی مجازی فازی 6 (FVFA) می‌نامیم. در روش پیشنهادی ما در ابتدای الگوریتم نیروی مجازی سنتی، قبل از شروع تکرارها، مقدار مناسب فاصله بهینه dth در الگوریتم نیروی مجازی بر اساس میزان کفایت تعداد حسگرها تعیین می‌شود. در این رویکرد، پارامتر فاصله بهینه برای تمام حسگرها مشترک فرض می‌شود، و روی مقدار یکسانی تنظیم می‌گردد.
شكل3. حداکثر پوشش یکنواخت یک منطقه بدون هم‌پوشانی حسگرها
برای طراحی سیستم فازی مناسب، نیاز است که معیاری برای میزان کفایت تعداد حسگرها داشته باشیم. به این منظور، حداقل تعداد حسگر لازم برای پوشش تمام منطقه تحت بررسی را بدون هم پوشانی حسگرها در نظر می‌گیریم و میزان کفایت تعداد حسگرها را بر اساس آن محاسبه می‌کنیم. شکل 3 را در نظر بگیرید که در آن، منطقه هدف به عرض W و ارتفاع H توسط تعداد کافی حسگر فاقد هم‌پوشانی به شعاع r پوشش داده شده است. با این شرط که حسگرها فاقد هم‌پوشانی باشند، تعداد حسگرهای لازم از طریق رابطه زیر قابل محاسبه است:
(2) |
|
اگر تعداد حسگرهای ورودی مسئله یعنی p از حداقل حسگرهای لازم یعنی p* کمتر یا مساوی باشد، باید از در هم روی حسگرها اجتناب کنیم. در این صورت مقدار فاصله بهینه باید روی مقدار dth=2r تنظیم شود. اما اگر تعداد حسگرهای ورودی از p* بیشتر باشد، باید به تدریج به حسگرها اجازه دهیم هم‌پوشانی پیدا کنند. در این حالت مقدار فاصله باید روی dth<2r تنظیم شود. لذا نسبت کفایت7 تعداد حسگرها را به شکل زیر تعریف می‌کنیم و آن را با SF نشان می‌دهیم:
(3) |
|
برای توصیف کلامی مقدار نسبت کفایت، مجموعه‌های فازی8 «low»، «medium»، «high»، «very_high»، «redundant» و «very_redundant» را مطابق شکل 4 در نظر گرفتیم.
شكل4. مقادیر کلامی و مجموعه‌های فازی متناظر با آن‌ها برای نسبت کفایت SF
در یک سیستم فازی تاکاشی-سوگنو [39]، در بخش تالی هر قانون باید مقدار خروجی سیستم به ازای آن قانون به صورت یک مقدار عددی یا یک تابعی عددی از ورودی‌ها بیان شود. سیستم فازی پیشنهادی باید مقادیر مختلف نسبت کفایت را به مقادیر مناسب فاصله بهینه در بازه r<dth<2r نگاشت دهد. بر همین اساس می‌توانیم مقدار فاصله بهینه را به صورت dth=k*r در نظر گرفته و ضریب k را به عنوان خروجی سیستم فازی در نظر بگیریم. در این صورت، مقدار متغیر خروجی k باید در بازه 1≤k≤2 انتخاب شود. بر اساس معیار نسبت کفایت، سیستم فازی سوگنو نشان داده شده در شکل 5 جهت محاسبه مقدار مناسب فاصله بهینه روی هر نمونه مسئله طراحی شد.
در این سیستم فازی، میزان تحریک9 هر قانون بر اساس درجه عضویت10 محاسبه شده از بخش مقدم آن قانون تعیین می‌شود. سپس مقدار ضریب فاصله بهینه k برای حسگر جاری بر اساس خروجی هر قانون و میزان تحریک هر قانون، به کمک روش مرکز ثقل11 محاسبه می‌شود. اگر خروجی قانون شماره i را با ki و میزان تحریک آن قانون را با μ(ki) نشان دهیم، خروجی کل سیستم فازی به شکل زیر محاسبه می‌شود:
(4) |
|
استفاده از روش مرکز ثقل باعث می‌شود تا برای هر مقدار نسبت کفایت، خروجی سیستم به صورت یک عدد حقیقی-مقدار بر اساس مقادیر مشخص شده در بخش تالی قوانین سیستم درون‌یابی شود. مقدار ضریب فاصله بهینه k که توسط این سیستم برای هر مقدار نسبت کفایت محاسبه می‌شود در نمودار شکل 6 نمایش داده شده است.
پارامتر شعاع جذب R نیز یک پارامتر موثر دیگر در الگوریتم نیروی مجازی است که مقدار آن نیز می‌تواند بر اساس شعاع ادراک هر حسگر و به کمک رابطه R=h*r تعیین شود؛ که در آن سمبل h را ضریب شعاع جذب می‌نامیم. در این بخش، ضریب شعاع جذب نیز بر اساس نسبت کفایت و به کمک یک سیستم فازی سوگنو با قوانین نشان داده شده در شکل 7 محاسبه شد.
دو پارامتر دیگر در الگوریتم نیروی مجازی ضریب نیروی دافعه و ضریب نیروی جاذبه هستند. نیروی دافعه در الگوریتم نیروی مجازی نقش مهم‌تری نسبت به نیروی جاذبه دارد، زیرا باعث فاصله گرفتن حسگرهای در هم فرو رفته و افزایش سریع نرخ پوشش می‌شود. به همین دلیل معمولا ضریب نیروی دافعه مقدار بزرگتری نسبت به ضریب نیروی جاذبه دارد. در این پژوهش، ما مقدار wR=0.1 را برای ضریب نیروی دافعه، و wA=0.01 را برای ضریب نیروی جاذبه پیشنهاد می‌دهیم.
شكل5. مجموعه قوانین سیستم فازی FVFA برای محاسبه ضریب فاصله بهینه بر اساس نسبت کفایت
شكل6. مقدار ضریب فاصله بهینه متناظر با نسبت کفایت در مسئله ورودی که به کمک سیستم فازی FVFA محاسبه شده است
شكل7. مجموعه قوانین سیستم فازی پیشنهادی برای محاسبه ضریب شعاع جذب بر اساس معیار نسبت کفایت در سیستم فازی FVFA
5. الگوریتم نیروی مجازی بهبودیافته فازی
Xie و همکاران در سال 2019 پیشنهاد داده‌اند که مقدار فاصله بهینه برای هر حسگر مستقل از سایر حسگرها تعیین شود [30]. در روش پیشنهادی ایشان که الگوریتم نیروی مجازی بهبودیافته (IVFA) نامیده شده است، مقدار مناسب پارامتر فاصله بهینه برای هر حسگر بر اساس تعداد و چگالی محلی حسگرها در آن ناحیه تعیین می‌شود. زمانی که تعداد حسگرها در ناحیه اطراف حسگر فعلی زیاد باشد، برای دستیابی به پوشش بالا باید از در هم روی آن‌ها اجتناب کنیم. در مقابل، زمانی که تعداد حسگرها در یک ناحیه محلی کم است، باید اجازه دهیم که حسگرها به یکدیگر نزدیک شوند تا نواحی خالی باقیمانده بین حسگرهای همسایه نیز پوشش پیدا کنند. به این ترتیب حسگرها به تدریج از نواحی پر چگالی به سمت نواحی کم چگالی حرکت می‌کنند تا پوشش یکنواختی به دست آید. با این وجود، در روش پیشنهادی Xie مقدار فاصله بهینه هر حسگر تنها روی یکی از دو مقدار dth=2r یا dth=√3r تنظیم می‌شود، و مقادیر بین این دو در نظر گرفته نشده‌اند.
در این بخش ما از یک سیستم فازی تاکاشی-سوگنو [39]، برای تعیین وفقی مقدار مناسب فاصله بهینه بر اساس چگالی محلی حسگرها در اطراف هر حسگر استفاده می‌کنیم. از آنجایی که در روش پیشنهادی ما از یک سیستم فازی برای اصلاح الگوریتم نیروی مجازی بهبودیافته استفاده شده است، ما روش پیشنهادی خود را الگوریتم نیروی مجازی بهبودیافته فازی12 (FIVFA) می‌نامیم. در روش پیشنهادی ما در هر تکرار از الگوریتم نیروی مجازی سنتی، قبل از محاسبه نیروهای جاذبه و دافعه بین حسگرها، مقدار مناسب فاصله بهینه dth برای هر حسگر بر اساس چگالی محلی حسگرها در اطراف آن حسگر تعیین می‌شود. بدین منظور ابتدا چگالی محلی برای هر حسگر با الهام از [30]، طبق رابطه زیر محاسبه می‌شود:
(5) |
|
که در آن مخرج کسر فاصله حسگر جاری تا هر حسگر دیگر را محاسبه می‌کند. به این ترتیب، زمانی که فاصله حسگر جاری تا سایر حسگرها کم باشد، مقدار چگالی محلی بزرگ خواهد بود. در مقابل، زمانی که فاصله حسگرهای دیگر تا حسگر جاری زیاد باشد، مقدار چگالی محلی کوچک خواهد بود.
بعد از محاسبه چگالی محلی هر حسگر، لازم است چگالی محلی حسگر جاری با میانگین چگالی محلی کلیه حسگرها مقایسه شود. به این منظور نسبت چگالی محلی13 به میانگین چگالی محلی کل حسگرها را برای هر حسگر به شکل زیر محاسبه می‌کنیم:
(6) |
|
که در آن مخرج کسر میانگین چگالی محلی کلیه حسگرها را نشان می‌دهد، و صورت کسر چگالی محلی حسگر شماره i را نشان می‌دهد.
ورودی سیستم فازی پیشنهادی، مقدار RTi نسبت چگالی محلی برای حسگر جاری و خروجی آن مقدار مناسب dth فاصله بهینه برای حسگر جاری است. مقدار نسبت چگالی محلی معمولا در بازه 0.5≤RTi≤1.5 قرار می‌گیرد. با این وجود، برای اطمینان بیشتر، ما مقدار نسبت چگالی محلی را در بازه 0≤RTi≤2.0 در نظر گرفته و مقادیر کلامی متغیر ورودی نسبت چگالی محلی را روی این بازه تعریف می‌کنیم. برای توصیف کلامی مقدار نسبت چگالی محلی حسگر جاری، مجموعه‌های فازی «very_low»، «low»، «normal»، «high» و «very_high» را مطابق شکل 8 در نظر گرفتیم.
هدف روش پیشنهادی ما ایجاد یک پوشش یکنواخت در منطقه هدف است، طوری که چگالی محلی تمام حسگرها مشابه هم باشد. این پوشش یکنواخت از تمرکز بیش از حد حسگرها در یک بخش از منطقه هدف، و خالی ماندن بخش‌های دیگر اجتناب می‌کند، و در نهایت انتظار می‌رود نرخ پوشش کل منطقه را افزایش دهد. زمانی که چگالی محلی اطراف حسگر فعلی بالا است، مقدار فاصله بهینه باید بزرگ تعیین شود تا حسگرها به تدریج از هم فاصله بگیرند و چگالی محلی اطراف حسگر جاری به چگالی محلی سایر حسگرها نزدیک شود. بر عکس، زمانی که چگالی محلی اطراف حسگر جاری پائین است، فاصله بهینه باید کاهش یابد تا امکان نزدیک شدن حسگرها به یکدیگر افزایش یافته و به تدریج چگالی محلی حسگرها در آن ناحیه افزایش یابد. به این ترتیب، حسگرها به تدریج از بخش‌های پرچگالی به سمت بخش‌های کم چگالی حرکت خواهند کرد.
سیستم فازی پیشنهادی این بخش باید مقادیر مختلف نسبت چگالی محلی را به مقادیر مناسب فاصله بهینه در بازه خروجی r<dth<2r نگاشت دهد. بر همین اساس، مشابه بخش قبل، مقدار فاصله بهینه را به صورت dth=k*r در نظر گرفته و ضریب k را به عنوان خروجی سیستم فازی در نظر می‌گیریم. در این صورت، مقدار متغیر خروجی k باید مشابه بخش قبل در بازه 1≤k≤2 انتخاب شود، با این تفاوت که در این بخش برای هر حسگر مقدار k را مستقل از حسگرهای دیگر محاسبه می‌کنیم. بر این اساس، قوانین نمایش داده شده در شکل 9 به عنوان قوانین سیستم فازی پیشنهادی تعیین شدند. مقدار ضریب فاصله بهینه k که توسط این سیستم برای هر مقدار چگالی محلی محاسبه می‌شود در نمودار شکل 10 نمایش داده شده است. در این بخش، پارامتر شعاع جذب R روی مقدار R=3*r تنظیم شد.
شكل8. مقادیر کلامی و مجموعه‌های فازی متناظر با آن‌ها برای نسبت چگالی محلی RT
شكل9. مجموعه قوانین سیستم فازی FIVFA برای محاسبه ضریب فاصله بهینه
شكل10. نگاشت مقادیر مختلف نسبت چگالی محلی به مقادیر مناسب برای فاصله بهینه برای هر حسگر توسط سیستم فازی FIVFA
6. ارزیابی عملکرد
به‌منظور ارزیابی روش‌های پیشنهادی آزمایش‌های متعددی انجام شد، و کارایی روش پیشنهادی اول (FVFA) و روش پیشنهادی دوم (FIVFA) با الگوریتم نیروی مجازی سنتی (VFA) مطرح شده در [26]، الگوریتم نیروی مجازی بهبودیافته (IVFA) مطرح شده در [30]، الگوریتم چیدمان مجدد فازی گره‌ها (FRED) مطرح شده در [21]، الگوریتم ژنتیک (GA)، و الگوریتم توده ذرات (PSO) مورد مقایسه قرار گرفت. روش پیشنهادی و روش‌های رقیب همگی در محیط MATLAB پیاده‌سازی شدند. در آزمایش‌های این بخش جایابی حسگرها در یک منطقه مربعی با ابعاد [-2,+2]×[-2,+2] انجام شد. حداکثر تعداد دفعات تکرار الگوریتم نیز 100 تکرار در نظر گرفته شد. تمام آزمایش‌های این بخش روی یک سیستم با پردازنده Intel Core 2 Duo 2.53 GHZ و حافظه اصلی 4.00 GB اجرا شد. بعد از اتمام اجرای کامل تکرارهای الگوریتم، موقعیت نهایی حسگرها به‌عنوان خروجی الگوریتم در نظر گرفته شد، و نرخ پوشش به‌دست‌آمده برای موقعیت نهایی گزارش شد.
برای الگوریتم نیروی مجازی سنتی (VFA) در تمام اجراها مقدار پارامترها روی r=0.4، dth=1.2r، R=3r، wR=0.1، و wA=0.01 تنظیم شد. در الگوریتم نیروی مجازی بهبودیافته (IVFA) مطرح شده توسط Xie نیز از همین مقادیر پارامترها استفاده شد، به جز این که مقدار فاصله بهینه (dth) بسته به چگالی محلی اطراف هر حسگر روی یکی از دو مقدار dth=2r یا dth=√3r تنظیم شد. برای الگوریتم چیدمان مجدد فازی (FRED) پارامتر beta روی 2 تنظیم شد، و شعاع همسایگی نیز روی 3r تنظیم شد. در روش‌های پیشنهادی ما مقدار فاصله بهینه (dth) به صورت وفقی محاسبه شد که در سیستم فازی پیشنهادی اول (FVFA) مقدار فاصله بهینه برای تمام حسگرها به صورت مشترک محاسبه شد، اما در سیستم فازی پیشنهادی دوم (FIVFA) مقدار فاصله بهینه برای هر حسگر به صورت مستقل تعیین شد. همچنین در سیستم پیشنهادی اول (FVFA)، مقدار پارامتر شعاع جذب نیز به کمک یک سیستم فازی محاسبه شد. برای محاسبه نرخ پوشش در پایان هر آزمایش، منطقه هدف به کمک یک مشبکه 14 به تعدادی نقطه تقسیم شد و نسبت تعداد نقاط پوشش یافته به کل نقاط به عنوان نرخ پوشش در نظر گرفته شد.
شکل 11 چیدمان تولید شده توسط روش‌های پیشنهادی و چیدمان تولید شده توسط الگوریتم‌های رقیب را برای اصلاح چیدمان تصادفی اولیه 40 حسگر نشان می‌دهد. در چیدمان تصادفی اولیه با نرخ پوشش 16/67% تعداد زیادی از حسگرها روی هم قرار گرفته‌اند و بخش‌هایی از فضا نیز بدون پوشش باقی مانده‌اند. الگوریتم توزیع مجدد فازی (FRED) با بهره‌گیری از بخش‌بندی Voronoi توانسته است حسگرها را به مکان‌های بهتری هدایت کند و به نرخ پوشش 56/86% دست یافته است. الگوریتم ژنتیک (GA) و الگوریتم توده ذرات (PSO) در اصلاح چیدمان حسگرها چندان موفق نبوده‌اند و نرخ پوشش را به ترتیب به 56/81% و 69/77% افزایش داده‌اند. الگوریتم نیروی مجازی سنتی (VFA) نیز در توزیع یکنواخت حسگرها موفق نبوده است، و حسگرها در چیدمان نهایی همچنان در بعضی نواحی منطقه هدف تمرکز بیشتر و در سایر نواحی تمرکز کمی دارند. در نتیجه، الگوریتم نیروی مجازی سنتی نیز به نرخ پوشش نهایی به 29/78% دست یافته است. در مقابل، الگوریتم نیروی مجازی بهبودیافته (IVFA) و الگوریتم پیشنهادی نیروی مجازی بهبودیافته فازی (FIVFA) در توزیع یکنواخت حسگرها در منطقه هدف بسیار موفق‌تر عمل کرده‌اند، و به ترتیب به نرخ پوشش 12/90% و نرخ پوشش 23/94% دست یافته‌اند. در مجموع، روش‌های پیشنهادی ما توزیع یکنواختی از حسگرها را تولید کرده‌اند و به بالاترین نرخ پوشش در بین روش‌های مختلف دست یافته‌اند.
شکل 12 تغییرات نرخ پوشش را در تکرارهای متوالی برای روش‌های پیشنهادی با الگوریتم‌های رقیب مبتنی بر نیروی مجازی مقایسه می‌کند. اصلاح جایابی برای 40 حسگر انجام شده است. روش‌های پیشنهادی FIVFA و FVFA توانسته‌اند جایابی را در تکرارهای بیشتری بهبود دهند و به این ترتیب حسگرها را مرتباً به مکان‌های بهتری هدایت کنند. این در حالی است که الگوریتم VFA به دلیل استفاده از مقادیر نامناسبی برای پارامترها، خیلی زود متوقف شده است و بهبود بیشتر جایابی در آن ممکن نبوده است. الگوریتم IVFA نسبت به VFA جایابی را برای تکرارهای بیشتری ادامه داده است، اما عملکرد بدتری نسبت به روش‌های پیشنهادی ما داشته است. در مجموع روش‌های پیشنهادی ما نسبت به سایر روش‌ها، با تنظیم وفقی پارامتر فاصله بهینه برای هر حسگر، توانسته‌اند به نرخ پوشش نهایی بالاتری دست پیدا کند و بهبود را برای تکرارهای بیشتری ادامه دهند.
شکل 13 نرخ پوشش به دست آمده در تکرارهای متوالی را برای روش‌های پیشنهادی با روش‌هایی مقایسه کرده است که از نیروی مجازی استفاده نمی‌کنند. روش‌های پیشنهادی FIVFA و FVFA با بهره‌گیری از نیروهای مجازی نسبت به الگوریتم‌های GA، PSO، و PRED حسگرها را به مکان‌های بهتری هدایت کرده و به نرخ پوشش بالاتری دست یافته‌اند. روش FRED که بر نمودار ورونوی مبتنی است، خیلی زود متوقف شده و امکان بهبود بیشتر جایابی در آن وجود نداشته است. الگوریتم‌های متاهیورستیک GA و PSO با این که اجرا را تا 100 تکرار ادامه داده‌اند، ولی به دلیل ناکارآمدی عملگرهای جستجو نتوانسته‌اند به نرخ پوشش مناسبی دست پیدا کنند. استفاده از نیروهای مجازی در روش‌های پیشنهادی ما بسیار موثر بوده و حسگرها را به مکان‌های بهتری هدایت کرده است.
[1] virtual molecular force algorithm (VMFA)
[2] focused virtual force field (FVFF)
[3] voronoi partition
[4] fuzzy redeployment (FRED)
[5] sensors redeployment
[6] fuzzy virtual force algorithm (FVFA)
[7] sufficiency factor
[8] fuzzy sets
[9] activation
[10] membership degree
[11] centroid
[12] fuzzy improved virtual force algorithm (FIVFA)
[13] area intensity ratio
[14] grid
شكل11. مقایسه جایابی انجام شده توسط روش‌های پیشنهادی (FVFA و FIVFA) با الگوریتم‌های رقیب برای 40 حسگر
شكل12. مقایسه تغییرات نرخ پوشش در تکرارهای متوالی برای الگوریتم‌های مبتنی بر نیروی مجازی
شكل13. مقایسه تغییرات نرخ پوشش در تکرارهای متوالی بین روش‌های پیشنهادی و الگوریتم‌های غیر نیروی مجازی
جدول2. عملکرد روش‌های پیشنهادی (FVFA و FIVFA) با روش‌های رقیب برای تعداد مختلف حسگرها از نظر نرخ پوشش چیدمان نهایی
p | Initial | GA | PSO | FRED | VFA | IVFA | FVFA | FIVFA |
20 | 41% | 53% | 52% | 54% | 46% | 49% | 54% | 53% |
30 | 56% | 72% | 69% | 72% | 63% | 74% | 76% | 79% |
40 | 67% | 82% | 78% | 86% | 78% | 90% | 90% | 94% |
50 | 82% | 89% | 89% | 87% | 89% | 92% | 93% | 97% |
60 | 83% | 96% | 93% | 98% | 98% | 99% | 100% | 100% |
70 | 94% | 99% | 98% | 100% | 100% | 100% | 100% | 100% |
جدول3. عملکرد روش‌های پیشنهادی (FVFA و FIVFA) با روش‌های رقیب برای تعداد مختلف حسگرها از نظر زمان مصرفی (ثانیه)
p | GA | PSO | FRED | VFA | IVFA | FVFA | FIVFA |
20 | 73/24 | 13/31 | 83/16 | 86/0 | 52/0 | 38/1 | 12/3 |
30 | 52/23 | 06/32 | 96/16 | 37/1 | 06/1 | 07/1 | 13/4 |
40 | 56/27 | 27/33 | 33/32 | 94/0 | 91/0 | 37/1 | 19/5 |
50 | 59/25 | 43/35 | 19/23 | 92/0 | 49/0 | 13/1 | 38/4 |
60 | 27/27 | 36/36 | 51/27 | 09/1 | 59/0 | 16/1 | 07/3 |
70 | 32/29 | 09/40 | 88/42 | 35/1 | 72/0 | 14/1 | 25/3 |
شكل14. مقایسه نرخ پوشش چیدمان نهایی حاصل از روش‌های پیشنهادی (FVFA و FIVFA) با روش‌های رقیب برای تعداد مختلف حسگرها
شكل15. مقایسه زمان مصرفی روش‌های پیشنهادی (FVFA و FIVFA) با روش‌های رقیب برای تعداد مختلف حسگرها
در جدول 2، عملکرد روش پیشنهادی از نظر نرخ پوشش روی تعدادی نمونه مسئله با 20، 30، 40، 50، 70، و 100 حسگر با روش‌های رقیب مقایسه شده است. شکل 14 نرخ پوشش چیدمان نهایی را برای روش‌های مختلف با هم مقایسه می‌کند. با افزایش تعداد حسگرها، نرخ پوشش منطقه برای روش‌های مختلف روندی افزایشی داشته است. روش‌های پیشنهادی برای چیدمان 70 و 100 حسگر به پوشش 100 درصدی منطقه هدف دست یافته‌اند. از طرف دیگر، روش پیشنهادی دوم این پژوهش یعنی الگوریتم نیروی مجازی بهبودیافته فازی (FIVFA) برای تمام نمونه مسائل به نرخ پوشش بالاتری نسبت به روش‌های رقیب دست یافته است. روش پیشنهادی نیروی مجازی بهبودیافته فازی (FIVFA) و روش نیروی مجازی بهبودیافته (IVFA) برای نمونه مسائل مختلف توانسته‌اند با توزیع یکنواخت حسگرها در منطقه هدف به نرخ پوشش بالایی دست پیدا کنند.
جدول 3 زمان مصرفی روش پیشنهادی را با روش‌های رقیب برای تعداد مختلف حسگرها مقایسه می‌کند. شکل 15 زمان مصرفی روش‌های مختلف را به صورت یک نمودار نمایش می‌دهد. روش‌های متاهیورستیک الگوریتم ژنتیک (GA) و الگوریتم توده ذرات (PSO) که خیلی دیر همگرا می‌شوند و از جستجوی جمعیتی در فضای چیدمان‌های ممکن استفاده می‌کنند، زمان مصرفی بسیار بیشتری نسبت به الگوریتم‌های مبتنی بر نیروی مجازی داشته‌اند. روش فازی FRED که از ترکیب سیستم فازی با نمودار ورونوی استفاده می‌کند نیز به دلیل نیاز به محاسبه بخش‌بندی ورونوی و اشتراک نواحی بخش‌بندی شده با حسگرها زمان زیادی مصرف می‌کند. زمان مصرفی این سه روش برای مسئله‌ای با 100 حسگر بین 30 تا 40 ثانیه بوده است. روش‌های پیشنهادی ما یعنی FVFA و FIVFA نسبت به روش‌های مبتنی بر نیروی مجازی دیگر مثل VFA و IVFA زمان بیشتری مصرف کرده‌اند، اما این زمان بیشتر چندان چشمگیر نبوده و با توجه به نرخ پوشش بالاتر قابل تحمل است. از طرف دیگر، روش‌های پیشنهادی ما نسبت به GA، PSO، و FRED به زمان بسیار کمتری برای اصلاح چیدمان حسگرها نیاز دارند.
این نتایج نشان می‌دهند که روش پیشنهادی الگوریتم نیروی مجازی بهبودیافته فازی (FIVFA) در این مقاله توانسته است برای تمام نمونه مسائل بررسی شده به نرخ پوشش بالاتری نسبت به روش‌های رقیب دست یابد. از نظر زمان مصرفی نیز روش پیشنهادی ما نسبت به روش‌های متاهیورستیک بسیار سریع‌تر بوده، و نسبت به الگوریتم‌های قبلی مبتنی بر نیروهای مجازی کمی کندتر است. در مجموع، روش پیشنهادی FIVFA در این مقاله عملکرد خوبی را از نظر نرخ پوشش و زمان مصرفی در مقابل روش‌های رقیب دارد. روش پیشنهادی با بهره‌گیری از سیستم فازی برای تنظیم وفقی مقدار فاصله بهینه هر حسگر توانسته است به چیدمانی با چگالی محلی یکنواخت در حسگرهای مختلف دست یابد که از نظر نرخ پوشش کیفیت بسیار بالاتری نسبت به روش‌های رقیب دارد.
7. نتیجه‌گیری
در این مقاله دو روش بهبودیافته مبتنی بر الگوریتم نیروی مجازی و سسیستم فازی تاکاشی-سوگنو برای حل مسأله اصلاح جایابی حسگرها حین پوشش منطقه مطرح شد که در آن‌ها از سیستم فازی برای تنظیم فاصله بهینه حسگر تا حسگرهای همسایه استفاده شد. ارزیابی روش‌های پیشنهادی نشان داد که استفاده از سیستم فازی جهت تنظیم فاصله بهینه باعث می‌شود حسگرها به تدریج از نواحی پرچگالی به نواحی کم چگالی منتقل شوند، و در نهایت یک چیدمان یکنواخت از حسگرها در منطقه هدف تولید شود. تنظیم مقدار فاصله بهینه برای هر حسگر مستقل از سایر حسگرها به نتایج بهتری در ارزیابی‌های ما منجر شد. برای این منظور در روش پیشنهادی دوم این مقاله که آن را الگوریتم نیروی مجازی بهبودیافته فازی (FIVFA) می‌نامیم، مقدار فاصله بهینه برای هر حسگر بر اساس چگالی محلی حسگرها در ناحیه اطراف آن حسگر و به کمک یک سیستم فازی تاکاشی-سوگنو تنظیم شد. این روش از نظر نرخ پوشش در تمام نمونه مسائل بررسی شده عملکرد بهتری را نسبت به الگوریتم نیروی مجازی سنتی، الگوریتم نیروی مجازی بهبودیافته، الگوریتم چیدمان مجدد فازی، الگوریتم ژنتیک، و الگوریتم توده ذرات دارد. از نظر زمان مصرفی نیز روش‌های پیشنهادی ما که مبتنی بر نیروی مجازی هستند، سرعت بسیار بالاتری نسبت به روش‌های متاهیورستیک و روش‌های مبتنی بر بخش‌بندی ورونوی دارند. توسعه این رویکرد به حوزه‌های دیگر مانند پوشش اهداف و ترکیب آن با الگوریتم‌های متاهیورستیک می‌تواند موضوع کارهای آینده باشد.
سپاسگزاری
نویسنده مقاله بدین وسیله مراتب قدردانی خود را از جناب آقای دکتر حمید فدیشه‌ای استادیار گروه مهندسی کامپیوتر دانشگاه بجنورد برای راهنمایی‌های ارزشمند ایشان در مراحل مختلف این کار پژوهشی اعلام می‌دارد. همچنین، نویسنده مقاله مراتب قدردانی خود را از داوران محترم اعلام می‌دارد. بی‌شک نقطه نظرات ارزشمندشان در بهبود کیفیت مقاله نقش به‌سزایی داشته است.
مراجع
[1] S. Fattah, A. Gani, I. Ahmedy, M. Y. I. Idris, and I. A. Targio Hashem, “A Survey on Underwater Wireless Sensor Networks: Requirements, Taxonomy, Recent Advances, and Open Research Challenges,” J. Sens., vol. 20, no. 18:5393, pp. 1–30, Jan. 2020.
[2] D. Kandris, C. Nakas, D. Vomvas, and G. Koulouras, “Applications of Wireless Sensor Networks: An Up-to-Date Survey,” Appl. Syst. Innov., vol. 3, no. 1:14, pp. 1–24, 2020.
[3] S. Loganathan and J. Arumugam, “Clustering Algorithms for Wireless Sensor Networks Survey,” Sens. Lett., vol. 18, no. 2, pp. 143–149, Feb. 2020.
[4] A. Singh, S. Sharma, and J. Singh, “Nature-inspired algorithms for Wireless Sensor Networks: A comprehensive survey,” Comput. Sci. Rev., vol. 39:100342, pp. 1–53, Feb. 2021.
[5] A. Boulmaiz, N. Doghmane, S. Harize, N. Kouadria, and D. Messadeg, “The use of WSN (wireless sensor network) in the surveillance of endangered bird species,” in Advances in Ubiquitous Computing, A. Neustein, Ed. Academic Press, 2020, pp. 261–306.
[6] J.-A. Jiang et al., “A WSN-based automatic monitoring system for the foraging behavior of honey bees and environmental factors of beehives,” Comput. Electron. Agric., vol. 123, pp. 304–318, Apr. 2016.
[7] S. Cao and A. Sanchez-Azofeifa, “Modeling seasonal surface temperature variations in secondary tropical dry forests,” Int. J. Appl. Earth Obs. Geoinformation, vol. 62, pp. 122–134, Oct. 2017.
[8] J. Amutha, J. Nagar, and S. Sharma, “A Distributed Border Surveillance (DBS) System for Rectangular and Circular Region of Interest with Wireless Sensor Networks in Shadowed Environments,” Wirel. Pers. Commun., vol. 117, no. 3, pp. 2135–2155, Apr. 2021.
[9] N. Jeyakkannan, P. Manimegalai, and G. P. Venkatesan, “Systematic CO2 monitoring using machine learning enabled WSN to develop the anti-hazard strategies for the future,” Int. J. Biomed. Eng. Technol., vol. 34, no. 1, pp. 31–44, 2020.
[10] A. Ali, Y. K. Jadoon, S. A. Changazi, and M. Qasim, “Military Operations: Wireless Sensor Networks based Applications to Reinforce Future Battlefield Command System,” in 2020 IEEE 23rd International Multitopic Conference (INMIC), Bahawalpur, Pakistan, Nov. 5-7, 2020, pp. 1–6.
[11] D. Sostaric and G. Mester, “Drone localization using ultrasonic TDOA and RSS signal: Integration of the inverse method of a particle filter,” FME Trans., vol. 48, no. 1, pp. 21–30, 2020.
[12] S. M. Mohamed, H. S. Hamza, and I. A. Saroit, “Coverage in mobile wireless sensor networks (M-WSN): A survey,” Comput. Commun., vol. 110, pp. 133–150, Sep. 2017.
[13] R. Priyadarshi, B. Gupta, and A. Anurag, “Deployment techniques in wireless sensor networks: a survey, classification, challenges, and future research issues,” J. Supercomput., vol. 76, no. 9, pp. 7333–7373, Sep. 2020.
[14] G. P. Gupta and S. Jha, “Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks,” Wirel. Netw., vol. 25, no. 6, pp. 3167–3177, Aug. 2019.
[15] H. T. T. Binh, N. T. Hanh, L. V. Quan, N. D. Nghia, and N. Dey, “Metaheuristics for maximization of obstacles constrained area coverage in heterogeneous wireless sensor networks,” Appl. Soft Comput., vol. 86:105939, pp. 1–39, 2020.
[16] D. Liang, H. Shen, and L. Chen, “Maximum Target Coverage Problem in Mobile Wireless Sensor Networks,” J. Sens., vol. 21, no. 1:184, pp. 1–13, Dec. 2020.
[17] Z. Dong, C. Shang, C.-Y. Chang, and D. S. Roy, “Barrier Coverage Mechanism Using Adaptive Sensing Range for Renewable WSNs,” IEEE Access, vol. 8, pp. 86065–86080, 2020.
[18] W. Barkhoda and H. Sheikhi, “Immigrant imperialist competitive algorithm to solve the multi-constraint node placement problem in target-based wireless sensor networks,” Ad Hoc Netw., vol. 106: 102183, pp. 1–25, Sep. 2020.
[19] H. ZainEldin, M. Badawy, M. Elhosseini, H. Arafat, and A. Abraham, “An improved dynamic deployment technique based-on genetic algorithm (IDDT-GA) for maximizing coverage in wireless sensor networks,” J. Ambient Intell. Humaniz. Comput., vol. 11, no. 10, pp. 4177–4194, Oct. 2020.
[20] M. Abo-Zahhad, S. M. Ahmed, N. Sabor, and S. Sasaki, “Rearrangement of Mobile Wireless Sensor Nodes for Coverage Maximization Based on Immune Node Deployment Algorithm,” Comput. Electr. Eng., vol. 43, no. C, pp. 76–89, Apr. 2015.
[21] A. Osmani, M. Dehghan, H. Pourakbar, and P. Emdadi, “Fuzzy-Based Movement-Assisted Sensor Deployment Method in Wireless Sensor Networks,” in 2009 First International Conference on Computational Intelligence, Communication Systems and Networks, Indore, India, Jul. 23-25, 2009, pp. 90–95.
[22] A. K. Paul and T. Sato, “Localization in Wireless Sensor Networks: A Survey on Algorithms, Measurement Techniques, Applications and Challenges,” J. Sens. Actuator Netw., vol. 6, no. 4:24, pp. 1–23, Dec. 2017.
[23] K. Tarnaris, I. Preka, D. Kandris, and A. Alexandridis, “Coverage and k-Coverage Optimization in Wireless Sensor Networks Using Computational Intelligence Methods: A Comparative Study,” Electronics, vol. 9, no. 4:675, pp. 1–24, Apr. 2020.
[24] B. Al-Fuhaidi, A. M. Mohsen, A. Ghazi, and W. M. Yousef, “An Efficient Deployment Model for Maximizing Coverage of Heterogeneous Wireless Sensor Network Based on Harmony Search Algorithm,” J. Sens., vol. 2020:8818826, pp. 1–18, Nov. 2020.
[25] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” in Autonomous Robot Vehicles, I. J. Cox and G. T. Wilfong, Eds. New York, NY: Springer, 1990, pp. 396–404.
[26] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Trans Embed Comput Syst, vol. 3, no. 1, pp. 61–91, Feb. 2004.
[27] C.-C. Yang and J.-H. Wen, “A Hybrid Local Virtual Force Algorithm for Sensing Deployment in Wireless Sensor Network,” in 2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Taichung, Taiwan, Jul. 3-5, 2013, pp. 617–621.
[28] Y. Li, B. Zhang, and S. Chai, “An energy balanced-virtual force algorithm for Mobile-WSNs,” in 2015 IEEE International Conference on Mechatronics and Automation (ICMA), Beijing, China, Aug. 2-5, 2015, pp. 1779–1784.
[29] X. Deng, Z. Yu, R. Tang, X. Qian, K. Yuan, and S. Liu, “An Optimized Node Deployment Solution Based on a Virtual Spring Force Algorithm for Wireless Sensor Network Applications,” J. Sens., vol. 19, no. 8:1817, pp. 1–15, Apr. 2019.
[30] J. Xie, D. Wei, S. Huang, and X. Bu, “A Sensor Deployment Approach Using Improved Virtual Force Algorithm Based on Area Intensity for Multisensor Networks,” Mathematical Problems in Engineering, vol. 2019:8015309, pp. 1–10, Feb. 2019.
[31] S. Liu, R. Zhang, and Y. Shi, “Design of coverage algorithm for mobile sensor networks based on virtual molecular force,” Comput. Commun., vol. 150, pp. 269–277, Jan. 2020.
[32] W. Jun and G. Haoyang, “Virtual force field coverage algorithms for wireless sensor networks in water environments,” Int. J. Sens. Netw., vol. 32, no. 3, pp. 174–181, Jan. 2020.
[33] X. Wang, S. Wang, and D. Bi, “Virtual Force-Directed Particle Swarm Optimization for Dynamic Deployment in Wireless Sensor Networks,” in Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues, D.-S. Huang, L. Heutte, and M. Loog, Eds. Berlin, Heidelberg: Springer, 2007, pp. 292–303.
[34] M. Song, L. Yang, W. Li, and T. A. Gulliver, “Improving wireless sensor network coverage using the VF-BBO algorithm,” in 2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Victoria, BC, Canada, Aug. 27-29, 2013, pp. 318–321.
[35] D. Izadi, J. Abawajy, and S. Ghanavati, “An Alternative Node Deployment Scheme for WSNs,” IEEE Sens. J., vol. 15, no. 2, pp. 667–675, Feb. 2015.
[36] S. Wang, X. Yang, X. Wang, and Z. Qian, “A Virtual Force Algorithm-Lévy-Embedded Grey Wolf Optimization Algorithm for Wireless Sensor Network Coverage Optimization,” J. Sens., vol. 19, no. 12:2735, pp. 1–20, Jan. 2019.
[37] M. Li, J. Hu, and X. Cao, “A Two-Phase Coverage Control Algorithm for Self-Orienting Heterogeneous Directional Sensor Networks,” IEEE Access, vol. 8, pp. 88215–88226, 2020.
[38] X. Qi, Z. Li, C. Chen, and L. Liu, “A wireless sensor node deployment scheme based on embedded virtual force resampling particle swarm optimization algorithm,” Appl. Intell., vol. 2021, Sep. 2021.
[39] L.-X. Wang, A course in fuzzy systems and control. New Jersey: Prentice-Hall Press, 1996.
Two Fuzzy Virtual Force Algorithms to Improve Sensor Deployment in Wireless Sensor Networks
Abstract:
Maximizing area coverage is an important issue in the placement of wireless network sensors, the realization of which helps to improve the network monitoring power. In many applications, the sensors are first randomly distributed in the sensing filed and then their placement is modified. The virtual force algorithm (VFA) tries to achieve a more desirable deployment from an initial sensing deployment by considering repulsive and attractive forces between the sensors. In this paper, the combination of Takashi-Sugeno fuzzy system with VFA is used to achieve a better redeployment of the sensors. To adaptively adjust optimal distance value of the sensors, two fuzzy methods are proposed in this paper and their role in improving performance of the virtual force algorithm is analyzed. Comparison of the performance of the proposed methods with the state-of-the-art reveals that intelligent and adaptive adjustment of the optimal distance using a fuzzy system leads to higher final coverage ratio over traditional virtual force algorithm (VFA), improved virtual force algorithm (IVFA), fuzzy redeployment algorithm (FRED), and two metaheuristics GA, and PSO. On the other hand, the proposed VF-based methods require much less time to solve the problem than GA and PSO metaheuristic methods.
Keywords: Maximal coverage, Sensor redeployment, Virtual Force Algorithm, Fuzzy system.