Router Node Placement with Service Priority in Wireless Mesh Networks Using Simulated Annealing with Momentum Terms

Chun Cheng Lin, Lei Shu, Der-Jiunn Deng

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

In wireless mesh networks (WMNs), mesh clients communicate with each other via the gateway and bridging functions of mesh routers. The performance of a WMN is generally affected by its network connectivity and client coverage, both of which are determined by its router node placement (RNP) in the deployment area. For simplicity, previous works considered only the RNP where each mesh client is served as an equal. In practice, however, mesh clients should be served with different priorities owing to factors such as their importance and their different payments for the service access. To fulfil this requirement, by assuming that each mesh client is also associated with a service priority, this paper investigates an RNP problem with a service priority constraint in which the mesh clients with service priorities higher than a threshold must be served. Given that this problem inherited from the complexity of the original RNP problem is computationally intractable in general, this paper also develops a novel simulated annealing (SA) approach that takes into account momentum terms to improve the efficiency and accuracy of annealing schedules and prevent fluctuations in values of the acceptance probability function. Additionally, the time complexity of the proposed SA algorithm is analyzed. Furthermore, evaluation of different-size instances under various parameters and annealing schedules demonstrates the superiority of the proposed approach.

Original languageEnglish
Pages (from-to)1402-1411
Number of pages10
JournalIEEE Systems Journal
Volume10
Issue number4
DOIs
Publication statusPublished - 2016 Dec 1

Fingerprint

Wireless mesh networks (WMN)
Simulated annealing
Routers
Momentum
Annealing

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this

@article{9bde83936bdf45a58c0024ad89aa6171,
title = "Router Node Placement with Service Priority in Wireless Mesh Networks Using Simulated Annealing with Momentum Terms",
abstract = "In wireless mesh networks (WMNs), mesh clients communicate with each other via the gateway and bridging functions of mesh routers. The performance of a WMN is generally affected by its network connectivity and client coverage, both of which are determined by its router node placement (RNP) in the deployment area. For simplicity, previous works considered only the RNP where each mesh client is served as an equal. In practice, however, mesh clients should be served with different priorities owing to factors such as their importance and their different payments for the service access. To fulfil this requirement, by assuming that each mesh client is also associated with a service priority, this paper investigates an RNP problem with a service priority constraint in which the mesh clients with service priorities higher than a threshold must be served. Given that this problem inherited from the complexity of the original RNP problem is computationally intractable in general, this paper also develops a novel simulated annealing (SA) approach that takes into account momentum terms to improve the efficiency and accuracy of annealing schedules and prevent fluctuations in values of the acceptance probability function. Additionally, the time complexity of the proposed SA algorithm is analyzed. Furthermore, evaluation of different-size instances under various parameters and annealing schedules demonstrates the superiority of the proposed approach.",
author = "Lin, {Chun Cheng} and Lei Shu and Der-Jiunn Deng",
year = "2016",
month = "12",
day = "1",
doi = "10.1109/JSYST.2014.2341033",
language = "English",
volume = "10",
pages = "1402--1411",
journal = "IEEE Systems Journal",
issn = "1932-8184",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

Router Node Placement with Service Priority in Wireless Mesh Networks Using Simulated Annealing with Momentum Terms. / Lin, Chun Cheng; Shu, Lei; Deng, Der-Jiunn.

In: IEEE Systems Journal, Vol. 10, No. 4, 01.12.2016, p. 1402-1411.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Router Node Placement with Service Priority in Wireless Mesh Networks Using Simulated Annealing with Momentum Terms

AU - Lin, Chun Cheng

AU - Shu, Lei

AU - Deng, Der-Jiunn

PY - 2016/12/1

Y1 - 2016/12/1

N2 - In wireless mesh networks (WMNs), mesh clients communicate with each other via the gateway and bridging functions of mesh routers. The performance of a WMN is generally affected by its network connectivity and client coverage, both of which are determined by its router node placement (RNP) in the deployment area. For simplicity, previous works considered only the RNP where each mesh client is served as an equal. In practice, however, mesh clients should be served with different priorities owing to factors such as their importance and their different payments for the service access. To fulfil this requirement, by assuming that each mesh client is also associated with a service priority, this paper investigates an RNP problem with a service priority constraint in which the mesh clients with service priorities higher than a threshold must be served. Given that this problem inherited from the complexity of the original RNP problem is computationally intractable in general, this paper also develops a novel simulated annealing (SA) approach that takes into account momentum terms to improve the efficiency and accuracy of annealing schedules and prevent fluctuations in values of the acceptance probability function. Additionally, the time complexity of the proposed SA algorithm is analyzed. Furthermore, evaluation of different-size instances under various parameters and annealing schedules demonstrates the superiority of the proposed approach.

AB - In wireless mesh networks (WMNs), mesh clients communicate with each other via the gateway and bridging functions of mesh routers. The performance of a WMN is generally affected by its network connectivity and client coverage, both of which are determined by its router node placement (RNP) in the deployment area. For simplicity, previous works considered only the RNP where each mesh client is served as an equal. In practice, however, mesh clients should be served with different priorities owing to factors such as their importance and their different payments for the service access. To fulfil this requirement, by assuming that each mesh client is also associated with a service priority, this paper investigates an RNP problem with a service priority constraint in which the mesh clients with service priorities higher than a threshold must be served. Given that this problem inherited from the complexity of the original RNP problem is computationally intractable in general, this paper also develops a novel simulated annealing (SA) approach that takes into account momentum terms to improve the efficiency and accuracy of annealing schedules and prevent fluctuations in values of the acceptance probability function. Additionally, the time complexity of the proposed SA algorithm is analyzed. Furthermore, evaluation of different-size instances under various parameters and annealing schedules demonstrates the superiority of the proposed approach.

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

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

U2 - 10.1109/JSYST.2014.2341033

DO - 10.1109/JSYST.2014.2341033

M3 - Article

AN - SCOPUS:85010663314

VL - 10

SP - 1402

EP - 1411

JO - IEEE Systems Journal

JF - IEEE Systems Journal

SN - 1932-8184

IS - 4

ER -