Minimum energy cooperative path routing in all-wireless networks: NP-completeness and heuristic algorithms

Fulu Li; Kui Wu; Andrew Lippman

doi:10.1109/JCN.2008.6389840

Minimum energy cooperative path routing in all-wireless networks: NP-completeness and heuristic algorithms

Fulu Li, Kui Wu, Andrew Lippman

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

11 Citations (Scopus)

Abstract

We study the routing problem in all-wireless networks based on cooperative transmissions. We model the minimum-energy cooperative path (MECP) problem and prove that this problem is NP-complete. We hence design an approximation algorithm called cooperative shortest path (CSP) algorithm that uses Dijkstra's algorithm as the basic building block and utilizes cooperative transmissions in the relaxation procedure. Compared with traditional non-cooperative shortest path algorithms, the CSP algorithm can achieve a higher energy saving and better balanced energy consumption among network nodes, especially when the network is in large scale. The nice features lead to a unique, scalable routing scheme that changes the high network density from the curse of congestion to the blessing of cooperative transmissions. © 2008 KICS.

Original language	English
Pages (from-to)	204-212
Journal	Journal of Communications and Networks
Volume	10
Issue number	2
DOIs	https://doi.org/10.1109/JCN.2008.6389840
Publication status	Published - Jun 2008
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected]</a

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Research Keywords

Cooperative transmissions
Distributed algorithms
Energy efficiency
Wireless networks

Access Output

10.1109/JCN.2008.6389840

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{cb005dd8a5574ff9b213a8f28a192da8,

title = "Minimum energy cooperative path routing in all-wireless networks: NP-completeness and heuristic algorithms",

abstract = "We study the routing problem in all-wireless networks based on cooperative transmissions. We model the minimum-energy cooperative path (MECP) problem and prove that this problem is NP-complete. We hence design an approximation algorithm called cooperative shortest path (CSP) algorithm that uses Dijkstra's algorithm as the basic building block and utilizes cooperative transmissions in the relaxation procedure. Compared with traditional non-cooperative shortest path algorithms, the CSP algorithm can achieve a higher energy saving and better balanced energy consumption among network nodes, especially when the network is in large scale. The nice features lead to a unique, scalable routing scheme that changes the high network density from the curse of congestion to the blessing of cooperative transmissions. {\textcopyright} 2008 KICS.",

keywords = "Cooperative transmissions, Distributed algorithms, Energy efficiency, Wireless networks",

author = "Fulu Li and Kui Wu and Andrew Lippman",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected]</a",

year = "2008",

month = jun,

doi = "10.1109/JCN.2008.6389840",

language = "English",

volume = "10",

pages = "204--212",

journal = "Journal of Communications and Networks",

issn = "1229-2370",

publisher = "Korean Institute of Communications Information Sciences",

number = "2",

}

TY - JOUR

T1 - Minimum energy cooperative path routing in all-wireless networks

T2 - NP-completeness and heuristic algorithms

AU - Li, Fulu

AU - Wu, Kui

AU - Lippman, Andrew

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected]</a

PY - 2008/6

Y1 - 2008/6

N2 - We study the routing problem in all-wireless networks based on cooperative transmissions. We model the minimum-energy cooperative path (MECP) problem and prove that this problem is NP-complete. We hence design an approximation algorithm called cooperative shortest path (CSP) algorithm that uses Dijkstra's algorithm as the basic building block and utilizes cooperative transmissions in the relaxation procedure. Compared with traditional non-cooperative shortest path algorithms, the CSP algorithm can achieve a higher energy saving and better balanced energy consumption among network nodes, especially when the network is in large scale. The nice features lead to a unique, scalable routing scheme that changes the high network density from the curse of congestion to the blessing of cooperative transmissions. © 2008 KICS.

AB - We study the routing problem in all-wireless networks based on cooperative transmissions. We model the minimum-energy cooperative path (MECP) problem and prove that this problem is NP-complete. We hence design an approximation algorithm called cooperative shortest path (CSP) algorithm that uses Dijkstra's algorithm as the basic building block and utilizes cooperative transmissions in the relaxation procedure. Compared with traditional non-cooperative shortest path algorithms, the CSP algorithm can achieve a higher energy saving and better balanced energy consumption among network nodes, especially when the network is in large scale. The nice features lead to a unique, scalable routing scheme that changes the high network density from the curse of congestion to the blessing of cooperative transmissions. © 2008 KICS.

KW - Cooperative transmissions

KW - Distributed algorithms

KW - Energy efficiency

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=47249118431&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-47249118431&origin=recordpage

U2 - 10.1109/JCN.2008.6389840

DO - 10.1109/JCN.2008.6389840

M3 - RGC 21 - Publication in refereed journal

SN - 1229-2370

VL - 10

SP - 204

EP - 212

JO - Journal of Communications and Networks

JF - Journal of Communications and Networks

IS - 2

ER -

Minimum energy cooperative path routing in all-wireless networks: NP-completeness and heuristic algorithms

Abstract

Bibliographical note

UN SDGs

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this