Kablosuz algılayıcı ağlarda mobil sensör ile kapsama deliği optimizasyonu / Cansu Cav ; thesis advisor Ayşegül Altın Kayhan.
Material type:
- text
- unmediated
- volume
- Coverage hole optımızatıon wıth a mobıle sensor ın wıreless sensor networks [Parallel title]
Item type | Current library | Home library | Collection | Call number | Copy number | Status | Date due | Barcode | |
---|---|---|---|---|---|---|---|---|---|
![]() |
Merkez Kütüphane Tez Koleksiyonu / Thesis Collection | Merkez Kütüphane | Tezler | TEZ TOBB FBE END YL’20 CAV (Browse shelf(Opens below)) | 1 | Ödünç Verilemez-Tez / Not For Loan-Thesis | TZ01242 |
Tez (Yüksek Lisans Tezi)--TOBB ETÜ Fen Bilimleri Enstitüsü Ağustos 2020
Kablosuz Algılayıcı Ağlar için birçok farklı uygulama alanı bulunmaktadır. Savaş alanı gözetimi, acil kurtarma ve hedef tespiti gibi bazı alanlarda hedef bölgenin ağı oluşturan sensörler tarafından izlenmesi veri güvenilirliği ve olay tespiti bakımından büyük önem taşımaktadır. Ancak sensörlerin hedef alandaki engellere takılmalarından, işlevselliklerini kaybetmelerinden veya düzensiz bir şekilde dağıtılmış olmalarından kaynaklanan birçok farklı sebepten dolayı hedef alan tam olarak kapsanamamakta ve dolayısıyla da kapsama delikleri oluşmaktadır. Bu çalışmada belirli bir alana rastgele yerleştirilmiş statik sensörlerin tam alan kapsamasını sağlayamadığı durumlarda meydana gelen kapsama deliklerinin mobil sensör yardımıyla bertaraf edilmesi amaçlanmıştır. Literatürde Kablosuz Algılayıcı Ağ optimizasyonu başlığı altında yer alan kapsama probleminin çözümüne yönelik matematiksel model tabanlı yaklaşımlarda eksiklik olduğu gözlemlenmiştir. Bu sebeple belirtilen problemin amacına yönelik olarak, mobil sensörün izleyeceği en kısa güzergahın matematiksel modelleme ile hesaplanması hedeflenmiştir. Önerilen model Ana Dağıtım Üssü Yer Seçimi ve Gezgin Satıcı problemlerinden esinlenilerek geliştirilmiştir. Sunulan matematiksel model kendi içinde aynı anda iki alt problemi ele almaktadır. Bunlardan ilki her bir kapsama deliğinin mobil sensörün dolaşması planlanan rotanın en az bir durağında kapsanması, ikincisi ise bu duraklardan oluşturulan rotanın toplam mesafesinin en küçüklenmesidir. Mobil sensörün her bir durağı bir kümebaşını temsil etmektedir ve bu kümebaşlarının seçim için Ana Dağıtım Üssü Yer Seçimi Probleminden, güzergah uzunluğunun en küçüklenmesi için ise Gezgin Satıcı Probleminden faydalanılmıştır. Bu iki problemin harmanlanmasıyla oluşturulan matematiksel modelin Cplex OPL ile çözdürülmesi sonucu, veri kümesi büyüdükçe optimal sonuçların elde edilemediği gözlemlenmiştir. Süre kısıtlaması altında elde edilen çözümlerin de optimal çözümlerle arasındaki açıklık değerlerinin büyük olduğu saptanmıştır. Bu sebeple modelin olası çözüm kümesini daraltan yeni bir model ve probleme daha sıkı üst sınırlar getirebileceği düşünülen iki aşamalı bir matematiksel model ele alınmıştır. Sonrasında ise geliştirilen sezgisel yöntemlerle kısa zamanda çözüm kalitesi yüksek sonuçlar elde edilmesi hedeflenmiştir. Bu doğrultuda iki versiyonu bulunan sezgisel bir algoritma ve bu sezgisel algoritma ile matematiksel modelin harmanlandığı hibrit bir yöntem kullanılarak çözüm süresi ve çözüm kalitesi ödünleşimi sağlanmaya çalışılmıştır. Hibrit algoritma, geliştirilen diğer yöntemlerle karşılaştırılmış, sonuçlar hem süre hem de çözüm kalitesi bakımından değerlendirilmiştir. Kıyaslamalar yapılırken hem elde edilen üst sınır değerleri hem de orijinal model sonuçları göz önünde bulundurulmuştur. Bu veriler ışığında, hibrit yöntemin iki performans ölçütü bazında da iyi çözümler verdiği sonucuna varılmıştır.
Wireless Sensor Networks have many different application areas. In some areas such as battlefield surveillance, emergency rescue, and target detection, monitoring the target area with sensors that compose the network is of great importance for data reliability and event detection. However, due to many different reasons such as obstacles in the target area, loss of functionality, or uneven distribution of sensors, the target area cannot be fully covered, and therefore coverage holes emerge. In this study, the motivation is to eliminate coverage holes which occur when randomly deployed static sensors in Wireless Sensor Networks cannot cover the entire target region using a mobile sensor. After a thorough literature review of Wireless Sensor Network optimization, it has been observed that there is a lack of mathematical model-based approaches for the coverage problem. Therefore, for the specified problem, we propose a mathematical model so as to find the shortest path to be followed by the mobile sensor. The proposed model includes variables and constraints similar to those in the Hub Location and Traveling Salesman problems. Two decisions are handled simultaneously in the model. The first is to determine the stops in the mobile sensor's path so that each coverage hole is within the sensing range of the mobile sensor in at least one of these stops, i.e, to ensure full coverage when the mobile sensor completes its tour. Moreover, the second is to find the shortest one of such tours. Each stop of the mobile sensor represents a cluster-head, and the Hub Location constraints are used to determine these cluster-heads whereas the Traveling Salesman Problem constraints are included to minimize the total distance. It gets quite difficult to solve the resulting model to optimality even for medium sized instances using commercial solvers. Moreover, the optimality gaps are large for the best solutions obtained at the end of the specified time limit. To this end, a new model with a restriction on the set of possible cluster head locations and a two-phase mathematical model are introduced so as to get better solutions. Consequently heuristic methods are discussed in order to obtain good solutions in a short time. Accordingly, in addition to a heuristic algorithm with two versions, a hybrid method in which the mathematical modeling is used in accordance with heuristic algorithms is used to balance the trade-off between solution time and quality. Test results show that the hybrid method is quite effective in terms of solution time and quality.
There are no comments on this title.