Sage Journals: Discover world-class research

Abstract

A wireless network consists of a large number of nodes with limited resources. The large number of event data will be generated over a period of time in a wireless network. Also, faced with high resource demand variability and with misfit resource renting policies, the current practices is to overprovision for each game tens of owned data. In a wireless network, the agent node may become easily overloaded by the high demand from the players for updates. So, we propose a hybrid load balancing scheme for games in wireless networks which is based on allocating load on wireless mobile nodes proportionally to each of the agent's capacities. This proposed scheme is a combined dynamic provisioning algorithm based on greedy graph and user-oriented load balancing scheme for maintaining the performance and stability of distributed system in wireless networks. We address the key functions for our proposed scheme and simulate the efficiency of our proposed scheme using mathematical analyses. We then testify that the proposal has best performance compared with previous researches.

1. Introduction

A wireless network consists of a large number of tiny nodes with limited computation, memory storage, communication range, and battery power [1]. The wireless network is comprised of many low cost devices called nodes which monitor the status of the environment and send sensing data to the sink node. Without load balancing, a coordinator with excessive number of wireless mobile nodes may lead to more energy consumption and experience data reception delay as compared to the other coordinators. In a wireless network, frequent changes in large scale network topology lead to a challenge for delay sensitive data reception. When nodes that are associated with the same coordinator send data at the same time, there will be a delay or a failure of data received by the coordinator. Wireless mobile nodes have maximum utility when they can be used “anywhere at any time” [2]. Additionally, some of the ability is to provide a more abundant user experience by running heavy desktop based games. With the explosion of games and user demand, wireless networks are born to integrate cloud networks into the wireless networks. Also, wireless networks bring unprecedented opportunities and challenges associated with developing mobile user-oriented specific mobile games. To apply wireless networks to mobile environment, there are still many obstacles including service availability, mobility, security, privacy, and load balancing.

In the wireless networks, the mobile games in which a large number of players can interact with each other in the same world at the same time [3, 4], so it is the large number of players interacting simultaneously, reaching the number of tens of thousands [5]. Each of the players remotely controls one or several in game characters called avatars. States of the avatars are simulated by the hosting agent, with updates of the avatars states broadcasted to other hosting agents and clients. In this way, all avatars can be properly rendered on their client side. For example, if the avatars of two players are too distant from each other, probably there will be no interaction between them and therefore the agent needs only to update each one with the result of their own actions. However, if these avatars are close to each other, each player should be updated not only by his own actions, but also by the actions of the other player [6]. For this reason, it is not enough just to divide the players between agents, even if this division is proportional to the resources of each one of them. There are several limitations. In some instances, a large number of mobile nodes result in bandwidth demand that is a square function to the number of players. In other situations, there may be linear relationship to wireless networks. Another important consideration is the overhead of the distribution. As the agents need to communicate with one another, there must be a way to minimize this traffic. Reducing the waste of resources of the agent system for mobile games must prevent the presence of hotspots from degrading the quality of the game beyond a tolerable limit. There is an important issue when considering a load balancing scheme in wireless network. It must be established within a short time to adapt to the change in wireless nodes locations, and the parameter that triggers the action must relate to the changes in the topology.

Therefore, we propose a hybrid scheme that is combined dynamic provisioning algorithm based on greedy graph and user-oriented load balancing scheme for maintaining the performance and stability of distributed system in wireless networks.

The rest of the paper is structured as follows. Section 2 introduces related works on load balancing schemes on wireless networks. In Section 3, we describe our proposed architecture and provide the detailed load balancing scheme for mobile games in wireless networks. Also in Section 4, we address the efficiency of our proposed scheme using analytical models and compare the results with the previous researches. In the final section, we constitute a summary of our proposal and suggest further study directions.

2. Related Works

In wireless networks, communication efficiency and power consumption are usually the main obstacles to improving service availability and energy efficiency. The power consumption of node and link is highly related with the corresponding traffic volume. One method to solve the tradeoff between communication efficiency and power consumption is to distribute the traffic uniformly across the network. To deal with this issue, a number of load balancing approaches have been previously proposed.

A real-time communication protocol named SPEED is proposed in [7, 8], in which a stateless nondeterministic geographic forwarding (SNGF) algorithm was employed. SPEED can support soft real-time communication based on feedback control and SNGF. The control overhead and the transient congestion are also well handled. However SNGF forwards each stream among random concurrent paths. Thus, if only a few paths with the same cost are available between each pair of nodes, there will be very few paths for SNGF to choose from. Two paths with the same cost rarely occur between two nodes.

Other approaches include a load balance solution derived by formulizing the network lifetime maximization problem into a nonlinear programming [9], a method to achieve load balance among all clusters, each of which is composed of several nodes in wireless networks [10, 11]. This least energy constraint node in a cluster acts as the cluster head and performs as the gateway to forward data to the base station. However, this method achieves load balance in an offline way that is based on the static traffic demand knowledge and topology information.

It only balances the load among different clusters but not all nodes. A multipath protocol and an algorithm were also proposed to achieve load balance in wireless networks [12]. While the aim of this approach is to reduce the energy consumption for each node other than the link utilization of wireless link, there is a limitation. The load balance ratio has to be determined prior to performing the proposed protocol in the network using offline nonlinear programming.

The load distributing problem in conventional distributed systems has been studied for many years. It can be classified into static and adaptive algorithms, where adaptive algorithms can be regarded as special class of dynamic algorithm. Dynamic load distributing algorithms can be further classified into load sharing algorithms and load balancing algorithms [13–16].

A load shedding method is one in which an overloaded server attempts to shed its load to its neighbors [17]. After finding a lightly loaded neighbor server, it transfers some of its boundary microcells to that neighbor. To form the group of microcells to transfer, a microcell from the border is chosen and others are added in a breadth first search (BFS) order. A very similar work, which also uses BFS, is described in [18].

Zone sharing is a distributed scheme for the decomposition of storage hotspots [19]. It presents the solution in the context of the distributed index for multidimensional data scheme [20]. The benefit of this structure is that it stores data with similar attributes nearby and enables energy efficient query resolution [21]. When a hotspot arises in a set of mobile nodes, those nodes falling on the border of the hotspot will transfer some loads of their zones to some of their less-loaded neighbors. The information will be sent to notify its neighbors and to increase the cost of communication. Although zone sharing can distribute the heavy loads of a mobile node to other nodes, it will incur extra overhead and destroy the distributed multidimensional data scheme structure.

A dynamic geographic hash table for data centric storage is proposed in [22, 23]. A temporal-based hashing function redefines the original basic operation of the geographic hash table and combines the timeslot. For each timeslot, each event is mapped into a grid cell. For the next timeslot, the next event will be mapped into another grid cell and thus achieve load balancing. The concept of node contribution potential is used to avoid situations where events are mapped into locations in which the surrounding nodes do not have enough resources to service the networks [24–26]. However, the contribution potential value and the coordinate of the node with the highest potential in a cell must relay back to the sink. The sink selects a set of cells with potentials above a certain threshold to be the location set. Hence, it may result in a higher overhead. In addition, all nodes must be time synchronized and hence will need extra overhead.

3. Proposed Load Balancing Scheme

For the load balancing approach, we propose that the traffic generated by player is not simply linear but is the square for each cluster of game players in wireless networks. And another point is the overhead, which must be taken into account, no matter which load balancing algorithm is being used.

Our proposed scheme combines dynamic provisioning algorithm based on greedy growing algorithm and a user-oriented load balancing scheme, which seeks to allocate the heaviest mobile node and nearest mobile nodes in communication with the regions managed by the most powerful agents. An initial division of the wireless networks is considered in Figure 1.

Figure 1

An example for proposed scheme of wireless mobile nodes.

In Figure 1, the vertex indicates the wireless mobile node and the selection starts with the vertex of weight 6 and at each step the vertex is connected by the heaviest edge and nearest of mean of the region added to the partition. The selected edges and the vertices belonging to the new partition are highlighted. The proceeding and result of the first execution are shown in Tables 1 to 3. Also, the second proceed and result of our proposed scheme are addressed in Tables 4 and 5. Result of the first execution of proposed scheme is shown in Table 3. In Table 1, the R means the number of wireless network group and F means the fragment of the wireless networks. Table 2 shows the distance between vertices by coordinates.

Table 1

Proceed of first execution of proposed scheme.

	Vertex	Number of vertices	Weight	Center
	Vertex	Number of vertices	Weight	x	y
R1	A, B	2	17	0	0.5
R2	E, D	2	9	1.5	0.5
R3_F	F, G	2	5	0.3	0.5
R4_F	C	1	4	1	1
R5_F	H	1	3	2	2

$R = 2$ and $F = 3$ ; R: wireless network group and F: Fragment.

Table 2

Distance of between vertexes by coordinates of first execution.

Vertex	Mean		A	B	C	D	E	F	G	H
Vertex	x	y	A	B	C	D	E	F	G	H
A	0	0	0	1
B	0	1	1	0	1	1.41
C	1	1		1	0		1
D	1	0		1.41		0	1.41		2	2.23
E	2	1			1	1.41	0	1
F	3	1					1	0	1
G	3	0				2		1	0
H	2	2				2				0

Table 3

Result of first execution of proposed scheme.

	Vertex	Number of vertices	Weight	Mean
	Vertex	Number of vertices	Weight	x	y
R1	A, B	2	17	0	0.5
R2	E, D	2	9	1.5	0.5
R3_F	F, G	2	5	3	0.5
R4_F	C	1	4	1	1
R5_F	H	1	3	2	2

Table 4

Proceed of second execution of proposed scheme.

	Vertex	Number of vertices	Weight	Center
	Vertex	Number of vertices	Weight	x	y
R1	A, B, D, E	4	17	0.3	0.3
R2	F, G	2	9	3	0.5
R3_F	H	1	3	1	1
R4_F	C	1	3	2	2

$R = 2$ and $F = 3$ ; R: wireless network group; F: fragment.

Table 5

Result of second execution of proposed scheme.

	Vertex	Number of vertices	Weight	Mean
	Vertex	Number of vertices	Weight	x	y
R1	A, B, D, E	4	20	0.3	0.3
R2	F, G	2	9	3	0.5
R3_F	C	1	3	2	2
R4_F	H	1	3	2	2

When wireless mobile gaming users are within visual range of each other, it is best to locate them in one mobile agent [27, 28]. To manage wireless mobile gaming users like the above, both the scope of interactions and the probable interactions have to be taken into account and then set the neighboring gaming users area to about 1.5~2 times the visual range of the gaming users at the center. All wireless mobile gaming agents or anchors have the same capacity, each one being able to handle the same wireless mobile gaming users. When new wireless mobile gaming users proceed to login, first check whether the existing wireless mobile gaming users are in the nearest gaming user area; if so, then distribute the new wireless mobile gaming users to the nearest wireless mobile gaming user areas.

It is considered that an initial section of the virtual environment has already been made. Each mobile agent or agent should then check regularly if there is an imbalance and trigger the algorithm. Although the overhead resulting from the distribution of the virtual environment is part of the workload on mobile agent or agents, there is no way to know it beforehand without executing the repartitioning first.

For load-balancing, each of the centers of each gaming agent gets updated at the load-balancing agent and this point is equated by the average coordinates of the game users. Load-balancing agents distribute gaming users to the agent which is closest to the center of the agent when new game users login and when all gaming users of the game agents are not included in the nearest section. Figure 2 shows the selection anchor node of the wireless gaming nodes.

Figure 2

An anchor of wireless gaming nodes.

The proposed scheme is as follows: (i)

select the group of local regions: most of the largest cells are allocated to the largest agent,

(ii)

calculate the weight of each of the cells and represent all of the cells in the graph,

(iii)

allocate coordinate of agent to average cells,

(iv)

decide on the cell adjacent of the agent through the coordinate of the cell,

(v)

balance these regions, assigning to each one a weight which is proportional to the power of its agent,

(vi)

refine the partitioning, reducing the overhead.

Details of our proposed scheme are shown in Algorithm 1. Let us consider N wireless mobile nodes connected to a distributed game session aggregating a total of H regions. Here, we use the parameters listed in Table 6 for the simulation of the load balancing in the wireless networks.

Table 6

The parameters of the simulation.

Parameters	Descriptions
N	Number of nodes
H	Number of regions
I	Total number of interactions
BE	Number of moving nodes
AE	Number of active entities
C	Number of connected wireless mobile nodes
$I C$	Number of avatars interacting with any other entities
$T_{i}$	Consumed time for each computation
$T_{u}$	Update of entity states received from/sent to another nodes
$T_{m}$	Reception of event message from/sent to other nodes
$P_{c i}$	Percentage of CH
$P_{e i}$	Average number of interactions as a percentage of BE
$P_{u i}$	Ratio between time necessary for one entity update
B	Bandwidth
$d_{update}$	Location update of wireless mobile nodes

Algorithm 1: Our proposed scheme.

cell has a position coordinates( $x, y$ );

weight_to_divide ← 0;

free_capacity ← 0;

for each region R in region_list do

weight_to_divide ← weight_to_divide + Wr(R)

free_capacity ← freee_capacity + P(S(R))

calulate distance between cells

S( $c x, c y$ ) ← cell(M) //s( $c x, c y$ ): agent's coordinates, cell( $x m, y m$ ): cell's mean

cell_list ← list of cells from R in increasing order of cell's distance

while fracCr(R) > fracCp(S(R)) do

if cell( $x, y$ ) is not adjcent of S( $c x, c y$ )

c ← first element from cell_list

remove C from R

remove C from cell_list

endif

end while

sort region_list in increasing order of u(S(R))

for each region R in region_list do

weight_share ← weight_to_divide * $P p$ (s(R))/free_capacity

while Wr(R) < weight_share do

if there is any cell from R neighboring a free cell then

R ←R U {neighbor free cell with the highest Intc(C)}

else if there is any free cell then

if cell adjacent to Agent

R ←R U {cell}

Else

R ←R U {heavist free cell}

endif

end while

end for

We propose an analytical model for the load of games in wireless networks. We consider two main types of resources used by games for load calculation. They are CPU and network. For modeling the load of one node in a wireless network, we consider three basic time activities with one game tick. $T_{i}$ is the computation of the interaction between pairs of entities. The $T_{m}$ is the reception of event messages from each mobile node. The $T_{u}$ is the update of entity states received from or sent to another mobile node. We model the time $T_{M}$ that the CPU time spends to send and receive messages from agent to each mobile node as

\begin{matrix} T_{M} = C \cdot t_{m} . \end{matrix}

(1)

Also,

\begin{matrix} T_{v} = (N - C) \cdot T_{u} + (BE - AE) \cdot T_{u} + AE \cdot T_{u} . \end{matrix}

(2)

The interactions between entities are considered function $f (e_{1}, e_{2})$ in our modeling. Therefore, we can define the CPU load of mobile node in wireless network as in [29].

4. Performance Analyses

For the proposed scheme described in Section 3, MATLAB10 was used in our simulation for performance analysis. Our scheme showed that even though the number of mobile nodes increased, the occurrence of reallocation for load-balancing did not increase as much. As shown in Figure 3, when the number of mobile nodes exceeds 700, our scheme is different from previous researches.

Figure 3

Reallocation by increasing wireless gaming nodes.

In addition, we triggered messages between mobile nodes in order to analyze the load balancing of the interaction between mobile nodes in wireless networks.

In Figure 4, we show that even when the number of interaction messages exceeds 1200, the number of reallocation for load balancing does not increase much in our scheme. Therefore, load balancing caused by many interactions between mobile nodes is much more efficient than those of previous researches.

Figure 4

Reallocation by increasing interactions.

In Figure 5, we illustrate the load of the wireless mobile nodes using our proposed scheme. We found that the load is kept constant in the wireless mobile nodes in our proposed scheme.

Figure 5

Load of the wireless gaming nodes.

5. Conclusion and Future Works

We propose a scheme which combines a dynamic provisioning algorithm based on greedy graph and user-oriented load balancing scheme for maintaining the performance and stability of distributed system in wireless networks. We address the key functions for our proposed scheme and simulate the efficiency of our proposed scheme using mathematical analysis. When compared with previous researches, our proposed scheme in Section 4 was proven by simulations through mathematical modeling to be more efficient than previous research; even though the nodes increase, the probability of node replacement for load-balancing decreases compared to previous research as shown in Figure 3. Despite the fact that the interactions within the node along with the load increase, efficient load-balancing still occurs as seen in Figure 4. We found through Figure 5 that the load is kept constant in the wireless mobile nodes on our proposed scheme. We are going to improve the scheme based on real data through tests that applied our scheme to the real-world.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The work of this paper was supported by research funds of KIAT (the Korea Institute for the Advancement of Technology). This work was supported by 2014 Hongik University Sabbatical Year Research Fund.

References

Kim

K.-H.

Lee

S.-J.

Congdon

On cloud-centric network architecture for multi-dimensional mobility

Proceedings of the 1st MCC Workshop in Mobile Cloud Computing (MCC '12)

2012

1 6

10.1145/2342509.2342511

Sinha

P. K.

Dhore

S. R.

Multi-agent optimized load balancing using spaning tree for mobile services

International Journal of Computer Applications 2010 1 6 33 40

10.5120/145-265

Kim

H.-Y.

An efficient access control scheme for online gaming agent

Computer Science and Convergence 2011 114 259 267 Lecture Notes in Electrical Engineering

Kim

H.-Y.

Park

H.-J.

An efficient gaming user oriented load balancing scheme for MMORPG

Wireless Personal Communication 2013 73 2 289 297

10.1007/s11277-013-1237-2

Schiele

Süselbeck

Wacker

Hähner

Becker

Weis

Requirements of peer-to-peer-based massively multiplayer online gaming

Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGRID '07)

May 2007

Rio De Janeiro, Brazil

773 782

2-s2.0-34548319382

10.1109/CCGRID.2007.97

Bezerra

C. E. B.

Comba

J. L. D.

Geyer

C. F. R.

A fine granularity load balancing technique for MMOG servers using a KD-tree to partition the space

Proceedings of the 8th Brazilian Symposium on Games and Digital Entertainment (SBGAMES '09)

October 2009

Rio de Janeiro, Brazil

17 26

2-s2.0-77954421356

10.1109/SBGAMES.2009.11

Stankovic

J. A.

Abdelzaher

SPEED: a stateless protocol for real-time communication in sensor networks

Proceedings of the 23th IEEE International Conference on Distributed Computing Systems

May 2003

Philadelphia, Pa, USA

46 55

2-s2.0-0037968893

10.1109/ICDCS.2003.1203451

Cheng

S.-T.

Chang

T.-Y.

An adaptive learning scheme for load balancing with zone partition in multi-sink wireless sensor network

Expert Systems with Applications 2012 39 10 9427 9434

2-s2.0-84859219035

10.1016/j.eswa.2012.02.119

Kacimi

Dhaou

Beylot

A. L.

Load balancing techniques for lifetime maximizing in wireless sensor networks

Ad Hoc Networks 2013 11 8 2172 2186

10.1016/j.adhoc.2013.04.009

10.

Gupta

Younis

Load-balanced clustering of wireless sensor networks

Proceedings of the IEEE International Conference on Communications (ICC '03)

May 2003

1848 11852

10.1109/ICC.2003.1203919

11.

Liao

W.-H.

Shih

K.-P.

W.-C.

A grid-based dynamic load balancing approach for data-centric storage in wireless sensor networks

Computers and Electrical Engineering 2010 36 1 19 30

2-s2.0-72449148749

10.1016/j.compeleceng.2009.04.003

12.

Y. M.

Wong

V. W. S.

An energy-efficient multipath routing protocol for wireless sensor networks

International Journal of Communication Systems 2007 20 7 747 766

2-s2.0-34547266421

10.1002/dac.843

13.

Bezerra

C. E. B.

Geyer

C. F. R.

A load balancing scheme for massively multiplayer online games

Multimedia Tools and Applications 2009 45 1–3 263 289

2-s2.0-69949121263

10.1007/s11042-009-0302-z

14.

Zamboni

M. A.

Ferretti

Interactivity maintenance event synchronization in massive multiplayer online games

2005 UBLCS-2005-05

15.

Nae

Iosup

Prodan

Dynamic resource provisioning in massively multiplayer online games

IEEE Transactions on Parallel and Distributed Systems 2011 22 3 380 395

2-s2.0-79551559106

10.1109/TPDS.2010.82

16.

de Grande

R. E.

Boukerche

Dynamic partitioning of distributed virtual simulations for reducing communication load

Proceedings of the IEEE International Workshop on Haptic Audio Visual Environments and Games (HAVE '09)

November 2009

Lecco, Italy

176 181

2-s2.0-76649139151

10.1109/HAVE.2009.5356113

17.

Quax

Cleuren

Vanmontfort

Lamotte

Empirical evaluation of the efficiency of spatial subdivision schemes and load balancing strategies for networked games

Proceedings of the 20th International Conference on Computer Communications and Networks (ICCCN '11)

July-August 2011

Maui, Hawaii, USA

1 6

2-s2.0-80052993224

10.1109/ICCCN.2011.6006024

18.

Lee

A scalable dynamic load distribution scheme for multi-server distributed virtual environment system with highly-skewed user distribution

Proceedings of the ACM Symposium on Virtual Reality Software and Technology

2003

New York, NY, USA

160 168

10.1145/1008653.1008681

19.

Aly

Morsillo

Chrysanthis

P. K.

Pruhs

Zone sharing: a hot-spots decomposition scheme for data-centric storage in sensor networks

Proceeding of the International Conference on Very Large Data Bases (VLDB '05) and the 2nd International Workshop on Data Management for Sensor Networks (DMSN '05)

August 2005

21 26

2-s2.0-77954445300

10.1145/1080885.1080890

20.

Kim

Y. J.

Govindan

Hong

Multi-dimensional range queries in sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03)

November 2003

New York, NY, USA

ACM

63 75

2-s2.0-4243197464

10.1145/958491.958500

21.

Jannotti

de Couto

D. S. J.

Karger

D. R.

Morris

A scalable location service for geographic ad hoc routing

Proceedings of the ACM 6th Annual International Conference on Mobile Computing and Networking (MobiCom '00)

August 2000

Boston, Mass, USA

120 130

2-s2.0-0034548432

22.

Tlili

Slimeni

A hierarchical dynamic load balancing strategy for distributed data minig

International Journal of Advances in Science and Technology 2012 39

23.

Zeynali

Khanli

L. M.

Mollanejad

Fuzzy based approach for load balanced distributing database on sensor network

International Journal of Future Generation Communication and Network 2010 3 2 41 52

24.

Wang

Liu

Zheng

A clustering algorithm based on virtual area partition for heterogeneous wireless sensor networks

Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA '07)

August 2007

Harbin, China

372 376

2-s2.0-37049018003

10.1109/ICMA.2007.4303571

25.

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

26.

Shu

Krunz

Coverage-time optimization for clustered wireless sensor networks: a power-balancing approach

IEEE/ACM Transactions on Networking 2010 18 1 202 215

2-s2.0-77249170731

10.1109/TNET.2009.2022936

27.

Shin

Abraham

Han

S. Y.

Self organizing sensor networks using intelligent clustering

Computational Science and Its Applications—ICCSA 2006 2006 3983 40 49 Lecture Notes in Computer Science

28.

Tarapata

Weremczuk

Jachowicz

Shan

X. C.

Shi

C. W. P.

Construction of wireless sensor for harsh environment operation

Procedia Chemistry 2009 1 1 465 468

10.1016/j.proche.2009.07.116

29.

Raj

J. S.

Hridya

K. S.

Vasudevan

Augmenting hierarchical load balancing with intelligence in grid environment

International Journal of Grid and Distributed Computing 2012 5 2 9 18