Improving network reliability by exploiting path diversity in ad hoc networks with bursty losses

Abstract

ÖZET Telsiz mobil tasarsız ağlarda, uçtan-uca bağlantılarda, bağlantıyı işlemez hale getirmeyen fakat iletişimi kısa süreler için durduran kesikli bozulmalar olur. Bu kesikli bozulmalar genellikle, ağ elemanlarının (host) devingenliğinden, telsiz ortamın dinamik yapısından ve enerji tasarruf stratejilerinden kaynaklanır ve çoğuşma biçiminde (bursty) paket yitimlerine neden olur. Bu tip bir ortamda güvenilir iletişimin önemi, tasarsız ağlarda ses, video, veri gibi çeşitli çoğul ortam uygulamalarının ortaya çıkması ile artmaktadır. Bu tezde, ağdaki yolların kesikli kullanılabilirliğini yansıtan yeni bir yol güvenilirlik (path reliability) modeli ortaya konulmuş ve bu model üzerine, ağ güvenilirliğini iyileştirmek için bir yönlendirme stratejisi geliştirilmiştir. Geliştirdiğimiz yönlendirme stratejisi ağdaki yol çeşitliliğinden yararlanır ve verimliliği artırmak üzere çeşitleme kodlaması (diversity coding) kullanılır. Çeşitleme kodlaması yönteminde, özgün bilgi bir (N,K) kodu ile kodlanmışsa, alıcının gönderilen N bitlik bilgiden herhangi K bitlik bilgiyi alması, özgün bilginin elde edilmesi için yeterlidir. Bizim yöntemimizde, özgün bilgi N tane pakete bölünür ve paketler ağda var olan ayrışık yollar arasında dağıtılır. Paketlerin hangi yollara ne kadar dağıtıldıkları çok önemlidir. Paketler, yollara özgün bilginin alıcıda başarılı bir şekilde yeniden elde edilme olasılığım en yüksek kerteye çıkaracak biçimde 'akıllıca' yapılmalıdır. Yolların bozulma olasılıkları ve kodlama oram verildiğinde, önerdiğimiz strateji, her bir yol için o yol üzerinden gönderilecek paket sayısını, özgün bilginin alıcıda başarılı bir biçimde yeniden elde edilme olasılığım en yüksek kerteye çıkaracak biçimde bulur. Benzetim sonuçlan, yaklaşımımızın doğruluğunu ve verimliliğini destekler biçimdedir. Ayrıca, benzetim sonuçlan çokyollu yönlerdime stratejimizin ağ güvenilirliğini, bir yollu yönlendirmeye göre yeterince çok iyileştirdiğini göstermiştir. Telsiz ağlarda, sıkça kullanılan bir yöntem, batarya ömürlerini uzatmak amacıyla, ağ düğümlerinin az enerji tüketilen uyku kipine geçirilmesidir. Bu çalışmada, ağ düğümlerinin kesikli yararlanırlıklarının uyku/uyanık (sleep/awake) çevrimlerinden kaynaklandığı durumları da göz önünde bulundurduk. Paket gecikmesini en aza indiren ve aynı zamanda enerji tasarruf dizgesi tarafından belirlenen enerji tasarruf oranım sağlayan bir uyku/uyanık zamanlama stratejisi önerilmiştir.

ABSTRACT In wireless mobile ad hoc networks, end-to-end connections are often subject to failures which do not make the connection non-operational indefinitely but interrupt the communication for intermittent short periods of time. These intermittent failures usually arise from the mobility of hosts, dynamics of the wireless medium or energy-saving mechanisms, and cause bursty packet losses. Reliable communication in this kind of an environment is becoming more important with the emerging use of ad hoc networks for carrying diverse multimedia applications such as voice, video and data. In this thesis, we present a new path reliability model that captures intermittent availability of the paths, and we devise a routing strategy based on our path reliability model in order to improve the network reliability. Our routing strategy takes the advantage of path diversity in the network and uses a diversity coding scheme in order not to compromise efficiency. In diversity coding scheme, if the original information is encoded by using a (N,K) code, then it is enough for the destination to receive any K bits correctly out of N bits to successfully decode the original information. In our scheme, the original information is divided into N subpackets and subpackets are distributed among the available disjoint paths in the network. The distribution of subpackets among the diverse paths is a crucial decision. The subpackets should be distributed 'intelligently' so that the probability of successful reconstruction of the original information is maximized. Given the failure statistics of the paths, and the code rate (N, K), our strategy determines the allocation of subpackets to each path in such a manner that the probability of reconstruction of the original information at the destination is maximized. Simulation results justify the accuracy and efficiency of our approach. Additionally, simulation results show that our multipath routing strategy improves the network reliability substantially compared to the single path routing. In wireless networks, a widely used strategy is to place the nodes into a low energy consuming sleep mode in order to prolong the battery life. In this study, we also consider the cases where the intermittent availability of the nodes is due to the sleep/awake cycles of wireless nodes. A sleep/awake scheduling strategy is proposed which minimizes the packet latency while satisfying the energy saving ratio specified by the energy saving mechanism. IV