Energy efficient broadcasting in wireless ad hoc networks

Abstract

Son yıllarda ¸cok sekmeli kablosuz ¸sebekeler sivil ve askeri alanlardaki ¸cok ¸ce¸sitlipotansiyel uygulamaları nedeniyle ¨onemli ¨ol¸c¨ude dikkat ¸cekmi¸stir. Bu t¨ur ¸sebekeleri¸cin ¸co˘ga g¨onderim temel bir veri da˘gıtım y¨ontemidir. ˙Iletim g¨u¸c kontrol¨un¨un kablosuztasarsız a˘glar i¸cin ¸cok ¨onemli bir konudur ve hala tatmin edici ¸c¨oz¨umlerin bulunmamaktadır.Kablosuz a˘g olu¸sturma ortamı ¸co˘ga g¨onderim problemleri i¸cin zorlu biralandır. ¨ Ozellikle kablosuz ortam ¨ozellikleri ve pille ¸calı¸san ara¸cların bulunması kablosuz¸sebekelerde kısıtlı olan enerji kaynaklarının makul kullanılmasını ama¸clayan yenimodelleme yakla¸sımları ve algoritmik yakla¸sımlar gerektirmektedir. Buna ek olarak,¸sebekelerin kaynaktan hedef cihazlara kadar olan her iletim yolu ¨uzerinde ileti gecikmesiile ilgili olarak belli bir servis kalitesi garantisi sunması gerekmektedir. Dahası, her alıcıcihazda algılanan sinyalin ba¸sarılı bir ¸sekilde ¸c¨oz¨ulebilmesi i¸cin sinyalin yeteri kadarg¨u¸cl¨u olması gerekmektedir. Bu sebeble, bu ¸calı¸smada ¸cok sekmeli kablosuz a˘glardaen az enerjili ¸co˘ga g¨onderim problemini iki farklı kısıt do˘grultusunda incelemekteyiz:(i) her cihaz ¸co˘ga g¨onderim mesajını belli bir gecikme sınırı olan i¸cerisinde almalıdır,ve (ii) alınan sinyalin i¸saret-parazit-artı-g¨ur¨ult¨u-oranı (SINR) e¸sik de˘ger 'nın¨uzerinde olmalıdır ki sinyal ba¸sarı ile ¸c¨oz¨ulebilsin. Bu nedenle, sırasıyla kısıt (i) ve(ii) do˘grultusunda en az enerjili ¸co˘ga g¨onderim a˘gacı olu¸sturacak DTE ve SINR-BIPadlarında iki farklı algoritma ¨onermekteyiz. DTE minimum ¨orten a˘ga¸c algoritmasınında˘gıtık uygulanmasını baz almaktadır. Her yinelemede, gecikme sınırı kısıtını ihlaletmeden en az enerji artı¸sı gerektiren ve mevcut durumda ula¸sılamamı¸s d¨u˘g¨umlerdenen fazlasına ula¸sabilen d¨u˘g¨um e˘gaca eklenerek ¸co˘ga g¨onderim a˘gacı b¨uy¨ur. SINR-BIPalgoritmasında ise alınan sinyallerin SINR de˘gerleri g¨oz ¨on¨unde bulundurularak iyibilinen ¸co˘ga g¨onderim g¨u¸c-artı¸sı (BIP) algoritmasındaki ana fikre benzer bir yakla¸sımuygulanmı¸stır. Buna ek olarak, algoritmanın miyop etkisini azaltmak i¸cin SINR-BIP'ini¸cine g¨om¨ul¨u olarak bir budama yordamı kullanılmı¸stır. C¸ o˘ga g¨onderim a˘gacı heryinelemede b¨uy¨ud¨u˘g¨u i¸cin her iki algoritma da do˘gası gere˘gi yapıcı algoritmalardır.DTE'nin mevcut algoritmalardan daha iyi performans g¨osterdi˘gini ve DTE ile eldeedilen ¸co˘ga g¨onderim a˘gacının toplam enerji t¨uketiminin Tamsayı Programlama ileelde edilene %20 oranında yakın oldu˘gu g¨ozlenmektedir.

In recent years wireless multi-hop networks have attracted significant attention dueto their wide range of potential civil and military applications. Broadcasting is a fundamentaldata dissemination scheme for these networks. The transmission power controlis an important issue in wireless ad hoc networks and still has no satisfactory solutionmethods. The wireless networking environment presents formidable challenges to thestudy of broadcasting problems. In particular, the properties of the wireless mediumand the presence of battery-powered devices require novel modeling and algorithmicapproaches concentrating on judicious use of limited energy resources in wireless networks.In addition, networks are often required to provide certain quality of service(QoS) guarantees in terms of the end-to-end delay along the individual paths from thesource to each of the destination nodes. Moreover, the received signal at each receivingnode must be strong enough to be successfully decoded. In this study we addressthe minimum-energy broadcast problem in multi-hop wireless networks with respect totwo different constraints: (i) each node must receive broadcast message within a givendelay bound , and (ii) signal-to-interference-plus-noise ratio (SINR) of the receivedsignal must be above a given threshold so that the received signal can be successfullydecoded at the receiving node. We propose two distinct algorithms Distributed TreeExpansion (DTE) and SINR-BIP which aim to generate minimum power broadcasttree with respect to constraint (i) and (ii), respectively and exclusively. DTE is basedon an implementation of a distributed minimum spanning tree algorithm in which thetree grows at each iteration by adding a node that can cover the maximum numberof currently uncovered nodes in the network with minimum incremental transmissionpower and without violating the delay constraint. In SINR-BIP, we apply the similaridea of well-known Broadcast Incremental Power (BIP) algorithm while considering theSINR values of received powers. In addition, we use an embedded pruning procedurein SINR-BIP, so that the myopic effect of the algorithm is mitigated. Both the algorithmsDTE and SINR-BIP are constructive in nature since the broadcast tree growsat each iteration. We observed that the DTE outperforms the existing algorithms andthe total energy consumptions of the generated broadcast trees by DTE is within 20%percent of the solutions obtained by Integer Programming.