Kablosuz algılayıcı ağlarda en düşük ağırlıklı röle düğümlerinin yerleştirilmesi
Minimum weighted relay node placement for wireless sensor networks
- Tez No: 335002
- Danışmanlar: YRD. DOÇ. DR. İLKER BEKMEZCİ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Kablosuz ağlar, Sensörler, Wireless networks, Sensors
- Yıl: 2012
- Dil: Türkçe
- Üniversite: Hava Harp Okulu Komutanlığı
- Enstitü: Havacılık ve Uzay Teknolojileri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Yazılım Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Kablosuz Algılayıcı Ağlar (KAA), mikro-elektro-mekanik sistemlerinin hızla ilerlemesi sonucu ortaya çıkan düşük maliyetli, düşük seviyede enerji tüketen, fiziksel olarak küçük, çok fonksiyonlu algılayıcı düğümlerden oluşan bir ağdır. Algılayıcı düğümler tarafından, ihtiyaç durumuna göre hesaplama işlemi de enerji, maliyet gibi kısıtlar göz önüne alınarak kendi üzerlerinde gerçekleştirebilir. Birbirleri arası haberleşme ise sınırlı mesafesi olan radyo frekansı (RF) veya bluetooth protokolü aracılığı ile yapılır. Üzerinde algılayıcı bulunan bu düğümler, algılanılması istenen ortama planlı veya plansız (rasgele) olarak bırakılabilirler. Bırakılma öncesi ve esnası yapılan çalışmalar, bırakılma sonrası düğümler arası kurulacak haberleşmede önemli rol oynamaktadır.Bu haberleşmeyi sağlayacak ağ omurgasının (backbone) oluşturulma yöntemlerinden biri Röle Düğüm kullanımıdır. Röle düğümleri sıradan algılayıcı düğümler arasından seçilebileceği gibi, onlardan daha fazla enerjiye sahip, maliyeti yüksek, tek görevi algılayıcı düğümler ile Baz İstasyonu (Bİ) arası iletişimi sağlayacak düğümler de olabilirler. Röle Düğümü Yerleştirme Problemi (RDYP), en az sayıda RD kullanarak kapsama alanı (coverage), enerji (power), bağlılık (connectivity), maliyet (cost) gibi sorunları amaç fonksiyonunu en iyileyecek şekilde çözmeye çalışır. Buradan anlaşılacağı üzere, RDYP aslında algılayıcı düğümler arasında Steiner ağacı oluşturulması esnasında kullanılması gereken RDlerin sayısını bulmaya yöneliktir. RDYP, NP-zor problem sınıfına girmektedir. Dolayısıyla bulunan çözümler çokterimli (polinomial) zamanda ve belirli bir yakınsama oranına (approximation ratio) sahip olmaktadır.Bu tezde, röle düğümü yerleştirme problemi için, yukarıda belirtilen kriterlerden farklı olarak, aday noktaların sahip olduğunu varsaydığımız ağırlık değerlerine göre RD yerleştirilmesini en iyileyen optimal ve sezgisel olmak üzere iki çözüm üzerinde çalışılmıştır. Ağırlık sadece maliyet olarak değil, aynı zamanda aday noktaya RD yerleştirmenin zorluğu, güvenlik gereksinimleri, bölgeye ulaşma güçlüğü gibi durumları da yansıtabilir. Bir arazi ve yapılandırma için bulunan tek bir ağırlık değeri yerine, bu değere öngörülemeyen sebeplerden dolayı eklenen ağırlık ile ağırlık eklenmiş halinin karesinin alındığı üç durum üzerinde çalışılmıştır.Ağırlık yönünden, sabit arazi boyutlu-artan RD yoğunluklu durumda, sezgisel algoritma optimale yakın sonuçlar vermiştir. Bunun yanında rasgele RD dağılımı yapıldığında, planlı olandan %30a yakın fazla ağırlık çıkmıştır.Ağırlıklar toplamı bakımından incelendiğinde, planlı dağılımda plansıza göre daha az ağırlık çıkmasına rağmen daha fazla RD kullanıldığının gözlemlenmesidir. Ayrıca, üç farklı ağırlık değerlerinin kullanıldığı aynı yapılandırmaya sahip arazilerde farklı sayıda/konumdaki RDlerin kullanıldığı da gözlemlenmiştir. Dolayısıyla ağırlıkların eşit şekilde değişime uğraması, oluşturulan ağacın yapısını beklenenin aksine değiştirmektedir.Sonuç olarak, KAA'larda enerji, hayatta kalma, bağlanırlık, kapsama alanı maksimizasyonunda çözüm olarak başvurulan röle düğümü kullanımı, beraberinde bir optimizasyon problemini de getirmektedir. Bugüne kadar yapılan çalışmalar, amaç fonksiyonu olarak yukarıda belirtilen kısıtlar altında en az sayıda RD kullanmayı hedeflerken, yaptığımız bu çalışma ile ağırlık faktörünün hesaba katıldığı ve sonuçlarının en az sayıda RD kullanma ile hem zaman hem de sayı olarak farklılık gösterdiği sonuca ulaştık. Kullandığımız sezgisel yöntem zaman ve yakınsama derecesi olarak kabul edilebilir sınırlar içerisindedir.
Özet (Çeviri)
Wireless sensor network (WSN), with the help of rapid improvement in MEMS (micro electro mechanic systems), is a network that consists low-cost, less energy consuming, physically small, multi-functional sensor nodes. Depending on the constrains like energy, and cost, Sensor nodes also execute computing process on their own. Communication between these nodes is established by radio frequency (RF) or Bluetooth protocol which has rather a limited range. Nodes having sensors are deployed into to the medium to sense the sound, light, temperature etc. in a planned way or randomly. The planning that takes place pre-deployment and during deploying plays an important role in the communication that will be settled after the deployment between nodes.One of the methods to constitute the network backbone that will enable this communication is using Relay nodes (RN). Relay nodes can also be selected among regular sensor nodes or have only relaying mission with more power and cost between sensor nodes and base too. Relay Node Placement Problem (RNP) tries solving the optimization of an object function to maintain coverage/connectivity, consume less power, and be cost-effective by using minimum number of RNs. As can be seen here, the intention of RNP is to find the necessary number and locations of RNs to form the Steiner Tree subject to the purpose. Concurrently, RNP is an NP-complete problem. Thus, the duration of the solution and result will have polynomial time and approximation ratio, respectively.In this thesis, apart from the criteria above, two solution methods including optimal and heuristics are studied according to the weight values which supposedly belong to the candidate points of RNs. Weight might be defined not only as cost but also as difficulty of placing an RN, keeping RNs safe and secure, challenge for reaching that candidate point, and so on. Instead of a single weight for each field and node configuration, two more variations like adding a secondary weight due to unforeseen reasons and square of the added weight are studied.From the standpoint of weight, in constant field size-increasing RN density configuration, heuristic method yielded proximate results when compared with optimal. Furthermore, the results were same when the RN density to a certain value. Besides, deploying RNs randomly yielded with a weight approximately %30 percent high when compared with the planned one.With respect to sum of RN density, despite deploying the RNs randomly with a higher weight than planned one, random replacement facilitates less number of RNs. And what is more, assigning three different weight sets for the same field size and node density led to utilize different sets of RNs. Thus, altering the weight sets equally affects the form of the Steiner tree in the same configuration.To sum up, the heuristics method combined with a criterion of weight set brought a new scope for RNP, which also introduced striking results.
Benzer Tezler
- Design and construction of an automatic transceiver test system on a UNIX based multiuser computer
Başlık çevirisi yok
YAVUZ ÖZEREN
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiY.DOÇ.DR. M. METE BULUT
- Microcontroller controlled radio
Başlık çevirisi yok
LEVENT TAŞKIN
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiDOÇ.DR. AVNİ MORGÜL
- Switching transients in power systems
Başlık çevirisi yok
MEHMET TUMAY
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiGaziantep ÜniversitesiDOÇ.DR. UĞUR ÜNVER
- Analysis of lightning overvoltages in power systems
Enerji sistemlerinde meydana gelen yıldırım aşırı gerilimlerinin etüdü
ERGUN ERÇELEBİ
Yüksek Lisans
İngilizce
1992
Elektrik ve Elektronik MühendisliğiGaziantep ÜniversitesiDOÇ. DR. M. UĞUR ÜNVER
- Karayollarında kullanılan öngerlmeli beton kirişlerin optimum boyutlandırılması
The Optimum design of prestressed forced concrete higway bridge beams
İHSAN GÜZEL
Yüksek Lisans
Türkçe
1992
İnşaat MühendisliğiFırat Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ SAYIL ERDOĞAN