Abstract
Due to intrinsic properties of aqueous environments, routing protocols for underwater wireless sensor network (UWSN) have to cope with many challenges such as long propagation delay, bad robustness, and high energy consumption. Basic ant colony optimization algorithm (ACOA) is an intelligent heuristic algorithm which has good robustness, distributed computing and combines with other algorithms easily. But its disadvantage is that it may converge at local solution, not global solution. Artificial fish swarm algorithm (AFSA) is one kind of intelligent algorithm that can converge at global solution set quickly but has lower precision in finding global solution. Therefore we can make use of AFSA and ACOA based on idea of complementary advantages. So ACOA-AFSA fusion routing algorithm is proposed which possesses advantages of AFSA and ACOA. As fusion algorithm has aforementioned virtues, it can reduce existing routing protocols' transmission delay, energy consumption and improve routing protocols' robustness theoretically. Finally we verify the feasibility and effectiveness of fusion algorithm through a series of simulations.
1. Introduction
Rapid evolvement of wireless communication technology, electronic technique, sensor technology, micro-electro-mechanical system, and other computer technologies promotes research in wireless sensor network. Underwater wireless sensor network (UWSN), one kind of special and promising wireless sensor network, gains more and more attention. With the development of ocean exploitation, UWSN is becoming one of hot topics in research fields. UWSN is the development trend of future underwater communication and detection techniques, for instance, seabed resource detection and exploration, oil spill, tsunami, underwater earthquake, and underwater environment monitoring. Therefore we can say that marine development degree determines future world development degree while UWSN determines marine development.
Electromagnetic wave and light wave are not suitable for underwater communication since their signals can be absorbed by water. As wavelength of acoustic wave is long enough and it is cost effective, acoustic communication is the only ideal medium for underwater information transmission. That is to say, acoustic communication is the best communication style for UWSN to date [1]. However the transmission condition of ocean acoustic channel is terrible, and there are so many interference factors that disturb such information transferring [2]. Besides UWSN is disposed in interesting aquatic area which means nodes of UWSN are mobile and delicate easily. And above all, each node of UWSN carries limited energy and it is impossible to replace its battery. All of those afore-mentioned characteristic are huge challenge for the realization of UWSN. As most traditional land-based wireless sensor networks routing protocol and other energy-based routing protocols are designed for stationary network, they are not applicable to UWSN whose network topology is dynamic. Therefore UWSN routing protocol is becoming a hot spot in the field. The design principle of UWSN routing protocol is the same as WSN—low energy consumption [3]. UWSN is a kind of three-dimensional dynamic, sparse networks, so it is important to take such characteristics into consideration in devising underwater routing protocol. In other words, underwater routing protocol algorithm should have these following advantages: energy efficiency, short transmission path, and robustness.
Ant colony optimization algorithm (ACOA) is one kind of heuristic bionic algorithm based on ant colony finding its way in the population's foraging process. ACOA algorithm is parallel algorithm in essence that has the following features: robustness, universality, fast convergence, easiness of combining with other algorithm, and so forth [4, 5]. However ACOA may converge at local optimal solution for the algorithm refreshes local pheromones, so some improvements need to be taken to optimize ACOA for its application in UWSN. Compared with ACOA, AFSA converges at global solution better and is insensitive to parameters [6, 7]. So we can take advantage of AFSA to optimize ACOA, and apply the fusing algorithm based on ACOA, and AFSA to the routing protocol of UWSN, which can improve protocol's robustness and energy efficiency.
The remainder of the paper is organized as follows. In Section 2 we present related work. In Section 3, we present AFSA-ACOA fusion algorithm which includes introduction of ACOA, AFSA, the ACOA-AFSA fusion algorithm, the implementation, and its application in optimizing routing protocol of UWSN. Section 4 mainly gives details for the simulation and analysis of the simulation result. At last Section 5 concludes the paper.
2. Related Work
Lv et al. [8] provided a research review of mobile underwater wireless sensor network. It included the following contents: node's design of underwater wireless sensor network, nodes interconnection and dynamic network, nodes' location in three-dimensional environments, and acoustic channel link control. But Lv et al. did not pay much attention to UWSN's routing protocol, not to say the research about its optimization making use of some algorithms. Guo et al. [9] did the similar work as Lv et al. Meanwhile Guo introduced some research work with respect to routing protocol of UWSN. He said underwater routing protocol could be divided into three categories: initiative routing protocol, on-demand routing protocol, and routing based on geography. But Guo et al. did not present research about optimal algorithms for UWSN's routing protocol.
Yanhua [1] proposed time-sharing balance routing algorithm based on network coding for UWSN. It is one kind of improvement flooding algorithm. The routing protocol had the following characteristics: (a) children nodes need not to response to their father nodes in routing establishment process; they would broadcast their routing data packets which could be considered as acknowledgment to their father's requirement. Such activity saved time and energy effectively. What is more, the action reduced conflicts probability in sending data packets significantly. (b) Probability balance mechanism was given to regulate every communication cluster's children nodes. Thus each node's overhead in the routing tree was equivalent. (c) After establishment of routing tree, data packets received by nodes were encoded into one encoding, compressed data packet. Such encoding technique reduced node's energy cost and improved network bandwidth's utilization ratio, prolonged network's lifetime. Xiao et al. [10] reported the ongoing efforts of their research toward developing an analytic model to address the performance of contention-based protocols within the context of underwater acoustic sensor networks. They identified the challenges of modeling contention-based MAC protocols and present models for analyzing ALOHA and p-persistent ALOHA variants for a simple string topology.
Qiliany and Liping [11] took sensor nodes' limited energy, communication into account, and he proposed one routing protocol based on improved optimal ant colony algorithm. The algorithm considered node's residual energy, communication distance, and other factors fully in routing list; it gathered ants' searching activities near optimal solution successfully. To avoid accident of premature convergence, the algorithm restricted range of pheromones. But the algorithm is suitable for land-based wireless sensor network. Similarly, Xuhua et al. [12] discussed a new routing approach based on ant colony optimization algorithm to obtain the optimal path between two nodes in network. The algorithm increased formulas' sensibility to impact factors, thus the algorithm's convergence speed was raised largely. Xiangguang et al. [13] posed a new hybrid evolutionary algorithm based on artificial fish swarm algorithm and particle swarm optimization algorithm. The core is such algorithm took advantage of ASFA's global convergence to find range of satisfied solution firstly, then it employed PSO algorithm to get local optimal solution quickly. So the hybrid method had features of quick local searching speed and global convergence. For the multiple QoS constrained unicast routing problem, a new QoS routing algorithm combining modified ant colony algorithm with artificial fish swarm algorithm was proposed by Mingjia et al. [14]. It adopted hybrid ant behavior to produce diverse original paths, optimizing the choice nodes set according to multiple QoS constrained, adding AFSA to MACA's every generation, making use of AFSA's advantage of whole quick convergence, ACA's convergence speed was quickened, and AFSA's preying behavior improved the ability of MACA to avoid being premature.
Muhammad Ayaz and Abdullah [15] proposed a Hop-by-Hop Dynamic Addressing Based (H2-DAB) to provide scalable and time-efficient routing for UWSN. The H2-DAB routing does not require any dimensional location information or any extra specialized hardware compared with many other routing protocols in the same area. Domingo and Prior [16] presented GPS-free Routing Protocol for UWSN in deep water. It minimized the proactive routing message exchange and compensated the high propagation delays of the underwater medium using a continually adjusted timing advance combined with guard time values to minimize data loss and maintain communication quality. Huang et al. [17] proposed a self-healing clustering algorithm which combined the ideas of energy-efficient cluster-based routing and application-specific data aggregation. The self-healing mechanism significantly enhanced the robustness of clustered UWSNs.
The aforementioned researches are closely related with sensor network routing and its algorithms. As characteristics of subaqueous environments, routing algorithms with short propagation delay, good robustness, low energy consumption, and high network throughput can be really challenged for UWSN. To address the above-mentioned challenges, we propose one hybrid ACOA-AFSA routing algorithm for underwater wireless sensor network.
3. ACOA-AFSA Fusion Algorithm and Its Application in Optimization of UWSN's Protocol
3.1. Introduction of ACOA and AFSA
Ant will leave pheromones in their passing roads so that other ants can find the previous ants easily. What is more, ant is going to take the path which has higher pheromones, left by other ants, than other pathways nearby. So ant colony can find their end readily with the help of pheromones' positive information feedback. That's to say, although ant is nonintelligent species, activities of ant colony represent living intelligent. Advantages of ACOA are self-organization, distributed process, positive feedback, and good robustness. Thus ACOA is suitable for solution of NP-hard problems like routing protocol in UWSN. But we notice that ACOA may converge at local optimal solution instead of global optimal solution sometimes.
Fish can find specific areas that are rich in nutrients in their living waters by themselves or tagging along with other fish quickly. Thus the area that has the greatest number of fish is the most nutritious area in the water. According to the characteristics, artificial fish swarm algorithm is proposed by Xiaoli [6]. Artificial fish swarm algorithm (AFSA) can get global solution effectively by simulating activities of fish swarm's foraging, clustering, and rear ending. AFSA has simple algorithm model and strong abilities of getting out of local solution, converging at global solution. However the AFSA can hardly get high-accuracy solution sometimes. Besides in the foraging stage of AFSA, individual artificial fish may choose some new status randomly if the fish cannot get better status than current state. That means previous beneficial information is not used fully. Thus advantages and disadvantages of AFSA can be used and made up by ACOA.
3.2. Introduction of Fusion Algorithm
Basic idea of the fusion algorithm is that fusion algorithm takes artificial fish swarm algorithm as subject, and it introduces idea of ant colony optimization algorithm. So ant colony algorithm takes advantage of AFSA's speediness and global solution to fulfill quick convergence and get global solution. At the same time ACOA covers disadvantages of AFSA. As ACOA has strong ability of positive feedback for ants search for pheromones left by previous ants fully, every next state of ACOA will be better than its current status. Such superiority can cover disadvantage of AFSA effectively. With ACOA's calibration, AFSA can modify its routing path more slightly and accurately.
3.3. Implementation of Fusion Algorithm See [18]
AFSA can get optimal solution domain quickly with lower precision. Meanwhile an important feature of ACOA is that the algorithm makes use of pheromones' positive feedback to choose optimal solution. Thus based on the idea of offsetting each other's weakness, ACOA-AFSA fusion algorithm is proposed which can converge at optimal solution effectively and quickly. To summarize the realization of the proposed fusion routing algorithm, fish swarm tries to find routing path through data delivering from source node to destination node. And each node in the routing path then compares its energy, path length with nearby nodes with the assistance of ACOA algorithm. Algorithm's basic steps are as follows while its flow diagram is shown in Figure 1.
Fusion algorithm's flow diagram.
(a) Parameters' initialization: both parameters of ant colony algorithm and AFSA are initialized. They are shown as follows. Parameters in ant colony algorithm: pheromone evaporation factor ρ, pheromone level Q, number of ants K, maximum iteration number for ant colony algorithm Max, pheromone heuristic factor α. Parameters in AFSA: fish's step length S, visual radius and bulletin board's content, population quantity, crowding factor δ, and so on.
(b) i, identifier number of fish, increments one.
(c) Implement foraging activity. Fish swarm implements activity of foraging to test whether next status is better than current status. If so, the fish swarm implements foraging activity. If not AFSA will perform next activity: clustering activity. The logic formula of environment consistence is shown
(d) Implement clustering activity. fish swarm implements activity of clustering to test whether next status is better than current status. If so, the fish swarm implements foraging activity. If not AFSA will perform next activity: following activity. The activity of clustering is similar with foraging activity. First fish i percepts the number of fish in its visual range and the fish's visual range forms set of visual_fish
Fish i will implement clustering activity if those two conditions are met: (1)
(e) Implement following activity: fish swarm implements activity of following to test whether next status is better than current status. If so, the fish swarm implements foraging activity. If not AFSA will perform next activity: random activity. The following activity is an activity that fish tries to get closer to fish state that has minimum consistence. Certainly following activity will be implemented if the following conditions are met:
Similarly the two conditions indict that
So the same work is done to improve environment consistence like foraging activity and clustering activity. At last AFSA updates content of bulletin board.
(f) Random activity: if none of foraging activity, clustering activity, and following activity is implemented, then random activity is executed. The calculation formula for next step of fish is shown in expression (9). As shown in flow diagram, next step is to judge whether fish swarm gets optimal solution or AFSA reaches maximum iterations. If not, algorithm jumps to step b and implement circle successively:
(g) ACOA optimizes the path set from AFSA. Although AFSA has strong ability of finding optimal solution set, its disadvantage is that it has lower precision of obtaining optimal solution in optimal solution set. Because of the aforementioned reasons, we use ACOA to acquire optimal solution from the solution set that outputted from AFSA. Firstly taboo list in ACOA is initialized by solution set of AFSA and ant colony is the same as fish swarm.
(h) Searching for next node and transferring path: we use taboo list
(i) Path pheromone update. Pheromones level in each path that ants have passed by is refreshed in specific algorithm to induce more ants select the path. The update policy as follows:
In formula (12), Q represents pheromones' level; it affects convergence speed to some extent.
(j) Loop condition judgment: if whole ant colony walks around the same and the only one route to destination, or number of iterations reaches the maximum iterations set by the algorithm, the ant colony algorithm stops. Otherwise algorithm will jump to step h and continue the search for next path. Pseudo-code block of fusion algorithm's about AFSA's initialization as is in Algorithm 1.
{X = afinit (afNum,varNum,Xl,Xh,lchrom);
%initialization of AFSA
for i
temp=[X(i,1),X(i,2)];
Tempconsistence(i)=functionconsistence(temp,
simmodel);
end
foodconsistence=tempconsistence′;
% calculate food density
[a,b]=max(foodconsistence);
Xmax=[X(b,1),X(b,2)];
Ymax=a;
%initialize bulletin board
k=0;
visualweak=0;
while(k<iterativeTime)
for i=1:afNum
Xi=[X(i,1),X(i,2)];
%current status of fish i
nf1=0;
Xc=0;}
Algorithm 1
3.4. Issue Description and Solution
Usually UWSN consists of many underwater nodes for monitoring underwater environments. But characteristics of underwater environments, such as long propagation delay, multipath interference, and limited channel width, decrease UWSN's network performance. Nodes and network link may join in UWSN or be unusable at any time. Namely, protocols of UWSN may have bad robustness, higher energy consumption, longer transmission delay, lower throughput of network, and so forth.
Thus efficient routing protocol algorithm for UWSN should resolve the aforementioned deficiencies effectively. The conspicuous characteristics of efficient routing algorithm are that the algorithm has autocatalysis and positive feedback mechanism. Fusion algorithm proposed in this paper is the very algorithm that possesses the aforementioned characteristics. As fusion algorithm is based on ant colony algorithm and artificial fish swarm algorithm, the fusion algorithm has advantages of both algorithms like positive feedback mechanism, self-adaptive mechanism, converging at global solution quickly, and good robustness.
Fusion algorithm's self-adaptive mechanism enhances robustness of UWSN's routing protocol. In this case routing protocol will not be affected if partial nodes become invalid or some network links are disabled suddenly. Thus robustness of routing protocol is strengthened. What is more, the positive feedback mechanism makes message routes from source node to destination node in shortest path. That means overhead of information routing will be decreased naturally. The more nodes deployed in acoustic environment and further distance that message need to be delivered, the more overhead will be saved. Taking all the aforementioned contents into consideration, we can employ the fusion algorithm to improve UWSN's network robustness, reduce its energy consumption and propagation delay. Because of reasons given above, we will use ACOA-AFSA fusion algorithm for finding optimal link in UWSN.
For simplicity, we give communication links in protocol table of UWSN as shown in Figure 2. Node A is the source node and node D is sink node while node E is destination node. The distance between AB, BC, CD, DE, AH, HF, FG, GE, BH, LE, LD, DG is 10, 6, 10, 12, 8, 15, 18, 17, 5, 5, 9, 5, 16, respectively. Firstly fish swarm computes food density in the environment. That is to say, each fish in the population will implement foraging activity, clustering activity, following activity, or random activity to choose next node to jump according to formulas from (1) to (9). So after the fish swarm finishes the first circle, most fish will choose node H and node B as their next node, while only little fish will choose node I as their next node. So the optimal bulletin will record H and sub-optimal board will record B as their content. Then the fish swarm continues to find next node based on their current position until they arrive at node D which is a sink node. Next we extract the content in two bulletin boards. The path in optimal-board is A-H-B-C-D while the path in sub-optimal board is A-B-C-D. Then we use ACOA to choose which path is the real shortest path. Paths in optimal board and sub-optimal board form solution set. The source node and destination node in ACOA are node A and node D, respectively. Then ants walk along the given routes from source node to destination node. As The length of path A-B-C-D is 26 and the length of path A-H-B-C-D is 29. As a result, more and more ants will choose path A-B-C-D than path A-H-B-C-D as their route to destination. The whole ant colony will choose A-B-C-D as their walking path eventually. And the process of choosing path from D to E is similarly with choosing path from A to D. So the final routing path is A-B-C-D-E and the whole length of the path is 38.
Topology link of UWSN.
4. Simulation and Analysis
4.1. Simulation Setup
We ran series of simulations to evaluate performance of the proposed algorithm by comparing with other popular algorithms which were discussed in Section 3.2 concretely. In the series of experiment, 1000 nodes are randomly deployed in underwater environment in
4.2. Simulation Scheme
The simulation experiments were realized through C++ to verify feasibility and validity of the proposed algorithm. The compared schemes during the simulations included the proposed ACOA-AFSA fusion algorithm, a representative clustering algorithm called low-energy adaptive clustering hierarchy (LEACH) [24], classic routing protocol for underwater sensor networks named vector-based forwarding (VBF) [25].
We compared the three algorithms in the following aspects. (1) energy consumption: we compared energy consumption in the same application and condition, such as same nodes, same velocity, same packets need to be delivered. (2) Loss ratio of data packets: we got each algorithm's packets loss probability through quantity loss of the sent packets and received packets between same source node and destination node in same application and condition, such as same nodes, same velocity, and same packets that need to be delivered. (3) Propagation time and delay: propagation time and delay were measured by transmission time of data packets from same source node and destination node in the same application and condition such as same nodes, same velocity, same packets need to be delivered.
4.3. Simulation Results and Analysis
(a) Energy Consumption Comparison
Figure 3 shows the number of data received at sink nodes over different energy consumption level. In fact both algorithms of VBF and LEACH have intrinsic drawback of limited receiving capacity. Figure 3 reveals that LEACH protocol's largest capacity is 4200 approximately while VBF is 2500 data packets. The proposed routing protocol in the paper does not have such imperfection. Mainly reasons for the aforementioned phenomenon can be summed up as follows: (a) LEACH protocol assumes the nodes chosen as clustering randomly without considering energy state, and it presumes cluster nodes are scattered in monitoring area evenly. As a matter of fact, not all of the message collected by nodes in cluster can be sent to sink nodes correctly and effectively in the real and complicated monitoring area. Sometimes part of monitoring area is full of monitoring nodes but no clustering nodes, thus the information collected by spot nodes cannot be transferred and relayed in time. As a result, energy consumption of LEACH protocol is proportional to the amount packets while data packets fall short of protocol's theoretical maximum. LEACH's energy consumption increases while its packets remain unchanged if protocol reaches its maximum limitation. (b) In basic VBF protocol, nodes that near sink nodes think they are authorized to deliver and relay data packets. Thus same data packets may be transferred several times which means the protocol has the lowest capacity of receiving valid data packets. (c) The proposed fusion algorithm ACOA-AFSA can achieve much more data traffic with less energy consumption lies in such a fact; ACOA-AFSA algorithm makes use of biological intelligence to find global path for information delivery in minimum duration. What is more, the proposed algorithm can adaptively select the best route to transmit data if network topology changes. Given the reasons above, the proposed algorithm performs better than the other two algorithms. As ACOA-AFSA algorithm has the best routing path for data transmission, number of total data packets received at sink node is the largest for certainty. VBF and LEACH perform worse than ACOA-AFSA algorithm. VBF protocol takes data forwarding as its most important task if monitoring network is large enough, which results in VBF protocol's higher network load. That is to say, utilization ratio of VBF protocol's network is pretty lower which leads to lower sink node's lower data reception. As clustering nodes are selected randomly in LEACH protocol, some selected clustering nodes are not fit for the mission as their energy is lower. In other words some clusters may lose their clustering nodes easily for the selected nodes' lower energy, which brings about sink node lower data reception. Figure 4 proves the proceeding discussion.
energy consumption versus data receive at sink node.
Total data packets received at sink node.
(b) Loss Ratio of Data Packets
Figure 5 shows VBF and LEACH have higher packets dropping rate even if nodes have sufficient energy for data receiving and transmitting. The main reasons for such phenomenon is that VBF and LEACH are easily affected by dynamic and complicated underwater environment. Besides in VBF protocol nodes only near routing vector can transmit data which means VBF protocol has lower network usage ratio. As a result loss rate of VBF is largest among three UWSN routing protocol. LEACH protocol allows clustering node to realize the data transmission while nonclustering nodes can restore their energy for the next data transmission. Thus LEACH protocol performs better than VBF protocols. For the same reason, clustering nodes, which is chosen randomly in LEACH protocol, are easy to fail as they execute the assignments which consume a lot of energy. After several data transmission circles, energy distribution is extremely unevenly distributed. So nodes' energy in some monitoring regions is super small that means data delivery in the area is likely to fail. Through our experiment, it can be revealed that ACOA-AFSA gets the least data dropping probability. Such an outperformance may exist owing to ACOA-AFSA's global and local view of the whole network topology. And simultaneously, the self-adaptive switching of ACOA and AFSA causes less energy consumption during the disruption of the clusters resulting in deterioration of the performances.
Packet dropping rate versus remaining energy.
(c) Average Delay
We have also conducted the simulation to observe the average delay over number of nodes, namely, the relationship between network scale and average delay. VBF protocol is kind of UWSN routing protocol that performs well while scale of network is small. The major reason is that VBF protocol empowers most nodes in network to transfer data with less data retransmission if UWSN is dense network. As nodes' number increases, the protocol's shortage of data retransmission handicaps network's normal operation of data receiving and delivering seriously. Simulation result in Figure 6 testifies aforementioned VBF protocol's merits and demerits as well. What is more, Figure 6 demonstrates that ACOA-AFSA fusion algorithm could lower the average delay more with number of nodes increasing. The reason that ACOA-AFSA performs better than VBF is that the self-adaption mechanisms have been incorporated into the protocol. So, the routine efficiency is not so sensitive to the network scale and the scalability is thus optimized.
Average transmission delay versus number of nodes.
5. Conclusion
In this paper, a novel ACOA-AFSA fusion algorithm for UWSN routing protocol has been presented. It is a useful routing algorithm for underwater sensor networks owing to its local acknowledge and global view offered by ACOA and AFSA, respectively. The proposed algorithm also introduces a self-adaptive mechanism to fuse such two algorithms for searching better routing path. ACOA algorithm's parallel feature makes routing search in proposed protocol quickly. As AFSA algorithm finds candidate optimal routing path roughly in the fusion algorithm for optimizing and ACOA algorithm helps AFSA to calibrate routing path, fusion algorithm's robustness is stronger than VBF and LEACH. The fusion algorithm's global view and local optimal routing path makes its energy consumption for data transmission and reception more efficiently. With the increment of nodes and iteration number, advantages of swarm intelligence play greater role in finding best transmission route as well. The whole train of simulations proves ACOA-AFSA routing algorithm outperforms VBF and LEACH marginally in the way of energy consumption, packet loss rate, and delay. For future research work in the field, we will devote our efforts to the optimal tuning of parameters in ACOA and AFSA algorithm to realize the optimal performance in underwater wireless sensor network's data routing.
Footnotes
Acknowledgments
This paper was supported by Foundation of Shanghai Maritime University (20110028), Shanghai Science and Technology Committee Program (11PJ1404300, 09170502000), Shanghai Leading Academic Discipline Project (S30602), and a Grant from the National Natural Science Foundation of China (40801174).