TU Darmstadt / ULB / TUprints

Game Theory for Multi-hop Broadcast in Wireless Networks

Mousavi Toroujeni, Seyed Mahdi (2020):
Game Theory for Multi-hop Broadcast in Wireless Networks.
Darmstadt, Technische Universität, DOI: 10.25534/tuprints-00009284,
[Ph.D. Thesis]

[img]
Preview
Text
2019-10-24_Mousavi Toroujeni_Seyed Mahdi.pdf
Available under CC-BY-NC-SA 4.0 International - Creative Commons, Attribution Non-commercial, Share-alike.

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Title: Game Theory for Multi-hop Broadcast in Wireless Networks
Language: English
Abstract:

Multi-hop broadcast is an important application in wireless networks. It can be employed for file sharing, software updates, notification distribution, video streaming, etc. In a multi-hop broadcast, a node of a wireless network, as the source, shares its message with other nodes in a multi-hop fashion. Due to the importance of power management in wireless networks, in this dissertation, we study power minimization in multi-hop broadcast. In a multi-hop broadcast, the message flow from the source to the receivers can be modeled as a tree-graph, called the broadcast-tree (BT) and the problem of disseminating the message in the network with minimum-power is called the minimum-power broadcast-tree (MPBT) problem. The MPBT problem is NP-complete, meaning that a polynomial-time algorithm unlikely exists for it. Hence, many centralized and decentralized approximation algorithms are proposed in order to approximate the MPBT problem. The primary focus of this dissertation is on developing decentralized methods for tackling the MPBT problem. We first propose a game-theoretic model for the MPBT problem. In the proposed game, every node, in order to receive the message, chooses another node as its respective transmitting node. In this case, a receiving node and its respective transmitting node are called the child node (CN) and the parent node (PN), respectively. Such a decision by a CN imposes transmit power on its chosen PN. The key idea here is to assign a cost to every CN according to the power it imposes on its chosen PN so that the network power is minimized via cost minimization at the CNs. The game that we design is a non-cooperative cost sharing game. In such a game, via a so-called cost sharing scheme, the cost of using a PN is shared among the CNs that choose it. By employing a cost sharing game, the CNs are motivated to join together and form a multicast receiving group and this reduces the number of transmissions in the network. We study several cost sharing schemes and discuss their properties in terms of the performance of the obtained BT and the convergence of the game to a Nash equilibrium (NE). The proposed game-theoretic framework is further optimized for video streaming in user-centric networks (UCNs). The considered video is assumed to be encoded by the scalable video coding (SVC) technique. An SVC video consists of several layers and in our work, it is assumed that every layer of the video is streamed by a separate BT. To receive a certain video quality, a node has to join the corresponding BTs. In order to provide an incentive for the PNs, we assume that the PNs are paid by their corresponding CNs via tokens. The payment depends on the energy consumed by the PNs. By collecting tokens in exchange for forwarding the video, a contributing node is able to receive a higher video quality. Further, in multi-hop broadcast, the contribution of the nodes who are located closer to the source is vital for the rest of the network. To address this issue, we propose a taxation mechanism that specifically provides higher rewards for the nodes closer to the source. It is shown that the proposed game-theoretic incentive mechanism significantly improves the video quality perceived by the users while preserving the energy-efficiency of the network.

Alternative Abstract:
Alternative AbstractLanguage
Multi-Hop Broadcastübertragung ist eine wichtige Anwendung in drahtlosen Netzwerken. Sie kann u.a. zum Austausch von Dateien, zur Aktualisierung von Software oder zur Verteilung von Benachrichtigungen eingesetzt werden. Beim Multi-Hop Broadcast teilt ein Knoten des drahtlosen Netzwerks, der als Quelle agiert, seine Nachricht durch Multi-Hop Übertragung mit anderen Knoten. Aufgrund der Bedeutung des Energieverbrauchs in drahtlosen Netzwerken, wird in dieser Dissertation die Minimierung des Energieverbrauchs in Multi-Hop Netzwerken untersucht. Der Nachrichtenfluss von der Quelle zu den Empfängern kann als Baumdiagramm dargestellt werden, welches als Broadcast-Tree (BT) bezeichnet wird. Das entsprechende Problem, die Nachricht mit minimalem Energieaufwand im Netzwerk zu verbreiten, wird als Minimum-Power Broadcast-Tree (MPBT) Problem bezeichnet. Das MPBT-Problem ist NP-vollständig, was bedeutet, dass es sich vermutlich nicht effizient lösen lässt. Daher wurden viele zentralisierte und verteilte Algorithmen vorgeschlagen, die das MPBT-Problem approximieren. Der primäre Fokus dieser Dissertation liegt auf der Entwicklung verteilter Algorithmen, die das MPBT-Problem angehen. In dieser Dissertation wird ein Modell für das MPBT-Problem basierend auf Spieltheorie vorgeschlagen. In diesem Modell wählt jeder Knoten, der eine Nachricht empfangen möchte, einen anderen Knoten als entsprechenden Sendeknoten aus. In diesem Fall wird der sendende Knoten als Parent Node (PN) und der empfangende Knoten als Child Node (CN) bezeichnet. Eine solche Entscheidung erlegt dem gewählten PN eine Sendeleistung auf. Der Grundgedanke des Modells ist die Zuordnung von Kosten zu jedem CN in Abhängigkeit der auferlegten Sendeleistung an den von ihm gewählten PN, um durch Kostenminimierung an den CNs auch die Leistung im Netzwerk zu minimieren. Das modellierte Spiel ist ein nicht-kooperatives Kostenteilungsspiel. In einem solchen Spiel werden die Kosten der Nutzung eines PNs von allen CNs, die diesen PN wählen, über ein sogenanntes Kostenteilungsschema geteilt. Durch die Nutzung eines Kostenteilungsspiels, werden die CNs zum Zusammenschluss durch Bildung einer Multicast-Empfangsgruppe motiviert, um die Anzahl der notwendigen Übertragungen im Netzwerk zu reduzieren. Mehrere Kostenteilungsschemata und die jeweiligen Eigenschaften in Bezug auf die Performanz des erreichten BT sowie die Konvergenz hin zu einem Nash-Gleichgewicht (engl. Nash equilibrium, NE) werden diskutiert. In dieser Dissertation wird daher das vorgestellte spieltheoretische Grundgerüst weiter auf Videostreaming in nutzerzentrierten Netzwerken (engl. User-Centric Networks, UCNs) optimiert. Es wird angenommen, dass das betrachtete Video mit der Scalable Video Coding (SVC) Technik kodiert ist. Ein SVC Video besteht aus mehreren Schichten, und es wird angenommen, dass jede Schicht des Videos über einen anderen BT verbreitet wird. Um eine bestimmte Videoqualität zu erhalten, muss ein Knoten dem entsprechenden BTs beitreten. Um den beitragenden Knoten einen Anreiz zu bieten nehmen wir an, dass empfangende Knoten als Belohnung einen sogenannten Token an die sendenden Knoten zahlen, der von der von den PNs verbrauchten Energie abhängig ist. Indem ein teilnehmender Knoten Tokens für das Weiterleiten von Videos sammelt, erhält er die Möglichkeit an einer größeren Anzahl BTs teilzunehmen und eine bessere Videoqualität zu erhalten. Bei Multi-Hop Broadcast haben in der Nähe der Quelle sitzende Knoten eine hohe Bedeutung für den Rest des Netzwerks. Um die Performanz zu erhöhen schlagen wir daher ein Verteilungsmodell vor, das speziell den Knoten nahe der Quelle höhere Belohnungen verspricht. Es wird gezeigt, dass das vorgestellte spieltheoretische Anreizmodell zu einer signifikanten Steigerung der wahrgenommenen Videoqualität bei den Nutzern bei gleichzeitiger Beibehaltung der Energieeffizienz des Netzwerks führt.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Communications Engineering
Date Deposited: 13 Jan 2020 14:34
Last Modified: 19 Jun 2020 14:07
DOI: 10.25534/tuprints-00009284
URN: urn:nbn:de:tuda-tuprints-92845
Referees: Klein, Prof. Dr. Anja and Freisleben, Prof. Dr. Bernd
Refereed: 24 October 2019
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/9284
Export:
Actions (login required)
View Item View Item