Back to search

Aristotle University Of Thessaloniki (AUTH)

Μέθοδοι μετάδοσης πληροφορίας με εξοικονόμηση ενέργειας σε ασύρματα μη δομημένα τηλεπικοινωνιακά δίκτυα

Abstract

dc:description

In this dissertation the routing problem with energy conservation in wireless ad hoc networks is studied. Due to the importance of the problem, there is a large amount of recent papers in the literature addressing the issue of energy-aware routing across multiple hops with different transmission energy requirements. The objective of this doctoral thesis is to propose and study new criteria for the efficient management of the available energy resources, provide the appropriate routing algorithms, analyze their performance and complexity, and compare them with existing algorithms. The study is composed of three parts. The first part of the dissertation addresses the problem of broadcasting (and multicasting) in wireless multi-hop networks, so that the power consumed by any node in the network individually is as small as possible. The problem is formulated as a lexicographic node power optimization one. According to this optimization criterion, provided that the kth maximum consumed node power is minimized, the (k+1)th maximum power is minimized next. The problem is in general NP-complete. An optimal polynomial time algorithm is provided first for a special case of the problem. Next, this algorithm is extended to provide an optimal solution for the general case. The derived algorithm runs in reasonable time for moderate size random networks, where it can be employed to test the efficiency of proposed heuristics. However, as expected, its worst case running time is exponential in the size of the network. To deal with networks of larger sizes, a heuristic is developed that is based on the steps of the optimal algorithm and avoids the most computing intensive operations. Numerical results show that the proposed heuristic has good running times and provides fairly satisfactory performance relative to the optimal algorithm. Hence, it presents a good compromise between running time and achieved performance. The algorithms developed in this part can also be used to solve many other interesting problems. A useful application for example is to implement broadcasting so that the residual energy of any node in the network after the broadcast process is as large as possible (lexicographic maximization of residual node energies). In the second part the minimum-energy broadcast problem in wireless multi-hop networks is examined. This criterion minimizes the sum of consumed node powers during a broadcast process. Although this problem has been studied extensively in the literature, most of previous approaches provide a solution for it which depends on the source node that initiates the broadcast request. That is, every time a node needs to broadcast some information to all other nodes in the network, the algorithm is executed for the specific source node. Hence, in general, each node in the network has to keep track of a large number of different broadcast trees (the number is equal to the size of the network in the worst case). This requires large memory space and processing capabilities on behalf of the nodes, a demand that cannot always be met. To overcome this restriction, a polynomial time approximation algorithm is presented, so that all broadcast requests initiated by different source nodes take place on the same broadcast tree. This approach simplifies considerably the tree maintenance problem and allows scaling to larger networks. The performance analysis indicates that the approximation ratio provided by the algorithm is close to the best achievable bound in polynomial time. Moreover, it is better than any other existing approximation factor. Numerical results show that there are some interesting instances of general networks for which the proposed algorithm outperforms significantly other algorithms. In general, it presents a good compromise between simplicity and achieved performance. The third part addresses the issue of maximizing the lifetime in a wireless sensor network with energy and power constrained sensor nodes and mobile data collection point (sink). Information generated by the monitoring sensors needs to be routed efficiently to the location where the sink is currently located. The capability of the sink to be located in different places during network operation is exploited in order to maximize network lifetime. A novel linear programming formulation of the problem is provided. It is shown that maximum lifetime can be achieved by solving optimally two joint problems: 1) a scheduling problem that determines the sojourn times of the sink at different locations, and 2) a routing problem in order to deliver the sensed data to the sink in an energy-efficient way. The proposed model provides the optimal solution to both of these problems and gives the best achievable network lifetime. It also results in a fair balancing of the energy depletion among the sensor nodes. The implementation of the model implies the need of a central controller where the solution to the linear programming problem will be computed. An interesting issue for further study is to propose new heuristic on-line algorithms to be used in an adaptive and distributed environment, where the sink sojourn times are not determined a priori. In any case, the proposed model, providing the optimal solution, can be used as a yardstick against which one can compare the performance of other heuristics that might be proposed in the future. The formulation can also be used as a starting point on which new algorithms can be implemented.

Degree

thesis:*
Grantor dc:publisher
Aristotle University Of Thessaloniki (AUTH)
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Papadimitriou, Ioannis
  • Παπαδημητρίου, Ιωάννης

Subjects

dc:subject × 16

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/15101

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Papadimitriou, Ioannis; Παπαδημητρίου, Ιωάννης. Μέθοδοι μετάδοσης πληροφορίας με εξοικονόμηση ενέργειας σε ασύρματα μη δομημένα τηλεπικοινωνιακά δίκτυα. Aristotle University Of Thessaloniki (AUTH), 2006. http://hdl.handle.net/10442/hedi/15101