Abstract: Processing capacity of general node in Wireless Sensor Network (WSN) is weak and they cannot work for a long time limited their power supply. Therefore, cloud computing resource was used in finishing and processing task of general node in WSN. In order to ensure optimal computing node searched in a limited time, a three-step timing ant colony algorithm was proposed in this study. Three timers were used in setting back time for three role ants such as information ant, positioning ant and task ant. When timer started, general node of WSN was in power saving state. Simulation experimental results showed that optimal computing resource could be found in a short time by using the method proposed in this study.
INTRODUCTION
Along with the rapid development of micro-electromechanical systems (MEMS), sensor technique and Wireless Communication (WC), wireless sensor network (WSN) came into being. In WSN, all network nodes are linked by the way of self-organizing. Final information collected by WSN is the fusion information of all nodes (Sousa et al., 2012).
At present, the development of wireless sensor networks is also faced with severe challenges. Information needed by major task is more and more in complex environment. The share of each node in WSN is growing. Restricted by their own conditions, general node in WSN can’t accomplish some difficult tasks such as self-localization, large data processing and continuous hot-line job (Paoli et al., 2012). If these tasks were passed back to the master node for processing, the load on the master node would increase dramatically and the efficiency of the whole WSN would be greatly reduced.
Cloud computing is a new theory of IT. It can find the best resource for various types of users in Internet (Moschakis and Karatza, 2010). The user’s own difficult problems will be resolved by utilizing these resources. If tasks of general node in WSN were sent to the cloud by wireless communication, pressure of the master node in WSN would be reduced and implementation efficiency of the whole WSN would be improved greatly.
Problem solved in this study is how to schedule the best resource for general node in WSN when the tasks were sent to the cloud.
PRELIMINARY WORK
Research in this study involved three technology fields: wireless sensor network (WSN), cloud computing, ant colony algorithm. So their knowledge and research were introduced at first.
Wireless sensor network (WSN): The Untied States is an international leader for WSN. Their main research work is focused on several major aspects such as system form, system architecture, node position and wireless communication. Among these studies, system form is the basis of other work.
Each node in WSN was usually thrown into the appointed area by artificial embedded, launched via rocket, or spread through the aircraft. All nodes were combined to form final WSN by self-organization (Al-Ameen and Hasan, 2008). The general structure of the WSN system is shown in Fig. 1.
In Fig. 1, the general node in WSN is A-D. In order to reduce the difficulty of dissemination or launch, these nodes should be compact, simple and portable. General node in WSN is only equipped with necessary sensors, power and communications devices. So they themselves do not have the data-processing capacity. Data collected by general node must be delivered to sink node to process. When data-process and information fusion are completed by Sink node, final results will be sent to User node via Internet or satellite.
Currently, the biggest obstacle to restrict the working ability and the operating range of WSN is that, data-processing capabilities of general node it too weak and their power can not supply long hours energy.
| Fig. 1: | Structure of wireless sensor network |
Subject to a variety of unknown factors, contact between general node and other nodes is sometimes difficult to achieve. It makes WSN hard to work reliability (Misra et al., 2010).
The emergence of cloud computing offers the possibility to solve the problem.
Cloud computing: Cloud computing comes from the parallel computing, distributed computing and utility computing. It provides the required services to user by paying a fee. Clouding computing has a lot of excellent features such as scalability, reliability and autonomy (Ahuja et al., 2011). Cloud is constituted of a large number of inexpensive computing node, for example, Google’s cloud includes even millions of low-cost computers. General composition of cloud computing is shown in Fig. 2.
Computing speed, storage capacity and bandwidth are different to each node in cloud. How to find the most appropriate virtual machine resources for different users? It comes down to resource scheduling for cloud computing. Meta-scheduling model and Meta-scheduling policy were proposed (Assuncao et al., 2009). Based on this model and policy, data center can complete user’s task with minimal power consumption. Gang scheduling was introduced into cloud computing from parallel and distributed system (Moschakis and Karatza, 2012). Their results revealed that Gang scheduling could be effectively applied in a cloud computing environment both performance-wise and cost-wise. Cooperative co-evolutionary genetic algorithm (CCGA) was presented to solve the deadline-constrained resource allocation and scheduling problem for multiple composite web services (Ai et al., 2011). Experimental results showed that CCGA was both efficient and scalable.
An ant colony optimization was proposed based job scheduling algorithm, which adapts to dynamic characteristics of cloud computing and integrates specific advantages of ant colony optimization in NP-hard problems (Song et al., 2011).
| Fig. 2: | General composition of cloud computing |
Ant colony algorithm is a classical algorithm to solve the traveling salesman problem. When it was used in resource scheduling for cloud computing, the good results give us some inspiration. Could ant colony algorithm be used in seeking the best resource of cloud computing for WSN?
Ant colony algorithm: In 1990s, ant colony algorithm was first proposed by Dorigo and Gambardella (1997) and used in solving traveling salesman problem. The idea of ant colony algorithm comes from the study of searching capability of ant populations. Determining the best location by judging changes in pheromone concentration is the classic of ant colony algorithm.
At present, ant colony algorithm has been widely applied in many fields. Aimed at efficient transit schedule design of timing points, Mazloumi et al. (2012) had done a comparison of ant colony and genetic algorithms. Ant colony algorithm had been taken to solve the problem of multi-objective optimization study for job shop scheduling (Zeng et al., 2011). Mohammad (2011) proposed ant colony optimization technique for the sequence-dependent flowshop scheduling problem.
In most appeared ant colony algorithm, ants finished exchange by pheromone and direct exchange between the ants were not established. Therefore, the convergence of the algorithm is not high. To schedule resource for cloud computing better, more efficient ant colony algorithm is needed. In this study, the whole idea is that the best resource of cloud computing should be found for general node of WSN by ant colony algorithm. So their respective characteristics should be taken into account. Because the power supply of general node is shorter in WSN, cloud computing platform must return the results as soon as possible. However, cloud computing platform is so large that the best scheduling is difficult to be achieved in a short time. A three-step timing ant colony algorithm is proposed to schedule resource of cloud computing for general node in WSN.
PROPOSED METHOD
Limited by power supply, artificial ants can not be continuously sent from general node in WSN. A three-step timing ant colony algorithm is proposed to schedule resource of cloud computing for general node in WSN. Artificial ants were sent three times regularly. Role definition of artificial ant, pheromone definition and search strategy would be introduced one by one as following.
Role definition of artificial ant: In this study, the artificial ants are divided into three categories: information ant, positioning ant and task ant. These ants will be sent to cloud three times.
First, information ants are sent. The number of information ants is large. These ants are used in leaving pheromone to computing node which can satisfy the predetermined condition. After information ants were sent together, general node of WSN will start the timer and be in the power saving mode.
Second, positioning ants will be sent when timer reaches the specified time. Positioning ants are used in locating computing node which pheromone is high. After positioning ants were sent together, general node of WSN will start a new timer and power saving mode.
Third, task ants will be sent when all positioning ants come back. Task ants are used in convey task to the specific computing node and they will also carry processing results to general node in WSN. Structures of three ants are listed in Table 1.
Pheromone definition: Ants find path and search target depending on the concentration of pheromone. So of pheromone should be defined in ant colony algorithm. To general node in WSN, it need search the best computing resource from cloud. The quality of computing resources can be weighed by hardware and software level. Pheromone of hardware and software were defined respectively in this study. The definition of these pheromones is listed in Table 2.
| Table 1: | Structures of three ants |
| Table 2: | Pheromone definition |
The concentrations of these pheromones are shown as below:
| (1) |
where, hN0, hF0, hM0, hH0, hB0, ST0, SV0, are predefined threshold of hN, hF, hM, hH, hB, ST, SV.
The total concentration of the pheromone carried with an ant can be described as formula (2):
| (2) |
where, λ1+λ2+λ3+λ4+λ5+λ6+λ7 are weights of concentration components of all pheromones and λ1+λ2+λ3+λ4+λ5+λ6+λ7 = 1.
Search strategy: Based on different role of artificial ants, their search strategies are not the same. Three strategies were described as follow.
Search strategy of information ant: Information ant was used in assessing processing capacity of computing node in cloud and formed the pheromone of each computing node. When information ants were sent from general node in WSN, they would random search forward. During the search process, pheromone concentration would be left at every traversal node. If more information ants had traversed the same node, this node should be better performance. Here, formula (2) should be added a correction term and pheromone concentration should be improved. This correction result is shown as formula (3):
| (3) |
where, α is the traversal constant, n is the number of ants arrived at this node, τ' is the updated pheromone concentration.
Search strategy of positioning ant: Positioning ants were used in determining optimal computing node in cloud and recording the location and path information of this node. Only characterized static information of processing capability of each node was in formula (2). In order to express its dynamic information, CPU utilization should be considered when positioning ant reached a node. Thus, the definition of pheromone concentration is amended as follows:
| (4) |
where, β is the weight of CPU utilization, C is CPU utilization which range is from 0 to 100%, τ" is the updated pheromone concentration once again.
Because general node in WSN can not wait with power for a long time, positioning ants should return within the specified time. So, timer had been configured with each positioning ant. Before, time is half of the specified time, positioning ants can continue to search forward. When time is half of the specified time, positioning ants must return along with the same route in order that they can reach general node in WSN in time.
Search strategy of task ant: General node in WSN can only receive the returned positioning ants within the specified time. If more ants had returned within the specified time, those nodes would be selected as task-processing nodes which pheromone concentration is high.
When task-processing nodes were located, task ants would be sent to them. Task ants carry not only the information of the target node but also the threshold of pheromone concentration. If pheromone concentration of some node was higher than the threshold, current node would be updated as target node. If there were no new target nodes, task ant would go to the target node and convey the task to it. When task was completed by task node, task ant would take processing result to return general node in WSN.
Flow of algorithm: The whole flow of three-step timing ant colony algorithm is below:
| • | General node of WSN sends information ants and starts the first-step timer. Pheromone concentration of computing nodes of cloud will be initialized by information ants |
| • | When first-timer reaches the specified time, general node will send positioning ants. Second-step timer is configured with every positioning ant. When positioning ant is sent, its timer is also started. By introducing CPU utilization, positioning ants update pheromone concentration of traversal node. At the same time, related information of optimal computing node is also updated by the node with higher pheromone concentration |
| • | When second-step timer reaches half of the predefined time, positioning ants will backtrack. After positioning ants come back, pheromone concentration of computing node carried by every positioning ant will be compared and the top five will be selected as target node in cloud |
| • | Task ants are sent and the third-step timer is started by general node of WSN. Before task ant reaches predefined target node, target node can be updated by comparing pheromone concentration between current node and predefined target node |
| • | Target node is found or updated; task ant will transfer the task to this node. And task ant will wait at the target node until the task has been completed. After the task is finished, task ant will take the result to backtrack to general node in WSN |
EXPERIMENTAL RESULTS
In order to verify the effectiveness of the method proposed in this study, simulation software named CloudSim was selected as the experimental platform. One hundred of virtual machines were configured for cloud computing in CloudSim. General node of WSN was set to master node which can send task to cloud computing.
Parameter configuration: λ1, λ2, λ3, λ4, λ5 in the algorithm denotes the importance of CPU amount, CPU frequency, memory capacity external memory capacity and bandwidth respectively. λ6, λ7 denotes the importance of software type and software version.
Relatively, influence of other parameters is stronger than external memory capacity, software type and software version. So initial value of λ1, λ2, λ3, λ4, λ5, λ6, λ7 are set as 0.2, 0.2, 0.2, 0.1, 0.2, 0.05, 0.05. Value of hN0, hF0, hM0, hH0, hB0, ST0, SV0 are set as , 2.2 GHz, 4 G, 200 G, 5 m sec-1, 5, 8.
| Table 3: | Different combination and processing time |
The values of CPU amount, CPU frequency, memory capacity, external memory capacity and bandwidth are limited among 1-4, 1-4 GHz, 1-8 G, 100-300 G, 1-10 m sec-1.
Experimental results: The first experiment was used in determining the best operation mode of our method in CloudSim. That is, how much task can be finished fast when traversal constant α and weight of CPU utilization β had been given some value. α and β were given 0.1 or 0.05 and the size of task was given 50, 100, 150 and 200 m, respectively. Time of three timers was set as 5, 5, 10 sec-1. Different combinations and processing time is shown in Table 3.
From 16 groups of experimental results, processing effect is best when α was given 0.1 and β was given 0.05. At the same time, processing can be faster finished when size of task is 150 M. So, optimal operation of our method is that 150 M task is processed when α was given 0.1 and β was given 0.05.
Based on this optimal operation, second experiment was carried out. ACO1 and ACO2 scheduling strategy of ant colony algorithm were taken to compare with three-step timing ant colony algorithm proposed in this study. Because the scale of cloud computing did not change, first and second timer still was set as 5 sec in three-step timing ant colony. But third timer should change according to size of task. The corresponding calculation was like formula (5):
| (5) |
Where, T is the time, Size is the size of task.
The experimental result is shown as Fig. 3.
In Fig. 3, the horizontal axis indicates the size of task and the vertical axis represents the time that task is completed.
| Fig. 3: | Experimental results of comparison among three methods |
We can see that scheduling speed of three-step timing ant colony algorithm is higher than traditional ACO1 method and ACO2 method.
CONCLUSION
According to actual situation of general node in WSN, a new scheduling method was proposed for cloud computing resource. In fact, this method is an improved ant colony algorithm. Three types ants were used in resource scheduling. Information ants were used in sowing pheromone concentration on computing node. Positioning ants were used in positioning effective node. Task ants were used in sending task to effective node and taking processing result back to general node in WSN. Launching time and return time of three kinds ants were specified by three timers. When ants had been sent, general node of WSN would be in power saving state. Optimal parameters were selected in CloudSim platform. Experimental results showed that scheduling speed of three-step timing ant colony algorithm is higher than traditional ACO1 method and ACO2 method.