Topology control in wireless ad hoc networks

Hassan, Ahmed Mohamed Ali Omer (2014-04)

Thesis (MSc)--Stellenbosch University, 2014.

Thesis

ENGLISH ABSTRACT: Wireless ad hoc networks are increasingly used in today’s life in various areas ranging from environmental monitoring to the military. For technical reasons, they are severely limited in terms of battery power, communication capacity and computation capability. Research has been carried out to deal with these limitations using different approaches. A theoretical treatment of the subject is topology control whose basic task is to design network topologies with special properties that make them energy-efficient and interference-optimal. We study, implement and compare the XTC and CBTC algorithms in terms of interference reduction, length stretch factor and maximum degree. These two algorithms have two features that are absent in almost all competitive topology control algorithms which are practicality and maintaining connectivity. Both algorithms show good performance in terms of interference reduction and maintaining a good length stretch factor. Regarding CBTC, we prove that it is a power spanner. We show through extensive simulation that the degree distribution of wireless ad hoc networks modelled by the log-normal model is binomial if the average degree is not high. We find that there is no fixed threshold for the average degree at which the distribution is distorted and no longer binomial. We show through simulation that the node density which ensures the absence of isolated nodes is a tight lower bound for the node density which ensures connectivity. The implication of this result is that connectivity is ensured with high probability if the minimum node degree is equal to 1. Finally we show through simulation that the log-normal model is not a realistic representation of wireless ad hoc networks if the environmental parameter is at least 6. This result is important because there are no available measurements to determine the range of the environmental parameter for typical frequencies used in wireless ad hoc networks.

AFRIKAANSE OPSOMMING: Koordlose ad hoc netwerke word toenemend gebruik in vandag se lewe op verskillende gebiede wat wissel van die omgewing monitor tot militêregebruik. Vir tegniese redes is hulle ernstig beperk in terme van battery krag, kommunikasie kapasiteit en berekeningsvermoë. Navorsing vanuit verkillende benaderings word gedoen om met hierdie beperkings te deel. ’n Teoretiese benadering tot onderwerp is topologie beheer. Die basiese taak is om netwerktopologieë met spesiale eienskappe wat hulle energie-doeltreffend en interferensieoptimaal maak te ontwerp. Ons bestudeer, implementeer en vergelyk die XTC en CBTC algoritmes in terme van interferensie vermindering, lengte rek faktor en maksimum graad. Beide hierdie algoritmes het twee eienskappe wat afwesig is in byna al die mededingende topologie beheer algoritmes: hulle is prakties en handhaf verbindings. Beide algoritmes toon goeie prestasie in terme van interferensie verminder en die handhawing van ’n goeie lengte rek faktor. Ten opsigte van CBTC bewys ons dat dit ’n “power spanner” is. Ons wys deur middel van uitgebreide simulasie dat die graad verdeling van die koordlose ad hoc netwerke wat deur die log-normale model gemodelleer kan word binomiaal is as die gemiddelde graad nie hoog is nie. Ons vind dat daar geen vaste drempel is vir die gemiddelde graad waarby die verdeling vervorm en nie meer binomiaal is nie. Ons wys deur simulasie dat die node digtheid wat die afwesigheid van geïsoleerde nodusse verseker ’n streng ondergrens vir die node digtheid wat konnektiviteit verseker is. Die implikasie van hierdie resultaat is dat ‘n konneksie verseker word as die minimum node graad gelyk is aan 1. Ten slotte wys ons deur simulasie dat die log-normale model nie ’n realistiese voorstelling van koordlose ad hoc netwerke is wanneer die “environmental parameter” groter is as 6 nie. Hierdie resultaat is belangrik, want daar is geen beskikbare metings om die grense van hierdie parameter vir ’n tipiese frekwensie gebruik in koordlose ad hoc netwerke te bepaal nie.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/86709
This item appears in the following collections: