بهینه سازی جایابی شبکه های سنسور بی سیم با استفاده از الگوریتم های بهینه سازی سراسری و مدل سنجش احتمالی

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

نویسندگان

1 استادیار گروه سنجش از دور و GIS - دانشکده جغرافیا، دانشگاه تهران

2 استادیار دانشکده مهندسی نقشه برداری و اطلاعات مکانی، پردیس دانشکده های فنی دانشگاه تهران

3 دانشجوی کارشناسی ارشد سیستم‌های اطلاعات مکانی - دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته کرمان

10.22131/sepehr.2018.31468

چکیده

در سال های اخیر، شبکه­ های حسگر بیسیم[1] در کاربردهای متعددی مورد مطالعه قرار گرفته ­اند. یکی از مسائل مهم مورد مطالعه در این شبکه­ ها، جایابی[2]  بهینه حسگرها به منظور دستیابی به بیشینه­ ی مقدار پوشش[3]  است. از این رو، در اکثر تحقیقات برای رسیدن به پوشش حداکثر از الگوریتم­ های بهینه­ سازی استفاده شده است. در یک رده­ بندی کلی، الگوریتم­ های بهینه­ سازی برای جایابی بهینه حسگر با هدف افزایش پوشش، به دو گروه الگوریتم­ های بهینه­ سازی محلی و سراسری تقسیم می­ شوند. الگوریتم­ های سراسری عموماً از یک روش تصادفی بر اساس یک روند تکاملی استفاده می کنند. در اغلب تحقیقات انجام شده، مدل محیط و بعضاً چیدمان حسگرها در شبکه به صورت کاملاً ساده­ سازی شده در نظر گرفته شده­ اند. در این تحقیق با مدلسازی رستری و برداری محیط در فضاهای دو و سه بعدی، عملکرد الگوریتم­ های بهینه­ سازی سراسری به منظور جانمایی بهینه حسگرها، ارزیابی و مقایسه شده اند و مدل محیط برداری به عنوان مدل دقیق تر استفاده می­ شود.
از آنجایی که هدف مقایسه عملکرد و نتایج الگوریتمهای سراسری بوده است، منطقه مورد مطالعه و شرایط پیادهسازی یکسان فرض شدهاند. در این مقاله، چند روش بهینهسازی برای جایابی سنسور، از جمله الگوریتمهای ژنتیک، L-BFGS، VFCPSO و CMA-ES ،پیادهسازی و معیار ارزیابی الگوریتمها برای مسئله جایابی شبکههای حسگر بیسیم، مقدار پوشش بهینه، دقت پوشش آنها نسبت به مدل محیط و سرعت همگرایی الگوریتمها در نظر گرفته شده است.از سوی دیگر، در این تحقیق مدل احتمالی پوشش[4]  برای هر یک از الگوریتمهای بهینهسازی سراسری پیادهسازی شدند. نتایج این پیادهسازیها نشان میدهد که وجود پارامترهای پیچیدهتر در مدل محیط و پوشش، نتایج دقیقتر و منطبقتری با واقعیت را ارائه میکند. با این حال ممکن است کارایی زمانی الگوریتمها را کاهش دهد.



[1]4- Wireless Sensor Networks


[2]5-Deployment


[3]6- Coverage


[4]7- Probablity coverage model

کلیدواژه‌ها


عنوان مقاله [English]

Optimized placement of wireless sensor networks using global optimization algorithms and probabilistic model

نویسندگان [English]

  • Meysam Argany 1
  • Farid Karimipour 2
  • Fatemeh Mafi 3
1 Assistant Professor of Remote Sensing and GIS, University of Tehran
2 Assistant Professor of Engineering Department Surveying and Spatial Information Sciences, University of Tehran
3 Graduate student of Geographic information systems, Kerman Graduate University of Advanced Technology
چکیده [English]

Extended Abstract                                                                             
Introduction
Wireless Sensor Networks (WSNs) are widely used for monitoring and observation of dynamic phenomena. A sensor in WSNs covers only a limited region, depending on its sensing and communicating ranges, as well as the environment configuration. For efficient deployment of sensors in a WSN, the coverage estimation is a critical issue. Probabilistic methods are among the most accurate models proposed for sensor coverage estimation. However, most of these methods are based on raster representation of the environment for coverage estimation which limits their quality. In this paper, we propose a probabilistic method for estimation of the coverage of a sensor network based on raster models, and 3D vector representation of the environment. Then, the performance of global approaches are evaluated, and the 3D vector model is used as an appropriate model.
 
Materials and Methods
Recent advances in electro mechanical and communication technologies have resulted in the development of more efficient, low cost and multi-function sensors. These tiny and ingenious devices are usually deployed in a wireless network to monitor and collect physical and environmental information such as motion, temperature, humidity, pollutants, traffic flow, etc. The information is then communicated to a process center where they are integrated and analyzed for different application. Deploying sensor networks allows inaccessible areas to be covered by minimizing the sensing costs compared to the use of separate sensors to completely cover the same area. Sensors may be spread with various densities depending on the area of application and details and quality of the information required. Despite the advances in sensor network technology, the efficiency of a sensor network for collection and communication of the information may be constrained by the limitations of sensors deployed in the network nodes. These restrictions may include sensing range, battery power, connection ability, memory, and limited computation capabilities. These limitations have been addressed by many researchers in recent years from various disciplines in order to design and deploy more efficient sensor networks.
Efficient sensor network deployment is one of the most important issues in sensor network filed that affects the coverage and communication between sensors in the network. Nodes use their sensing modules to detect events occurring in the region of interest. Each sensor is assumed to have a sensing range, which may be constrained by the phenomenon being sensed and the environment conditions. Hence, obstacles and environmental conditions affect network coverage and may result in holes in the sensing area. Communication between nodes is also important. Information collected from the region should be transferred to a processing center, directly or via its adjacent sensor. In the latter case, each sensor needs to be aware of the position of other adjacent sensors in their proximity.
In recent years, Wireless Sensor Networks (WSN) has been studied in several applications such as monitoring and control different criteria from smart cities and intelligent transportation to land use planning and environmental monitoring. Sensor deployment for achieving the maximum coverage is one of the important issues in WSN. Hence, several optimization algorithms to achieve maximum coverage are used in the majority of researches.
 
Discussion and Results
In a general classification, optimization algorithms for the sensor deployment with the aim of increasing coverage, are divided into local and global optimization algorithms. The feature of global algorithms is their randomness based on an evolutionary process. In all of these algorithms, the calculation of the sensor network coverage is essential as a target function. In fact, coverage improvement is done according to the coverage calculation method. In the previous researches, a simple model was considered as the environmental model for network sensors. In this research, raster and vector modeling in 2 and 3-dimensional spaces and the optimization algorithms of global performance for optimizing the sensor layouts were compared evaluated. errorIn this study, two-dimensional and three-dimensional vector models were used as a precise environmental model. Most of the models in the previous studies considered the coverage to be binary (i.e. a point is covered by a sensor or not). For realistic modeling, this study considers the coverage as an issue, which means that the amount of coverage obtained based on parameters such as distance and angle of the sensor is expressed as a percentage between zero and one hundred. errorIn fact, all sensors are not sensed in the same way and will vary according to their various parameters. Since the purpose of this study is to compare the performance and ability of global optimization algorithms, it is therefore assumed that the study area has equal conditions. In this paper, several optimization methods such as genetic algorithms, L-BFGS, VFCPSO and CMA-ES have been implemented to optimize the location of sensors. In this study, various sensor sensing types such as omnidirectional binary sensing model, directional sensing model and probabilistic sensing model have been used and tested for the aforementioned optimization algorithms in different Raster and Vector study areas.
 
Conclusion
This paper was focused on comparing the performance of four global optimization algorithms to optimize deployment of sensors in environment using more spatial details compared to previous approaches. The innovation of this study was to use 3D raster and vector data and to implement the global optimization methods using probabilistic sensing model to optimize sensor network placement. Finally, promising results have been presented and discussed and future methods were introduced.
 
 
 
 

کلیدواژه‌ها [English]

  • WSN
  • Deployment
  • Coverage
  • Global Optimization
  • Probabilistic Coverage Model
  • Raster Model
  • Vector Model

1 . A. Efrat, S. Har-Peled, J.S.B. Mitchell” ,Approximation algorithms for two optimal location problems in sensor networks _ pin Proc. of the 3rd International Conference onBroadband Communications Networks and Systems (Broadnets , (05‘Boston, Massachusetts,, .2005.

2  . Afghantoloee A, Doodman S, Karimipour F, Mostafavi MA. Coverage Estimation of GeoSensors in 3D Vector Environments. submitted to the GIResearch Conference 2014.

3 . Akbarzadeh, V. et al.Probabilistic Sensing Model for Sensor Placement Optimization based on Line-of-sight Coverage. IEEE Transactions on Instrumentation and Measurement, 2013. 62: p. 293-303.

4 . Akbarzadeh, v. et al.Black-box Optimization of Sensor Placement with Elevation Maps and Probabilistic Sensing Models, in International Symposium on Robotic and Sensors Environment, ROSE2011. p. 89-94.

5 . Argany, M. et al.A GIS Based Wireless Sensor Network Coverage Estimation and Optimization: A Voronoi Approach. A Voronoi Approach. Transacton on Computational Sciences Journal, 2011. 14: p. 151-172.

6.  Argany, M. et al.Impact of the quality of spatial 3D city models on sensor networks placement optimization. GEOMATICA, 2012. 66: p. 291—305.

7 . Argany, M., Mostafavi, M.A.,Gagné, C.,  Context-Aware Local Optimization of Sensor Network Deployment. Journal of Sensor and Actuator Networks (JSAN), 4, 160-188, 2015.

8 . Biljecki, F., H. Ledoux, and J. Stoter, Error propagation in the computation of volumes in 3D city models with the Monte Carlo method, in ISPRS/IGU Joint International Conference on Geospatial Theory, Processing, Modelling and Applications2014: Toronto, Canada.

9. Chen, X., et al., Sensor network security: a survey. Communications Surveys & Tutorials, IEEE, 2009. 11(2): p. 5273.

10 . Cortés, J. and S. Martínez, T Karatas, F Bullo. (2004), Coverage Control for Mobile Sensing Networks. IEEE Transaction on Robotics and Automation. 20: P.243-255.

11.  Foley, J.D. and A. Van Dam, Fundamentals of interactive computer graphics. Vol. 2. 1982: Addison-Wesley Reading, MA.

12 . Guvensan, M. A. and A. Gokhan Yavuz. (2011), On coverage issues in directional sensor networks: A survey. Ad Hoc Networks. 9: P.1238-1255.

13.  Hoiem, D. A.A. Efros, and M. Hebert, Putting objects in perspective. International Journal of Computer Vision, 2008. 80(1): p. 3-15.

14.  Hossain, A. and P. K. Biswas, S. Chakrabarti. (2008), Sensing models and its impact on network coverage in wireless sensor network. Proceedings of the 10th Colloquium and the 3rd ICIIS, IEEE. P.1-5.

15 . Howard, A. M.J. Matarić, and G.S. Sukhatme, Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem, in Distributed autonomous robotic systems 52002, Springer. p. 299-308.

16.  Jourdan, D. and O.L. de Weck. Layout optimization for a wireless sensor network using a multi-objective genetic algorithm. in Vehicular Technology Conference, 2004. VTC 2004-Spring. 2004 IEEE 59th. 2004. IEEE.

17 . Leonov, M.Polyboolean library. Polyboolean library, 2004.

18.  Locatelli, M. and U. Raber, Packing equal circles in a square: a deterministic global optimization approach. Discrete Applied Mathematics, 2002. 122(1): p. 139-166.

19 . Nocedal, J., Updating quasi-Newton matrices with limited storage. Mathematics of computation, 1980. 35(151): p. 773-782.

20 . Potter, M.A. and K.A. De Jong, A cooperative coevolutionary approach to function optimization, in Parallel Problem Solving from Nature—PPSN III1994, Springer. p. 249-257.

21 . Seixas, R., M. Mediano, and M. Gattass, 2005. Efficient line-of-sight algorithms for real terrain data.III.

22 . Simpósio de Pesquisa Operacional e IV Simpósio de Logística da Marinha–SPOLM 1999, 1999

Akyildiz, I.F., et al., A survey on sensor networks. Communications magazine, IEEE, 2002. 40(8): p. 102-114.

23.  Vahab Akbarzadeh, et al.Topography-Aware Sensor Deployment Optimization with CMA-ES. Parallel Problem Solving from Nature, PPSN XI, 2010.

24.  Van den Bergh, F. and A.P. Engelbrecht, A cooperative approach to particle swarm optimization. Evolutionary Computation, IEEE Transactions on, 2004. 8(3): p. 225-239.

25 . Wang, G. and G. Cao, T. L. Porta. (2004), Movement-assisted sensor deployment. IEEE Infocom (INFOCOM‘04). 5: P.640-652.

26 . Wang, Y. and G. Cao. (2011), On full-view coverage in camera sensor networks. Proceedings of INFOCOM 2011, IEEE. P.1781-1789.

27 . Werner-Allen, G. et al. Monitoring volcanic eruptions with a wireless sensor network. in Wireless Sensor Networks, 2005. Proceeedings of the Second European Workshop on. 2005. IEEE.

28 . Wright, S. and J. Nocedal, Numerical optimization. Vol. 2. 1999: Springer New York.

29 . Zhang, J. and V. Varadharajan, Wireless sensor network key management survey and taxonomy. Journal of Network and Computer Applications, 2010. 33(2): p. 63-75.

30 . Zou, Y. and K. Chakrabarty. Sensor deployment and target localization based on virtual forces. in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. 2003. IEEE.