Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks
Kablosuz duygaç ağlarında ağ ömrünü en büyüklemek için eniyi yerleştirme, çizelgeleme ve rotalama
- Tez No: 270464
- Danışmanlar: DOÇ. NECATİ ARAS, PROF. İ. KUBAN ALTINEL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 194
Özet
Bu çalışmada bir duygaç ağında ağ ömrünün en büyüklenmesi problemi elealınmaktadır. En uygun duygaç ve merkez yerleri, duygaç çalışma çizelgeleri ve duygaçmerkezveri akış rotaları belirlenmektedir. Akış dengesi, duygaç batarya enerjisi vebütçe limiti problemin kısıtlarıdır. İlk önce problemin karma tamsayılı doğrusal programlamagösterimi verilmektedir. Daha sonra gösterim geçerli eşitsizliklerle kuvvetlendirilmekte ve problem için bir kesin, üç sezgisel yöntem önerilmektedir. Kesin çözümyöntemi dal-eder yaklaşımını kullanmaktadır. Birinci sezgisel yöntem bir Lagrangesezgiselidir. İkinci sezgisel yöntemde problemin bir yeni gösteriminin doğrusal programgevşetmesinin çözümünden bir uygun çözüm elde edilmektedir. üçüncü sezgiselyöntemde açgözlü ölçüler kullanılarak çabuk bir çözüm elde edilir. Yapılan bilgisayısaldeneyler önerilen çözüm yöntemlerinin hem etkinlik hem de doğruluk açısından çokbaşarılı olduklarını söylemektedir. Deneyler ayrıca rotalamayı göz önüne almayan birmatematik modelin ağ ömrü için yanlış değerlendirmelere neden olabileceğini göstermektedir.Bu çalışmada gerçel katsayılı küme kaplama çokyüzlüsü için geçerli eşitsizliklerde önerilmektedir. Yüzlem tanımlama ile ilgili bir yeterli koşul ile kaldırma kullanarakgeçerli eşitsizliği üreten yeni bir yöntem de geliştirilmektedir. Deneyler, önerilen geçerlieşitsizliklerin doğrusal programlama gevşetmesinin eniyi çözümünü kestiklerini ve eldeedilen alt sınırı önemli ölçüde iyileştirdiklerini göstermektedir. Bu çalışmada koşullualtgradyanı kullanan saptırılmış altgradyan yönteminin yakınsaması için yeni bir tanıtda verilmektedir.
Özet (Çeviri)
In this study we consider the problem of network lifetime maximization in awireless sensor network. We determine the optimal sensor and sink locations, sensoractivity schedules and sensor-to-sink data flow routes. Flow balance, sensor batteryenergy and budget limitation are the constraints of the problem. We first formulatea mixed integer linear programming formulation. We then strengthen the formulationwith valid inequalities. We propose exact and heuristic solution procedures for theproblem. The exact solution procedure is based on branch and price. The first heuristicmethod is a Lagrangean Heuristic. In the second heuristic method we construct afeasible solution from the Linear Programming relaxation solution of a reformulationof the problem. In the third heuristic method we obtain a feasible solution using greedycriteria. Experiments show that the proposed solution methods perform better thanthe commercial solver in giving a feasible solution and in finding a good quality upperbound. Experiments also show that a mathematical model that ignores the routingissue can give erroneous estimations for the network lifetime.In this study we also propose valid inequalities for the general set covering polytope.We define a sufficient condition for facet definition and we develop a new procedurethat generates the valid inequality using lifting. Experiments show that theproposed valid inequalities cut off the fractional optimum and improve considerablythe linear programming relaxation lower bound obtained. We also present a rigorousproof for the convergence of the deflected subgradient algorithm that uses the conditionalsubgradient.
Benzer Tezler
- Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks under connectivity restrictions
Kablosuz duygaç ağlarının ömrünü en büyüklemek için yerleştirme, çizelgeleme ve rotalama problemlerinin bağlılık kısıtları altında çözümü
BANU KABAKULAK
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. İ. KUBAN ALTINEL
- Controlled sink mobility and wireless sensor network lifetime maximization
Hareketli ana alıcılar ve kablosuz duygaç ağlarının ömrünün enbüyüklenmesi
MUHAMMED EMRE KESKİN
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL KUBAN ALTINEL
- Hücresel imalat sistemleri tasarımı ve uygulaması
Başlık çevirisi yok
ALAETTİN VARDAR
Yüksek Lisans
Türkçe
1993
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ. DR. MEHMET TANYAŞ
- Optimal routing in internet of things networks using artificial intelligence
Başlık çevirisi yok
TAHA HUSSEIN MERIE ALHASAN
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiBilişim Teknolojileri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ABDULLAHI ABDU IBRAHIM