Mousavi Toroujeni, Seyed Mahdi (2020)
Game Theory for Multi-hop Broadcast in Wireless Networks.
Technische Universität Darmstadt
doi: 10.25534/tuprints-00009284
Dissertation, Erstveröffentlichung
Kurzbeschreibung (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.
Typ des Eintrags: | Dissertation | ||||
---|---|---|---|---|---|
Erschienen: | 2020 | ||||
Autor(en): | Mousavi Toroujeni, Seyed Mahdi | ||||
Art des Eintrags: | Erstveröffentlichung | ||||
Titel: | Game Theory for Multi-hop Broadcast in Wireless Networks | ||||
Sprache: | Englisch | ||||
Referenten: | Klein, Prof. Dr. Anja ; Freisleben, Prof. Dr. Bernd | ||||
Publikationsjahr: | 2020 | ||||
Ort: | Darmstadt | ||||
Datum der mündlichen Prüfung: | 24 Oktober 2019 | ||||
DOI: | 10.25534/tuprints-00009284 | ||||
URL / URN: | https://tuprints.ulb.tu-darmstadt.de/9284 | ||||
Kurzbeschreibung (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. |
||||
Alternatives oder übersetztes Abstract: |
|
||||
URN: | urn:nbn:de:tuda-tuprints-92845 | ||||
Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften und Maschinenbau |
||||
Fachbereich(e)/-gebiet(e): | 18 Fachbereich Elektrotechnik und Informationstechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Drahtlose Sensornetze 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik > Nachrichtentechnische Systeme |
||||
Hinterlegungsdatum: | 19 Jan 2020 20:55 | ||||
Letzte Änderung: | 22 Jun 2020 12:20 | ||||
PPN: | |||||
Referenten: | Klein, Prof. Dr. Anja ; Freisleben, Prof. Dr. Bernd | ||||
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: | 24 Oktober 2019 | ||||
Export: | |||||
Suche nach Titel in: | TUfind oder in Google |
Frage zum Eintrag |
Optionen (nur für Redakteure)
Redaktionelle Details anzeigen |