Nom original: 06633998.pdfTitre: Paper Title (use style: paper title)Auteur: IEEE
Ce document au format PDF 1.5 a été généré par Microsoft® Office Word 2007, et a été envoyé sur fichier-pdf.fr le 01/01/2014 à 21:32, depuis l'adresse IP 41.224.x.x.
La présente page de téléchargement du fichier a été vue 867 fois.
Taille du document: 578 Ko (3 pages).
Confidentialité: fichier public
Aperçu du document
2013 INTERNATIONAL CONFERENCE ON COMPUTING, ELECTRICAL AND ELECTRONIC ENGINEERING (ICCEEE)
Gateway Placement Approaches in Wireless Mesh
Network: Study Survey
Awadallah M. Ahmed
Aisha H. Abdalla
Faculty of Mathematical and
University of Gezira, Wad Medani
Faculty of Engineering, International
Islamic University Malaysia,
Kuala Lumpur, Malaysia
Department of Computer Engineering,
Al Neelain University,
its nature, wireless mesh networks suffers from the
bandwidth limitation .
A WMN needs gateway devices to connect to the
internet; usually in mesh networks. Some mesh routers
have the gateway functionality which can provide the
connectivity of WMN to the internet . Since the mesh
routers are the backbone of the networks, they make
bottleneck, therefore the gateway placement is an
important issue in network design in order to increase
the network throughput, to guarantee load balancing in
gateways and minimize signaling cost in the network,
then leads to better performance.
This paper focuses on presenting different gateway
placement approaches in the wireless mesh network area
considering the variation in the mechanism and the
design philosophy they have used. The research efforts
in the gateway placement in WMN are classified into
two broad categories:
the first consists of the papers pertaining to
throughput performance and connectivity
the secongd deals with quality of services.
Abstract—In this paper, gateway placement approaches in
Wireless Mesh Network are studied and evaluated. Their
purposes are classified.
According to the relevant
researches in this area, there are many gateway placement
approaches in Wireless Mesh Network that have been
found. These approaches are designed to find an optimal
network throughput, cost minimization, quality of services
and load balancing. In this paper these approaches are
classified depending on their purposes. This classification
helps in determining the optimal approaches by
comparing and analyzing the mechanism of each approach
and then select the suitable approach that can be used
depending on the aim of the wireless mesh network. The
study result shows that there are significant research
efforts in gateway placement problem in wireless mesh
network specifically in terms of throughput and quality of
services, but extra research efforts are needed in gateway
placement considering load balancing.
IndexTerms—Wireless Network, Wireless Mesh Networks,
and Gateway placement approaches
Recently wireless networks have gained more
attention by the researchers. This is because of their
limitations and challenges. Wireless mesh network
(WMN) is a communication technology for last-mile
broadband internet access , community and
neighborhood networks . WMN consists of mesh
routers (MR)s and mesh clients (MC)s. The backbone
here is a multi-hop wireless network of mesh routers.
The mesh backbone (network infrastructure for mesh
clients) can be built using Nemours types of radio
technologies . the mesh routers are self-configuring
and self-healing links among themselves . A WMN is
a type of wireless network, so it suffers from the same
limitations and challenges of the wireless network. By
978-1-4673-6232-0/13/$31.00 ©2013 IEEE
II. GATEWAY PLACEMENT APPROACHES
This Section classifies and studies gateway placement
approaches depending on their purpose such as:
throughput performance, connectivity/coverage rate,
load balancing, cost minimization, quality of services
and delays in communication.
A. Gate placement approaches for Load balancing
In , a gateway placement approach using linear
programming as a multiple objective was proposed.
Their approach used an algorithm for gateway selection,
and to balance the number of mesh routers attached to
the gateway. Althourgh the proposed approach achieved
a good load balancing comparing with the others, but no
improvement was achieved in their approach in the
number of gateways and the hop count.
network was proposed. The authors of that paper used
the proposed model in  to generate multiple scenarios
and then compare their relative performance in terms of
the network throughput. The proposed solution can
attain good performance by a achieving the optimum
throughput, but the solution can only be used in
networks with a single gateway while most of the
networks use multiple gateways.
B. Gateway placement approaches for connectivity/coverage
In , a new gateway problem approach was proposed
to solve the wireless mesh network bottleneck problem
at gateways to optimize the network performance. In this
paper, all mesh routers firstly were distributed and
treated as nodes. Then the weighted objective function
was designed using the logarithm normal distribution
model to guarantee the connectivity of all nodes
including the routers. Finally the nodes of high
throughput and better connectivity were configured as
gateways using tree-set partition (TSP) algorithm to
choose between them. The proposed solution achieved
better optimization in wireless mesh network
considering the connectivity, coverage, and throughput
performance; but in large networks the cost may increase
due to the increasing number of gateways in the network
that were configured as gateways to maintain high
connectivity and coverage rate.
D. Gateway placement approaches for cost minimization
In , a model to solve gateways placement problem
depending on integer linear programming with
considering quality of service issues was proposed. The
degree-based GDTSP was used to make comparisons
among existing solutions, and finally heuristic algorithm
was developed. However, the solution concentrated only
on cost minimization rather than enhancing the
performance. This is a drawback because one cannot
enhance performance and throughput without increasing
the number of gateways. So, this will automatically
increase the cost and thus it leads to a contradiction with
the assumption of reducing the cost.
C. Gateway placement approaches for optimal throughput
E. Gateway placement approaches for quality of services
considering relay load and delay in communication
In , grid-based gateway deployment method was
proposed using cross-layer throughput optimization. LPFlow-Throughput was used as an evaluation tool. The
evaluation shows that, the method exploits the available
resources effectively and it performs better than the
random and fixed deployment methods. Although, the
proposed solution achieved better throughput,
connectivity and coverage because of using a lot of
gateways; but this will increase the cost of the
equipment. Furhtermore, this solution did not consider
the number of mesh routers connected to the specific
gateway, so the balancing in number of mesh routers per
gateway has been forgotten.
In , a configuration model for a fixed wireless mesh
network haw proposed to determine the maximum and
the optimal throughput depending on fixed wireless
nodes with fixed locations and data flows generated in in
a logical manner, and also to determine how the network
can be configured to achieve the optimum throughput.
The authors of that paper developed and investigated
optimization framework to define the optimal throughput
and also to set the network configuration. They used the
enumerative method to get numerical results in different
situations of interest and to get different insights about
the network structure considering the optimal routes,
schedules and physical layer parameters. The proposed
model helps in determining the achievable throughput in
In , a model to generate many heuristics to get an
optimal position for a single gateway in wireless mesh
In , a solution was proposed and two gateway
placement problems were addressed: the first problem is
to optimize the delay in communication and the second
is to optimize the cost of communication. The
algorithms are flexible and can be improved considering
delay, relay load and the constraints the gateway
capacity as mentioned in , but the solution requires at
least two hops and two nodes to be tested.
In , an algorithm was proposed to solve the
gateway placement problem using clustering technique
in the following four stages: select cluster heads, assign
each node to an identified cluster satisfying the delay
constraint, break down the clusters that do not satisfy the
relay loadconstraint or the gateway capacity constraint,
and finally select gateways to reduce the maximum relay
load as mentioned in . However, the algorithm does
not have competitive performance because of the
following two reasons: first, when identifying cluster
heads and assigning mesh routers to the identified cluster
heads, the algorithm does not make use of global
information about the BWMN; second, splitting a cluster
without considering re-assigning those mesh routers to
existing clusters may create some unnecessary clusters
and therefore increases the number of clusters
significantly as mentioned in .
In , a new algorithm explored the placement
problem of Internet Transit Access Points (ITAP)s in
wireless neighborhood networks under three wireless link
models, and for each of the wireless link models,they
developed algorithms for the placement problembased on
neighborhood layouts, user demands, andwireless link
characteristics. The placement problem issimilar to the
gateway place of BWMN. However, theiralgorithms
consider only one constraint, that is, users’ bandwidth
requirements as mentioned in .
In , computationally the gateway placement
problem was considered as an N-Hard when it could be
transformed in a minimum dominating set problem and
proved as NP-complete and then adapted a recursive
dominating set algorithm to solve the minimum
dominating set problem. The algorithm considers the
delay, relay load and gateway constraints. This method
has better performance than the algorithms in [7, 9, 10].
However, it has the following deficiencies: first, it can
be used for those BWMNs that form a connected
component; second, it needs to set the initial radius size
properly; otherwise, it would not create satisfactory
results as mentioned in .
 W. Wu, J. Luo, and M. Yang, “Gateway placement
optimization for load balancing in wireless mesh
networks,” in CSCWD 2009. 13th International
Conference on Computer Supported Cooperative Work in
Design, 2009. IEEE, 2009, pp. 408–413.
 P. Jun and Z. QiangQiang, “Gateways placement
optimization in wireless mesh networks,” in International
Conference on Networking and Digital Society, 2009.
ICNDS’09, vol. 1. IEEE, 2009, pp. 221–226.
 F. Li, Y. Wang, and X.-Y. Li, “Gateway placement for
throughput optimization in wireless mesh networks,” in
IEEE International Conference on Communications, 2007.
ICC’07. IEEE, 2007, pp. 4955–4960.
 A. Karnik, A. Iyer, and C. Rosenberg, “Throughputoptimal configuration of fixed wireless networks,”
IEEE/ACM Transactions on Networking (TON), vol. 16,
no. 5, pp. 1161–1174, 2008.
 S. N. Muthaiah and C. Rosenberg, “Single gateway
placement in wireless mesh networks,” in Proceedings of
8th international IEEE symposium on computer networks,
 J. Ding, J. Xu, and Z. Zheng, “Gateway deployment
optimization in wireless mesh network: A case study in
china,” in IEEE/INFORMS International Conference on
Service Operations, Logistics and Informatics, 2009.
SOLI’09. IEEE, 2009, pp. 300–305.
 J. L. Wong, R. Jafari, and M. Potkonjak, “Gateway
placement for latency and energy efficient data
aggregation [wireless sensor networks],” in 29th Annual
IEEE International Conference on Local Computer
Networks, 2004. IEEE, 2004, pp. 490–497.
 T. Maolin, “Gateways placement in backbone wireless
mesh networks,” Int’l J. of Communications, Network and
System Sciences, vol. 2, no. 1, pp. 44–50, 2009.
 Y. Bejerano, “Efficient integration of multihop wireless
and wired networks with qos constraints,” IEEE/ACM
Transactions on Networking (TON), vol. 12, no. 6, pp.
 L. Qiu, R. Chandra, K. Jain, and M. Mahdian,
“Optimizing the placement of integration points in multihop wireless networks,” in Proceedings of ICNP, vol. 4,
 B. Aoun, R. Boutaba, Y. Iraqi, and G. Kenward,
“Gateway placement optimization in wireless mesh
networks with qos constraints,” IEEE Journal on Selected
Areas in Communications, vol. 24, no. 11, pp. 2127–2136,
III. . CONCLUSION
In this paper, gateway placement approaches in
Wireless Mesh Network are studied and evaluated, and
their purposes are studied. This paper has shown that,
there are many gateway placement approaches in
Wireless Mesh Network.
These approaches can be classified depending on their
design aims where these approaches are designed to find
an optimal network throughput in the form of perfect
connectivity and coverage, network performance, hops
count, network's equipments cost minimization, quality
of services and load balancing in term of the number of
mesh routers attached to the specific gateway.
This classification may help in determining the
optimal approaches by comparing and analyzing the
mechanism of each approach to select the suitable
approach among them depending on the aim of the
wireless mesh network and its design.
This study has shown that there are considrable
research efforts in gateway placement problem in
wireless mesh network specially in term of throughput
and quality of services, but extra research efforts are
needed in gateway placement considering load balancing
for better performance.