Telsiz duyarga ağlarında etkin kod yayılımı
Efficient code distribution on wireless sensor networks
Yazar: MUSTAFA BÜLENT MUTLUOĞLU
Danışman: PROF. DR. OYA KALIPSIZ
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Teknolojideki hızlı gelişmeler sayesinde, boyutları çok küçük, algılama, işleme ve haberleşme yeteneklerine sahip aygıtların, bir arada işbirliği içinde çalışarak, fiziksel dünyayı gözleme imkânı sunacak şekilde bir ağ oluşturmaları mümkün olmuştur. ?Duyarga ağları? diye isimlendirilen bu ağlar, günümüzde bilgisayar dünyasının en hızlı gelişen ve en çok araştırma yapılan alanlarından biri haline gelmiştir. Bu ağların gelecekte, bugünkü kişisel bilgisayarlardan daha çok hayatımızın içine gireceği tahmin edilmektedir.Duyarga ağları, hedef ortama yerleştirildikten sonra, aygıtlara fiziksel olarak erişim pek çok durumda imkânsızdır. Bu yüzden, ağ üzerinde çalışan uygulamanın değiştirilmesi ihtiyacı doğarsa, bu işlem uzaktan yapılmalıdır. Duyarga ağlarının uzaktan programlanması anlamına gelen ?kod yayma? konusunda çok az çalışma yapılmıştır ve bu alan gelişmeye çok açıktır.Bu tezde, duyarga ağları için etkin bir kod yayımı algoritması geliştirilmiştir. Duyarga ağlarının programlanması için bugüne kadar geliştirilmiş olan bütün algoritmalar, sürekli çalışan mekanizmalara sahiptir. Yeni bir program yüklenmemiş kararlı durumda bulunan bir ağda bile, düğümler belirli aralıklarla çevrelerine, üzerlerindeki programın versiyonu hakkında mesajlar yaymaktadır. Bu, duyarga ağlarında sınırlı ve değerli olan enerjinin ve bant genişliğinin boşuna harcanması anlamına gelmektedir.Süreklilik sorununun çözümü için, bütün düğümlerin güncellenmesinden sonra, kod yayımını durduracak bir mekanizma geliştirilmiştir. Algoritmanın temeli, kod yayımından önce, programlanacak düğümler arasında, sezgisel bir ağaç topolojisi oluşturmaya dayanmaktadır. Yavru düğümlerinin hepsinin güncellendiğini gören düğümler, kod yayma işlemine son vermektedir. Böylece ağacın en altındaki düğümler de güncellenince, kod yayımı tamamen durmaktadır.Geliştirilen kod yayma algoritmasının en önemli özelliklerinden biri, topoloji-duyarlı bir algoritma olmasıdır. Verimi artırmak için, önce en uygun ağ yapısı belirlenmekte ve kod yayma işlemi bu yapı üzerinde çalışmaktadır. Bu yaklaşımın verimi artırdığı ve ağa gönderilebilecek program sayısını iyileştirdiği, matematiksel olarak ispatlanmıştır. En uygun ağ yapısının belirlenmesinde gerekli olan parametreler, bu matematiksel analizden elde edilmiştir.Ağaç altyapısının, ağ kopmalarına karşı dayanıklı olmak üzere tasarlanmış, yayın tabanlı ve sürekli olan algoritmalara göre, sistemin toplam performansını geliştirdiği gösterilmiştir. Değişik algoritmalarla karşılaştırmalı sonuçlar alınabilmesi için, simülasyonlar yapılmıştır. Bu simülasyon sonuçları, yaklaşımın, var olan sürekli algoritmalara göre, enerji ve güncelleme maliyeti açısından daha iyi bir performans yakaladığını göstermiştir; aynı zamanda, başarı oranları ve ağ kopmaları dayanıklılığı açısından da karşılaştırılabilir sonuçlar elde edilmiştir.

Abstract:
Recent advances in the technology have enabled networks consisting of small devices capable of sensing, processing and communicating; working in parallel and cooperatively to observe the physical world. These networks, named as ?sensor networks?, have brought out one of the most challenging field of todays computer science world. It is envisioned that, in the future, wireless sensor networks will be an integral part of our lives, more so than the present-day personal computers.Physically reaching the sensor devices after deployment is mostly inefficient. Hence, if it is needed to update the application running on the network, this must be done remotely. Today, there are not many algorithms designed for ?code propagation?, which stands for the remote programming of sensor networks, and this field is open to research.In this thesis, an efficient code propagation algorithm for sensor networks is developed. All of the algorithms that have been developed so far for the programing of sensor networks have mechanisms that run continuously. The nodes on the network send messages periodically, about the version of the program they have, even if the network is in the stable state where there is no new program loaded to the network. This means waste of the resources like energy and bandwith, which are already scarce and valuable on sensor networks.In order to solve the contunity problem, a mechanism which stops the propagation of the code totally, after all the nodes are updated is developed. The approach is based on the construction of a heuristically optimized tree among the nodes to be programmed prior to code distribution. Nodes detecting that all their children are updated, stop sending messages concerning code propagation. Hence, when all the leaf nodes are updated, the code propagation process is stopped totally.One of the main features of the algorithm developed is that it is a topology-sensitive algorithm. To increase the efficiency, first an optimum network structure is determined and the code propagation runs on this optimum structure. It is proved mathematically that this approach increases the efficiency and optimizes the number of programs that can be deployed on the network. The necessary parameters needed for the optimum network structure were obtained from this mathematical analysis.It has been shown that underlying tree infrastructure improves overall performance of the system in comparison to continuous and broadcast algorithms designed to be resistant to network losses. Simulations have been made to obtain comparable results with different algorithms. These simulation results revealed that this approach achieves better performance than currently available continuous algorithms in terms of energy and cost update time while retaining comparable success rates and network loss tolerance.