Energy efficient broadcasting in wireless ad hoc networks /
Yazar: SERKAN ÇİFTLİKLİ
Danışman: YRD. DOÇ. DR. KEREM BÜLBÜL ; YRD. DOÇ. DR. ÖZGÜR ERÇETİN
Sabancı Üniversitesi / Fen Bilimleri Enstitüsü
Derece: Yüksek Lisans, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Son yıllarda ¸cok sekmeli kablosuz ¸sebekeler sivil ve askeri alanlardaki ¸cok ¸ce¸sitli
potansiyel uygulamaları nedeniyle ¨onemli ¨ol¸c¨ude dikkat ¸cekmi¸stir. Bu t¨ur ¸sebekeler
i¸cin ¸co˘ga g¨onderim temel bir veri da˘gıtım y¨ontemidir. ˙Iletim g¨u¸c kontrol¨un¨un kablosuz
tasarsı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 bir
alandı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 yeni
modelleme yakla¸sımları ve algoritmik yakla¸sımlar gerektirmektedir. Buna ek olarak,
¸sebekelerin kaynaktan hedef cihazlara kadar olan her iletim yolu ¨uzerinde ileti gecikmesi
ile 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 kadar
g¨u¸cl¨u olması gerekmektedir. Bu sebeble, bu ¸calı¸smada ¸cok sekmeli kablosuz a˘glarda
en 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-BIP
adlarında iki farklı algoritma ¨onermekteyiz. DTE minimum ¨orten a˘ga¸c algoritmasının
da˘gıtık uygulanmasını baz almaktadır. Her yinelemede, gecikme sınırı kısıtını ihlal
etmeden en az enerji artı¸sı gerektiren ve mevcut durumda ula¸sılamamı¸s d¨u˘g¨umlerden
en fazlasına ula¸sabilen d¨u˘g¨um e˘gaca eklenerek ¸co˘ga g¨onderim a˘gacı b¨uy¨ur. SINR-BIP
algoritmasında ise alınan sinyallerin SINR de˘gerleri g¨oz ¨on¨unde bulundurularak iyi
bilinen ¸co˘ga g¨onderim g¨u¸c-artı¸sı (BIP) algoritmasındaki ana fikre benzer bir yakla¸sım
uygulanmı¸stır. Buna ek olarak, algoritmanın miyop etkisini azaltmak i¸cin SINR-BIP'in
i¸cine g¨om¨ul¨u olarak bir budama yordamı kullanılmı¸stır. C¸ o˘ga g¨onderim a˘gacı her
yinelemede 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 elde
edilen ¸co˘ga g¨onderim a˘gacının toplam enerji t¨uketiminin Tamsayı Programlama ile
elde edilene %20 oranında yakın oldu˘gu g¨ozlenmektedir.

Abstract:
In recent years wireless multi-hop networks have attracted significant attention due
to their wide range of potential civil and military applications. Broadcasting is a fundamental
data dissemination scheme for these networks. The transmission power control
is an important issue in wireless ad hoc networks and still has no satisfactory solution
methods. The wireless networking environment presents formidable challenges to the
study of broadcasting problems. In particular, the properties of the wireless medium
and the presence of battery-powered devices require novel modeling and algorithmic
approaches 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 the
source to each of the destination nodes. Moreover, the received signal at each receiving
node must be strong enough to be successfully decoded. In this study we address
the minimum-energy broadcast problem in multi-hop wireless networks with respect to
two different constraints: (i) each node must receive broadcast message within a given
delay bound , and (ii) signal-to-interference-plus-noise ratio (SINR) of the received
signal must be above a given threshold 
 so that the received signal can be successfully
decoded at the receiving node. We propose two distinct algorithms Distributed Tree
Expansion (DTE) and SINR-BIP which aim to generate minimum power broadcast
tree with respect to constraint (i) and (ii), respectively and exclusively. DTE is based
on an implementation of a distributed minimum spanning tree algorithm in which the
tree grows at each iteration by adding a node that can cover the maximum number
of currently uncovered nodes in the network with minimum incremental transmission
power and without violating the delay constraint. In SINR-BIP, we apply the similar
idea of well-known Broadcast Incremental Power (BIP) algorithm while considering the
SINR values of received powers. In addition, we use an embedded pruning procedure
in SINR-BIP, so that the myopic effect of the algorithm is mitigated. Both the algorithms
DTE and SINR-BIP are constructive in nature since the broadcast tree grows
at each iteration. We observed that the DTE outperforms the existing algorithms and
the total energy consumptions of the generated broadcast trees by DTE is within 20%
percent of the solutions obtained by Integer Programming.