extfieldsofstudy:
Computer Science
Engineering

text:
Synchronization of a class of cyclic discrete-event systems describing legged locomotion

It has been shown that max-plus linear systems are well suited for applications in synchronization and scheduling, such as the generation of train timetables, manufacturing, or traffic. In this paper we show that the same is true for multi-legged locomotion. In this framework, the max-plus eigenvalue of the system matrix represents the total cycle time, whereas the max-plus eigenvector dictates the steady-state behavior. Uniqueness of the eigenstructure also indicates uniqueness of the resulting behavior. For the particular case of legged locomotion, the movement of each leg is abstracted to two-state circuits: swing and stance (leg in flight and on the ground, respectively). The generation of a gait (a manner of walking) for a multiple legged robot is then achieved by synchronizing the multiple discrete-event cycles via the max-plus framework. By construction, different gaits and gait parameters can be safely interleaved by using different system matrices. In this paper we address both the transient and steady-state behavior for a class of gaits by presenting closed-form expressions for the max-plus eigenvalue and max-plus eigenvector of the system matrix and the coupling time. The significance of this result is in showing guaranteed robustness to perturbations and gait switching, and also a systematic methodology for synthesizing controllers that allow for legged robots to change rhythms fast.

I. INTRODUCTION
Synchronization of cyclic processes is important in many fields, including manufacturing [51], transportation [31], genomics [48], and neuroscience [34,50], etc (see references within [13]). In this paper we focus on a class of multiple concurrent two-state cyclic systems with a direct application to legged locomotion. Our motivation is the requirement of legged mobile robots to cope with unstructured terrains in a flexible way by smoothly and effectively switching between different gaits.
Legged systems are traditionally modeled using cross-products of circles in the phase space of the set of continuous time gaits. Holmes et al. [34] give an extensive review of dynamic legged locomotion.
The central pattern generator [35] approach to design motion controllers lies in assembling sets of error functions to be minimized that cross-relate the phases of multiple legs, resulting in attractive limit cycles for the desired gait. Switching gaits online is typically not addressed since in the central pattern generator framework switching must be modeled as a hybrid system. Additionally, implementing "hard constraints" on the configuration space [29] can be quite complex mainly due to the combinatorial nature of the gait space, and often it comes at the cost of dramatically increasing the complexity of the controller.
As an alternative to the common continuous time modeling approach, we introduce an abstraction to represent the combinatorial nature of the gait space for multi-legged robots into ordered sets of leg index numbers. This abstraction combined with max-plus linear equations allows for systematic synthesis and implementation of motion controllers for multi-legged robots where gait switching is natural and the translation to continuous-time motion controllers is straightforward [38]. The methodology presented is particularly relevant for robots with four, six, or higher numbers of legs where the combinatorial nature of the gait space starts to play an important role. For a large number of legs it is not obvious in which order each leg should be in swing or in stance. Most legged animals, in particular large mammals, are known to walk and run with various gaits on a daily basis, depending on the terrain or how fast they need to move. The discrete-event framework presented in this paper enables the same behavior for multi-legged robots. Mathematical properties are derived for this framework, giving extra insight into the resulting robot motion.
The main mathematical representation employed in this paper are switching max-plus linear equations.
By defining the state variables to represent the time at which events occur, systems of linear equations in the max-plus algebra [1,11,32] can model a class of timed discrete-event systems. Specifically, max-plus liner systems are equivalent to (timed) Petri nets [44] where all places have a single incoming and a single outgoing arc. Max-plus linear systems inherit a large set of analysis and control synthesis tools thanks to many parallels between the max-plus-linear systems theory and the traditional linear systems theory. Discrete-event systems that enforce synchronization can be modeled in this framework. Max-plus algebra has been successfully applied to railroads [3,31], queuing systems [30], resource allocation [19], and recently to image processing [2] and legged locomotion [38,39].
The contributions of this paper are the following: we present a class of max-plus linear systems that realize the synchronization of the legs of a robot. Next, we derive closed-form expressions for the maxplus eigenvalue and eigenvector of the system matrix, and show that the max-plus eigen-parameters are max-plus unique, implying a unique steady-state behavior. This result is then used to compute the coupling Existence of eigenvalue and eigenvector (algebraic computation, Lemma 11) Coupling time (algebraic computation, Lemma 16) Transient Irreducibility (matrix structure, Lemma 12) Unique eigenvalue (Corollary 13) Single strongly connected subgraph (graph approach, Unique eigenvector (Theorem 15) Existence Uniqueness Steady-state time, which characterizes the transient behavior. The importance of having closed-form expressions and uniqueness of the max-plus eigen-structure is that, not only can one compute these parameters very fast without recurring to simulations or numerical algorithms (e.g. Karp's algorithm [1]), but one has also guarantees of uniqueness: the motion of the robot will always converge in a finite number of steps to the same prescribed behavior, regardless of gait changes or disturbances. This reassurance is fundamental when designing gait controllers for robotics. Additionally we present a low least number of steps needed to reach steady-state motion after changing gaits. This paper is focused on the general mathematical properties of a class of discrete-event systems that describe legged locomotion, and not on the actual implementation of gait controllers for robots, as presented previously in [38].
In Section II we revisit the fundamentals of legged locomotion with special emphasis on gait generation and show that max-plus algebra can be used in the modeling of the synchronization of multiple legs. In Section III we briefly review relevant concepts from the theory of max-plus algebra and in Section IV we present a class of parameterizations for the gait space. Given such class, we derive a number of properties, such as the max-plus eigen-structure of the system matrices (Section IV-C), their graph representation (Section IV-D), and the coupling time (Section IV-E). Figure 1 illustrates the structure of the contributions presented in this paper.
Modeling of legged locomotion. a) The configuration space of two oscillators is a torus. Synchronization is achieved by constructing attractive limit cycles, represented by the curve on the torus. b) Discrete-event representations of multiple circuits can be modeled as concurrent cyclic Petri nets. Synchronization is achieved by adding extra places, represented by s2 and s2.

II. MODELING LEGGED LOCOMOTION
In literature [14,28,34,45,46], the study of legged locomotion is approached from two main directions: the signal generation side, where emphasis is placed on the classes of signals that result in periodic locomotion behavior independent of the physical platform; and the mechanics side, where the (hybrid) Newtonian mechanics models are analyzed independently of the driving control signal. We focus on the first approach, by restating the traditional view of periodic gaits for legged systems being defined in the n-torus: Cartesian products of circles each representing an abstract phase that parameterizes the position of each leg in the Euclidean space. Such an abstraction serves as a platform for the models of "networks of phase oscillators" and central pattern generators, introduced in the earlier works of Grillner [27] and Cohen et al. [5]. These are now accepted by both biology and robotics communities as standard modeling tools [34].
In this paper we abstract beyond the notion of a continuous phase to consider concurrent circuits of discrete events. Taking a Petri net modeling approach, during ground locomotion the places represent leg stance (when the foot is touching the ground and supporting the body) and leg swing (when the foot and all parts of the leg are in the air). The transitions represent leg touchdown and lift off. This labeling is most convenient for ground locomotion, but one should be aware that the framework presented in this paper is valid for other types of locomotion where the phases of the various limbs need to be synchronized, such as swimming or flight. Figure 2 illustrates the conceptual difference between our approach ( Figure   2.b) where each phase is represented by a circuit in the discrete-event systems domain and the traditional continuous phase central pattern generator (Figure 2.a). Here, phase synchronization is enforced on the torus by implementing controllers that achieve stable limit cycles [37]. In this paper we translate timed event graphs 1 into the equivalent representation as max-plus linear systems, and achieve synchronization 1 We restrict ourselves to a class of timed Petri nets called timed event graphs such that a one-to-one translation to max-plus linear systems is possible (see [32], chapter 7). In timed event graphs each place can have one single incoming arc and one single outgoing arc. . 3. Illustration of a walking pattern, photos by Muybridge [40]. The solid bars, following Hildebrand's diagram notation [33], indicate that the leg is in stance (foot touching the ground) for τg time units, and white space that the leg is in swing (foot in flight) for τ f time units.
The time length when both feet are touching the ground is called the double-stance time τ∆. We use the notation t1(k − 1) to represent the time instant when leg 1 (left leg) touches the ground, and l1(k) when it initiates a swing. The parameter k is the "step counter". by designing the system matrices appropriately. Consider the leg synchronization of a biped robot. In this case, only two legs need to be synchronized during locomotion. For a typical walking motion (no aerial phase) the left leg should only lift off the ground after the right leg has touched down, to make sure the robot does not fall due to lack of support. This simple synchronization requirement can be captured by introducing state variables for the transition events defined as follows: let l i (k) be the time instant leg i lifts off the ground and t i (k) be the time instant it touches the ground, both for k-th iteration, where k is considered to be a global event or "step" counter. Enforcing that the time instant when the leg touches the ground must equal the time instant it lifted off the ground for the last time plus the time it is in swing A similar relation can be derived for the lift off time: where τ g is the stance time and t i (k − 1) refers to the previous iteration such that equations (1) and (2) can be used iteratively. For this system we have that τ f > 0 and also τ g > 0. Synchronization of the cycles of two legs can be achieved by introducing a double stance time parameter, denoted τ ∆ , representing that after each leg touchdown both legs must stay in stance for at least τ ∆ time units (see Figure 3). This is captured by the following equations: Equation (3) enforces simultaneously that leg 1 stays at least τ g time units in stance and will only lift off at least τ ∆ time units after leg 2 has touched down. When both conditions are satisfied, lift off takes place.
Equation (4) is analogous for leg 2. Note that the parameters τ f , τ g , and τ ∆ are in fact the minimal swing, stance, and double stance times, respectively, as opposed to the exact times. Note additionally that these equations are non-linear but they rely only on the "max" and "plus" operations. This motivates the use of the theory of the max-plus algebra to find parsimonious discrete-event models for legged locomotion.
Although the previous set of equations were designed for a walking behavior with no aerial phases, in practice they can also be used for running by choosing the double stance time to be negative, i.e. by enforcing that one leg lifts off τ ∆ time units before the other leg touches the ground. However, the results presented in this paper focus on the case when τ ∆ 0 such that stability (in the sense of ensuring a desired minimum number of legs on the ground simultaneously) is guaranteed.

III. MAX-PLUS ALGEBRA
In the early sixties the fact that certain classes of discrete-event systems can be described by models using the operations max and + has been discovered independently by a number of researchers, among whom Cuninghame-Green [9,10] and Giffler [21][22][23]. These discrete-event systems are called maxplus-linear systems since the model that describes their behavior becomes "linear" when formulated it in the max-plus algebra [1,11,32], which has maximization and addition as its basic operations. More specifically, discrete-event systems in which only synchronization and no concurrency or choice occur can be modeled using the operations maximization (corresponding to synchronization: a new operation starts as soon as all preceding operations have been finished) and addition (corresponding to the duration of activities: the finishing time of an operation equals the starting time plus the duration). Some examples of max-plus linear discrete-event systems are production systems, railroad networks, urban traffic networks, queuing systems, and array processors [1,11,32].
An account of the pioneering work of Cuninghame-Green on max-plus system theory has been given in [11]. Related work has been done by Gondran and Minoux [24][25][26]. In the eighties the topic attracted new interest due to the research of Cohen, Dubois, Moller, Quadrat, Viot [6][7][8], Olsder [41][42][43], and Gaubert [15][16][17], which resulted in the publication of [1]. Since then, several other researchers have entered the field. For an historical overview we refer the interested reader to [12,20,32]. In this section we give an introduction to the max-plus algebra. This section is based on [1,11], where a complete overview of the max-plus algebra can be found. The basic operations of the max-plus algebra are maximization and addition, which will be represented by ⊕ and ⊗ respectively x ⊕ y = max(x, y) and x ⊗ y = x + y, for x, y ∈ R max := R ∪ {−∞}. The zero element for ⊕ in R max is ε := −∞ and the unit element for ⊗ is e := 0. The structure (R max , ⊕, ⊗) is called the max-plus algebra [1,11]. The operations ⊕ and ⊗ are called the max-plus-algebraic addition and max-plus-algebraic multiplication respectively since many properties and concepts from linear algebra can be translated to the max-plus algebra by replacing + by ⊕ and × by ⊗.The max-plus algebra is a typical example of a class of algebraic structures called commutative dioids. In a dioid the additive operation ⊕ is associative, commutative, and idempotent, and it has a zero element; the multiplicative operation ⊗ is commutative and associative and it has an identity element; the additive zero element is absorbing for ⊗; and ⊗ is left and right distributive w.r.t. ⊕. Let r ∈ R. The rth max-plus power of x ∈ R is denoted by x ⊗r and corresponds to rx in conventional There is no inverse element for ε since ε is absorbing for ⊗. If r > 0 then ε ⊗r = ε. If r < 0 then ε ⊗r is not defined. In this paper we have ε ⊗0 = 0 by definition. The rules for the order of evaluation of the max-plus operators are similar to those of conventional algebra. So max-plus power has the highest priority, and max-plus multiplication ⊗ has a higher priority than max-plus addition ⊕. Throughout this paper the i, j element The matrix E n is the n by n max-plus identity matrix: We also define the m by n max-plus "one" matrix 1 m×n such that [1] ij = e = 0 for all i, j. If the dimensions of E, E, 1 are omitted in this paper, they should be clear from the context. The basic max-plus-algebraic operations are extended to matrices as follows.
for all i, j. Note the analogy with the definitions of matrix sum and product in conventional linear algebra.
The max-plus product of the scalar α ∈ R max and the matrix A ∈ R m×n max is defined by [α⊗A] ij = α⊗[A] ij for all i, j. The max-plus matrix power of A ∈ R n×n max is defined as follows: A ⊗0 = E n and A ⊗p = A⊗A ⊗p−1 for p 1.
Theorem 1 (see [1], Th 3.17). Consider the following system of linear equations in the max-plus algebra: If A * exists then solves the system of max-plus linear equations (7) Definition 2. The matrix A ∈ R n×n max is called nilpotent if there exists a finite positive integer p 0 such that for all integers p p 0 we have A ⊗p = E.

It is easy to verify that if
defined as an ordered pair (V,A), where V is a set of vertices and A is a set of ordered pairs of vertices.
The elements of A are called arcs. A loop is an arc of the form . When the initial and the final vertex of a path coincide, we have a circuit. An elementary circuit is a circuit in which no vertex appears more than once, except for the initial vertex, which appears exactly twice. A directed . . , n} and if we associate a real number [A] ij with each arc (j, i) ∈ A, then we say that G is a weighted directed graph. We call [A] ij the weight of the arc (j, i). Note that the first subscript of [A] ij corresponds to the final (and not the initial) vertex of the arc (j, i).

Definition 3 (Precedence graph).
Consider A ∈ R n×n max . The precedence graph of A, denoted by G(A), is a weighted directed graph with vertices 1, 2, . . . , n and an arc (j, i) with weight Let A ∈ R n×n max and consider G(A). The weight |p| w of a path p : i 1 → i 2 → . . . → i l+1 is defined as the sum of the weights of the arcs that compose the path: The average weight of a circuit is defined as the weight of the circuit divided by the length of the circuit: |p| w /|p| l .

Definition 4 (Irreducibility). A matrix A ∈ R n×n
max is called irreducible if its precedence graph is strongly connected.
Definition 5 (Max-plus eigenvalue and eigenvector). Let A ∈ R n×n max . If there exist a number λ ∈ R max and a vector v ∈ R n max with v = E n×1 such that A ⊗ v = λ ⊗ v, then we say that λ is a max-plus eigenvalue of A and that v is a corresponding max-plus eigenvector of A.
It can be shown that every square matrix with entries in R max has at least one max-plus eigenvalue (see e.g. [1]). However, in contrast to linear algebra, the number of max-plus eigenvalues of an n by n matrix is in general less than n. If a matrix is irreducible, it has only one max-plus eigenvalue (see e.g. [6]).
Moreover, if v is a max-plus eigenvector of A, then α ⊗ v with α ∈ R is also a max-plus eigenvector of A.
The max-plus eigenvalue has the following graph-theoretic interpretation. Consider A ∈ R n×n max . If λ max is the maximal average weight over all elementary circuits of G(A), then λ max is a max-plus eigenvalue of A. For formulas and algorithms to determine max-plus eigenvalues and eigenvectors the interested reader is referred to [1,4,6,36] and the references cited therein. Every circuit of G(A) with an average weight that is equal to λ max is called a critical circuit. The critical graph G c (A) of the matrix A is the set of all critical circuits. Let N be the set of positive, non-zero integers.
Theorem 6. Let A be an irreducible matrix. Then there exists c ∈ N (the cyclicity of A), λ ∈ R (the unique max-plus eigenvalue of A), and k 0 ∈ N (the coupling time of A) such that Proof: See e.g. [1,6,18].

IV. LEGGED LOCOMOTION VIA MAX-PLUS MODELING
In Section II equations (1), (3), and (4) describe the synchronization constraints between two legs. We can generalize these equations by defining the following vectors for an n-legged robot: Equation (1) is then written as: If one assumes that the synchronization is always enforced on the lift off time of a leg, equations (3) and (4) are written jointly as: where the matrices P and Q encode the synchronization between lift off of a leg related to a touchdown of the current event (as in equation (4)) and a touchdown of the previous event (as in equation (3)), respectively. The rationale behind this particular model is to prevent that a legged platform has too many legs in swing while walking 2 risking falling down. Synchronization constraints are always imposed on legs that are in stance and are about to enter swing: some legs should only swing if others are in stance (equation (14)). Once in swing, legs are never constrained to go into stance (equation (13)).
Equations (13) and (14) are written in state-space form as: Define the matrices Consider the full state x defined as (15) can then be written in simplified notation: Note that additional max-plus identity matrices E are introduced in the diagonal of matrix A 1 . This results in the extra trivial constraints t i (k + 1) t i (k) and l i (k + 1) l i (k), also resulting in the final system matrix (defined in page 13, equation (35)) being irreducible. This is observed later on in Lemma 12.

A. A gait parameterization
Consider a general legged robot where a two-event circuit is associated to each leg. We present a parsimonious representation of a walking gait of a robot by grouping sets of legs and specifying in what order they are allowed to cycle.
i.e., the sets p form a partition of {1, . . . , n}. A gait G is defined as an ordering relation of groups of legs: The gait space is the set of all gaits that satisfy the previous definitions.
By considering that each p contains the indices of a set of legs that are synchronized in phase, the previous ordering relation is interpreted in the following manner: the set of legs indexed by i swings synchronously. As soon as all legs in i touchdown then all legs in i+1 initiate their swing motion. The same is true for m and 1 , closing the cycle. For example, a trotting gait, where diagonal pairs of legs move synchronously, for a quadruped robot as illustrated in Figure 4, is represented by: sideways [49]. With the previous notation we can now derive the matrices P and Q in equation (15): For the trotting gait G trot we obtain: Define the function that transforms a gait into a vector of integers: For a gait G, define the similarity matrixC ∈ R n×n max as: The similarity matrixC is such thatC ⊗C T =C T ⊗C = E. The similarity matrix associated with the trotting gait G trot is:C here written in both max-plus and traditional algebra notation for legibility purposes. The similarity matrix C has the property of "normalizing" the P and Q matrices to a max-plus algebraic lower triangular form P and a max-plus algebraic upper triangular formQ respectively: Taking the previous example of the trotting gait, the normalized matrices take the form which are generated by the normal gait {1, 2} ≺ {3, 4}. Let # i represent the number of elements of the set i . For a general normal gaitḠ with1 i,j = 1 # i ×# j the structure of the matricesP andQ is: From equation (31) it is clear that the matrixP is always max-plus nilpotent, since the upper triangle is max-plus zero. For max-plus powers ofP we obtain: Max-plus nilpotency is invariant to max-plus similarity transformations (e.g. as defined in equations (27), (28)).
Given an arbitrary gait G with associated matrices P , Q, A 0 , and A 1 one can find the normal matrix P which is max-plus nilpotent. From Lemma 9 then P is also max-plus nilpotent. In the beginning of Section IV we have presented the synchronization equations (17) implicitly. However, if A * 0 exists then using equations (7) and (9), system (17) can be transformed into an explicit set of equations.
Lemma 10. A sufficient condition for A * 0 to exist is that the matrix P is nilpotent in the max-plus sense.
Proof: By direct computation, the repetitive products of A 0 can be found to be If P is max-plus nilpotent, then there exists a finite positive integer p 0 such that ∀p p 0 : = E, and therefore the max-plus sum for the computation of A * 0 is finite: Since P is always max-plus nilpotent for gaits generated by expressions (21) and (22), we conclude that A * 0 is well defined. Let A, that we call system matrix, be defined by: Equation (17) can be rewritten as: For an arbitrary gait the internal structure of A can be quite complex. However, the gait G associated to A can be transformed into a normal gait via a similarity transformation. Let The similarity matrix C transforms the system matrix A of an arbitrary gait G into the system matrix A of a normal gaitḠ via the similarity transformationĀ = C ⊗ A ⊗ C T . This can be shown by direct computation: Transforming an arbitrary gait into a normal gait is very useful since, by effectively switching rows and columns in A, one obtains a very structured matrixĀ where analysis is simple. The interpretation of the similarity matrixC is that legs can be renumbered, simplifying algebraic manipulation. Besides max-plus nilpotency, other properties are invariant to similarity transformations: irreducibility is preserved since the graphs of A andĀ are equivalent up to a label renaming. Max-plus eigenvalues and eigenvectors are related by: B. Structure of the system matrixĀ Let: The structure ofĀ can be obtained via a laborious but straightforward set of algebraic manipulations. For an arbitrary gait G we compute the normal gaitḠ via the similarity transformation with the matrix C. By observing the structures ofĀ 0 andĀ 1 (derived fromP andQ) a closed-form solution can be obtained where W = (τ f ⊗P ) * , illustrated in equation (48) on page 16. The matrixW is defined in equation (47) again on page 16. Note that τ f ⊗W ⊕ E = W and W W . An expression forĀ is then obtained: as illustrated by equation (49). One can show that: Since µ ⊗ W W for any µ > 0, and W W , expression (42) simplifies to: Let Equations (50)-(53) illustrate the resulting structure ofĀ written in the system formx(k) =Ā ⊗x(k − 1), (53), the ⊗ operator is omitted in unambiguous locations due to space limitations.

C. Max-plus eigenstructure of the system matrix
Given a parameterization of a gait, it is fundamental to understand whether the system x(k) = A ⊗ x(k − 1) reaches a unique steady state behavior. In robotics this is the equivalent of asking "does the robot walk/run as specified? Is it robust to disturbances?". These questions are answered by analyzing the max-plus eigenstructure of the system matrix: a unique eigenvalue means that the legs have a unique . . .
cycle time, and a unique (up to scaling) eigenvector means that the legs always reach the same motion pattern, independently of the initial condition or disturbances. The results obtained below use various analysis techniques available for max-plus linear systems. This is necessary due to the intrinsic time structure associated with the problem. Petri net tools (e.g. incidence matrices) can be used to understand structural properties of the system, such as irreducibility, but temporal properties are better analyzed using max-plus linear tools. In Section IV-D we show that for a fixed structure (i.e. a single Petri net) unique or non-unique eigenvectors are found by changing the holding time parameters. This result could not be captured by the Petri net structure alone. The analysis steps presented from here on are summarized in Figure 1.
Consider the following assumption (which is always satisfied in practice since the leg swing and stance times are always positive numbers): Lemma 11. If assumption A1 is satisfied then is a max-plus eigenvalue of the system matrix A (andĀ) defined by equations (36) (and (50)-(53)), and v ∈ R 2n max defined by ∀j ∈ {1, . . . , m}, ∀q ∈ j : is a max-plus eigenvector of A.
Recall equations (7) and (9) with new variables z and B such that Given the previous result, it is sufficient to show that if λ and v are a max-plus eigenvalue and eigenvector of A respectively, then replacing the state variable x(k − 1) by v and x(k) by λ ⊗ v in equation (15) holds true: The previous expression is equivalent to the following two equations: Since λ > 0 (by assumption A1), equation (59) is always verified. Thus we focus on equation (60), which can be simplified due to τ f ⊗ τ g > 0: Let τ ∆ ⊗ P 0 = P and τ ∆ ⊗ Q 0 = Q, i.e., all entries of matrices P 0 and Q 0 are either e or ε to obtain (recall that τ δ = τ f ⊗ τ ∆ and τ γ = τ f ⊗ τ g ): We now consider two cases: i) First we analyze the row indices of equation (62) that are elements of the sets 2 , . . . , m . For each j ∈ {1, . . . , m − 1} and for each row p ∈ j+1 we obtain (notice that according to (22) all the elements of [Q 0 ] p,· are ε since p / ∈ 1 , and that [v] p = τ ⊗j δ for p ∈ j+1 ): The last term always holds true since λ τ γ . Thus for rows p ∈ 2 , . . . , m equation (62) holds true.
ii) We now look at all the remaining rows p such that p ∈ 1 (noticing now that according to (21) all the elements of [P 0 ] p,· are ε and that [v] p = e since p ∈ 1 ): Combining i) and ii) we conclude that equation (62) holds true.
Consider again the trotting gait for a quadruped G trot defined in (20). For this gait m = 2, resulting in: conclude that A is also irreducible.
The max-plus eigenvector v defined by (55)-(56) is not necessarily unique, given assumption A1 alone.
Since, to the authors' best knowledge, there exists no algebraic method to prove max-plus eigenvector uniqueness in general, we take advantage of the precedence graph ofĀ to further investigate this property.
If the critical graph of a irreducible max-plus system matrix has a single strongly connected subgraph, then its max-plus eigenvector is unique up to a max-plus scaling factor (see [1], Theorem 3.101). We proceed by computing the critical graph(s) ofĀ.

D. The precedence graph ofĀ
Given expression (53) it is possible to construct the precedence graph ofĀ. Since this graph can be quite large for a generalĀ, we find it more efficient to first group "similar" nodes into a single node, i.e. apply a procedure called node reduction ( Figure 5). Next, we show various subgraphs of the graph ofĀ to better illustrate its structure ( Figure 6). The total precedence graph ofĀ is thus the combination of Figures 5 and 6. The process of constructing the graph ofĀ starts by grouping all nodes of an event associated with a group of legs i into a single node. This can be accomplished since event nodes from the same group of legs i have "similar" incoming and outgoing arcs. As an example, consider the first set of # 1 rows ofĀ as defined in expression (53): The precedence graph for equation (73) consists of 3 × # 1 nodes, since it involves the vectors t 1 , t m , and l 1 . The relation between t 1 (k) and t 1 (k − 1) results in # 1 self connected arcs in the t 1 events with weights τ γ . Instead of expressing all elements of t 1 as individual nodes with self arcs, we reduce then to a single node with one self arc, as seen in Figure 5-a2. The dashed attribute used on the self arc indicates that for each node in the group only self arcs exist, as expressed by the "connecting" matrix E 1 . The relation between t 1 (k) and t m (k − 1) is somewhat more involved, since it contains # 1 × # m arcs, as expressed by the connecting matrix 1 1,m . The resulting node reduction is illustrated in Figure   5-b1. The node reduction for the relation between t 1 and l 1 is illustrated in Figure 5 Given the node reduction one can now proceed to construct the precedence graph ofĀ: • Figure 6-a is the graph of the block diagonal ofĀ together with the block diagonals of the sub- • Figure 6-b is the graph of the columns formed by the matrices A 12 and [A T 32 A T 42 ] T using node reductions presented in Figures 5-b1 and 5-b2.
• Figures 6-c1 and 6-c2 illustrate two subgraphs of the remaining columns ofĀ. Note that we only present the subgraphs of the first sets of # 1 and # 2 out of a total of m − 1 columns. These follow the same pattern. We use different attributes on the arcs, such as dashed, thick solid, etc., to distinguish the different node reductions, as presented in Figures 5-c1 to 5-c4.
Consider the following assumption: If assumption A2 is verified then the critical graph of G c (A) (and G c (Ā)) has a single strongly connected subgraph.
Proof: We consider two cases: In this situation the circuits presented in Figures 5-a1 and 5-a2 all belong to the critical graph since their weights are τ γ or τ ⊗m δ both equal to the max-plus eigenvalue λ. Note that any circuit c 1 of length l made from the nodes of t m , illustrated in Figure 5-a1, has an average weight of and as such also belongs to the critical graph. Any other circuit in the precedence graph ofĀ must pass through at least one node of t m , as illustrated in Figures 6-b, 6-c1, and 6-c2 (with the exception of the self-loops in Figure 5-a3 and the circuits in Figure 5-a4 that we don't consider since their weights are e and τ γ /2 both less then λ). Additionally, arcs starting in nodes from a group t q with q < m are only connected to nodes in t q+p for p 0 (or l q+p ). This is again illustrated in Figures 6-a, 6-c1, and 6-c2.
Let t [ q ] i denote element i of t q . Consider the circuit · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · a1) b1) with q < m. The average weight is (with τ γ = τ ⊗m Circuit c 2 is thus also in the critical graph. For the general circuit of the type with q 1 < q 2 < · · · < q l < m, the average weight is Again, circuit c 3 is part of the critical graph. Any circuit that passes through any node in l q , for any q, will never be in the critical graph. This is due to the fact that arcs within touchdown nodes of different leg groups yield a higher weight: As such, a path that connects a touchdown node to a lift off node "loses" τ γ − τ g = τ f from the maximum possible weight, a path from lift off to lift off nodes loses τ γ , and a path from lift off nodes to touchdown nodes loses τ g in weight. This can also be observed in the structure ofĀ, in equation (51), where the sub-matrix τ f ⊗ (τ g ⊗ W ⊕ V ) overcomes the sub-matrices τ g ⊗ W ⊕ V , τ f ⊗ W , and W . Consider, for example, the circuit c 4 : then Since all the nodes in the critical graph are connected (they are all touchdown nodes) we conclude that for the case τ γ = τ ⊗m δ = λ the critical graph ofĀ has a single strongly connected subgraph. Figure 7-a illustrates the complete critical graph ofĀ for this case.
In this situation only circuits of the type c 1 are part of the critical graph. Circuits of the type c 2 or c 3 are not part of the critical graph. Figure 7-b illustrates the resulting critical graph ofĀ. Since all the nodes of t m are connected to each other we conclude that for the case τ γ < τ ⊗m δ = λ the critical graph ofĀ has a single strongly connected subgraph.
A third case can be considered: τ ⊗m δ < τ γ = λ. In this situation the critical graph ofĀ does not have a single strongly connected subgraph. Figure 7-c illustrates this situation, that we document here without proof.
Theorem 15. Given assumptions A1 and A2, the max-plus eigenvalue λ of the system matrix A (andĀ), defined by equation (54), is unique, and the max-plus eigenvector v of A (andĀ), defined by equations (55)-(56) is unique up to a max-plus scaling factor.
Proof: According to Lemma 12 A is irreducible, and as such it has a unique max-plus eigenvalue.
According to Lemma 14 the critical graph of G c (A) has a single strongly connected subgraph, and as such its max-plus eigenvector is unique up to a max-plus scaling factor (see [1], Theorem 3.101).

E. Coupling time
Theorem 6 on page 9 describes an important property of max-plus-linear systems when the system matrix A is irreducible: it guarantees the existence of an autonomous steady-state regime that is achieved in a number of finite steps k 0 , called the coupling time. Computing the coupling time is very important for the application of legged locomotion since it provides the number of steps a robot needs to take to reach steady state after a gait transition or a perturbation.
Proof: Computing successive products ofĀ and taking advantage of its structure and equations (43) Since λ τ γ it is sufficient to show that This can be confirmed by inspecting equations (48) and (92): 1) All the terms in the upper block triangle of τ γ ⊗ W are ε while for τ f ⊗ V ⊗ W they are positive numbers.

3) In the lower block triangle
thus concluding that the coupling time is k 0 = 2 with cyclicity c = 1.

V. CONCLUSIONS
We have shown that max-plus linear models are very well suited to model leg synchronization in legged locomotion. The abstraction of the continuous-time dynamics associated with each leg as a twoevent circuit simplifies the construction of a gait space. The combinatorial nature of this gait space, arising from all the possible arrangements in which multiple legs can be synchronized, is captured by a compact representation as an ordered set of ordered sets.
For the classes of switching max-plus linear systems developed in this paper important structural properties of the max-plus system matrix are obtained in closed-form. The unique max-plus eigenvalue represents the total cycle time, the unique (up to a scaling factor) max-plus eigenvector dictates a unique steady-state behavior, and the coupling time reveals the transient response to gait switching or disturbances.
Although some of the derivations in this paper are quite lengthy, using a combination of discreteevent algebraic tools with graph-theoretic concepts has lead to an important result in robotics: since the coupling time was found to be two, we have shown that legged robots can switch gaits (or rhythms) or recover from large disturbances in at least two steps. In the derivation process we have found that similarity transformations can facilitate the algebraic manipulations by exposing the structure of the system matrices.
This was important to find closed-form expressions to the eigen-structure of the system and the coupling time, that typically need to be computed via simulations of using numerical procedures. On the graph side, the node-reduction procedure has allowed depicting graphs that can have an arbitrary large number of nodes. A graph-theoretic proof is needed for proving the uniqueness of the max-plus eigenvector. Our results are valid for robots with an arbitrary number of legs.
Further research will look towards relaxing the structure of the system matrix to address the synchronization of general cyclic systems and towards the modeling of more general gaits.


An ACOA-AFSA Fusion Routing Algorithm for Underwater Wireless Sensor Network

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.

Introduction
Rapid evolvement of wireless communication technology, electronic technique, sensor technology, micro-electromechanical 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.

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 Hopby-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 selfhealing mechanism significantly enhanced the robustness of clustered UWSNs.
International Journal of Distributed Sensor Networks 3 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.

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.

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. [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.

Implementation of Fusion Algorithm See
(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 where x i is current state of fish i and x i1 , x i2 are the coordinates of x i , respectively, x(i) consistence is consistence of x i . Fish i implements activity of foraging by comparing the consistence with its neighbor. In its visual range, fish i chooses some status randomly and the chosen status is compared with current status to judge which one is better. If the chosen one is better, then fish i will move one step toward it. Else fish will try to find some better status in the extent of maximum number of iterations. The equations are shown as follows: where x v is the chosen state that needs to be compared and x inext is the next state that fish i will reach. Here (2) is valid if fish i finds better status in the maximum iterations, and (3) is executed for fish's next step toward x v . After that every status' consistence will be increased with idea of ACOA. That is to say, we introduce modifying factor, which is positive feedback mechanism from AOCA, to strengthen the chosen status (next node). The updated consistence is shown as expression (4)  optimal choice and the other one is for suboptimal choice. The content of the bulletin boards will be refreshed after every activity. We name the boards as optimal board and sub-optimal board, respectively. If there is only one link for fish to choose or the distance of alternative node is bigger than optimal path, then the content of optimal board is the same as sub-optimal board. The rules are applicable to the clustering activity, following activity and random activity: (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 s i . Center location of fish is calculated in (6): Fish i will implement clustering activity if those two conditions are met: (1) x(center) consistence < x(i) consistence , (2) x( j) − x(i) < δ, j / = i, j = 1, 2, . . . , n. The two premises demonstrate that x(center) is better than x(i). Logically the next status of fish i is shown in expression (7). Like foraging activity, consistence of next status should be strengthened with (4) and then bulletin board's content is refreshed by latest status: International Journal of Distributed Sensor Networks 5 (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 x(minimum) is better than x(i), so fish i will move one step toward x (minimum). The next state of fish i is shown 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 Tabu k to record the city that ant k walks around. And the transferring path is determined by route pheromone heuristic index α. P k i j represents probability that ant k moves to city j from city i. Its expression is shown in the following term: Parameter allowed k in expression (10) indicates potential cities that ants can choose for the next step. η i j (t) indicates heuristic function and its expression is as follows: where d i j is the distance between city i and j. (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. L 2 K represents the square of path length that ant k walks by in the circulation. N means total number of nodes that ant k has to traverse from source node to destination node [19,20].
(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.

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.

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 1000 × 1000 × 500 cubic meters which includes 80 sink nodes. The communication range for sensor nodes and sink nodes was 60 meters while data channel was set to 5 kbs. The length of each data message packet is 512 bytes. Based on the energy consumption model presented in [17,21], the least transmission power required at the transmitter site to achieve a power level, p 0 , at the receiver can be expressed as follows: where d is the distance between transmitting node and receiving node, k is loss factor that is affected by extension of wave surface, α( f ) is absorption coefficient of frequency, while f is the acoustic transmitting frequency. The parameters of AFSA and ACOA are as follows. (1) Parameters in AFSA. Fish's step length S is 2, bulletin board's content is 0, visual radius is 6, crowding factor δ is 10, iteration number is 2000, calculation precision is 10 −3 , and population quantity of fish swarm is 50 [7]. (2) Parameters in ACOA. Pheromone evaporation factor ρ is 0.5, number of ants is 50, maximum iteration number for ant colony algorithm Max is 1000, pheromone heuristic factor α is 1.5, expected heuristic factor β is 5, and strength of pheromone Q is 600 [22,23].

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 lowenergy adaptive clustering hierarchy (LEACH) [24], classic routing protocol for underwater sensor networks named vector-based forwarding (VBF) [25].
International Journal of Distributed Sensor Networks 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. 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.

Simulation Results and Analysis (a) Energy Consumption Comparison.
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.
(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.
(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.

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.


Automatic Multi Document Summarization Approaches

Problem statement: Text summarization can be of different nature rangi ng from indicative summary that identifies the topics of the document to informative summary which is meant to represent the concise description of the original d ocument, providing an idea of what the whole conten t of document is all about. Approach: Single document summary seems to capture both the i nformation well but it has not been the case for multi documen t summary where the overall comprehensive quality i n presenting informative summary often lacks. It is f ound that most of the existing methods tend to focu s on sentence scoring and less consideration is given to the contextual information content in multiple documents. Results: In this study, some survey on multi document summar ization approaches has been presented. We will direct our focus notably on four well known approaches to multi document summarization namely the feature based method, clus ter based method, graph based method and knowledge based method. The general ideas behind th ese methods have been described. Conclusion: Besides the general idea and concept, we discuss th e benefits and limitations concerning these methods. With the aim of enhancing multi document summarizat ion, specifically news documents, a novel type of approach is outline d to be developed in the future, taking into account the generic components of a news story in o rder to generate a better summary.

INTRODUCTION
The need of automatic text summarization has recently increased due to the proliferation of information on the Internet. With the availability and speed of internet, information search from online documents has been eased down to user's finger tips. However, it is not easy for users to manually summarize those large online documents. For example, when a user searches for information about earthquake which occurred in Sendai, Japan, the user will probably receive enormous articles related to that event. The user would definitely opt for a system that could summarize those articles. The goal of automatic text summarization is condensing the source text into a shorter version preserving its information content and overall meaning.
The objective and approach of summarization of documents explain the kind of summary that is generated. For example, it could be indicative of what a particular subject is about (closely related to a user query), or can be informative about what the whole content of document is all about. Besides that, approach towards text summarization can be either extractive or abstractive (Radev et al., 2002). In extractive type summarization, important sentences are identified and directly extracted from the original document, i.e. the final summary consists of original sentences. On the other hand, in abstractive type summarization (Ganesan et al., 2010) the sentences which are selected from the original document are further processed to restructure them before concatenating them into final summary. This process usually involves deep natural language analysis and sentence compression.
By understanding the type of summary i.e., indicative, informative, extractive and abstractive, we can then apply them to either single document or multi document. This study focuses mainly on informative and extractive type multi document text summarization. The distinct characteristics that make multi document summarization rather different from single document summarization is that multi document summarization problem involves multiple sources of information that overlap and supplement each other, being contradictory at occasions. So the key tasks are not only identifying and coping with redundancy across documents, but also ensuring that the final summary is both coherent and complete.
The contributions of this study can be summarized as follows: We discuss the four notable approaches of multi document summarization and present it with related research from literatures. The benefits and limitations concerning these approaches are also discussed. At the end of this study, a novel type of approach is outlined to be developed in the future, for news documents summarization. We aim to incorporate the generic components of a news document in order to generate a better summary.
The rest of the study is organized as follows: First we present the survey on four multi document summarization approaches namely the feature based method, cluster based method, graph based method and knowledge based method. Then we outline the proposed multi document summarization method; i.e., the component based method. Finally we end with conclusion.

Multi document summarization approaches:
A number of research study have addressed multi document summarization in academia (Erkan and Radev, 2004a, Wan and Yang, 2008, Haribagiu and Lacatusu, 2010 and illustrated different types of approaches and available systems for multi document summarization. In this study we direct our focus notably on four well known approaches to multi document summarization. Our discussion will be based on the following pattern: For each method, we will first discuss its main idea. Following that, we will look at some research study from related literatures. Finally the benefits and limitations concerning each method are commented.
Feature based method: Extractive type summarization involves identifying the most relevant sentences from the text and put them together to create a concise summary. In the process of identifying important sentences, features influencing the relevance of sentences are determined. Here we list some of the common features that have been considered for sentence selection.
Word frequency: The idea of using word frequency is that important words appear many times in the document. The most common measure widely used to calculate the word frequency is tf and idf.
Title/headline word: Occurrence of words from the document title in sentence indicates that the sentence is highly relevant to the document.
Sentence location: Important information in a document is often covered by writers at the beginning of the article. Thus the beginning sentences are assumed to contain the most important content.
Sentence length: Very short sentences are usually not included in summary as they convey less information. Very long sentences are also not suitable to represent a summary.
Cue word: There are certain words in a sentence which indicate that the sentence is carrying an important message in the document (e.g., "significantly", "in conclusion").
Proper noun: Sentences containing proper noun representing a unique entity suchlike name of a person, organization or place are considered important to the document.
Let us show a simple example for scoring a sentence S. Consider that we select three features namely title word, sentence length and sentence location. Calculation of the score for each of these features as in (Suanmali et al., 2009) is shown below: No.title word in S Title word ,T No.word in title = No.word in S Sentence length, L No.word in longest sentence = Sentence position, P 5 / 5 for 1st, 4 / 5 for 2nd, 3/ 5 for 3rd, 2 / 5 for 4th, 1/ 5 for 5th,0 / 5 for other sentences = After computing each of the feature score, the total scoring of a sentence is given by Eq. 1: where, Score_S i is the total score of sentence S i . The terms T i , L i and P i are the feature scores of sentence S i based on the title words it contains, sentence length and sentence position respectively. w 1 , w 2 and w 3 are the weights for the linear combination of the three features. Figure 1 depicts the generalized architecture of a feature based summarizer. We can see that text features score are combined for sentence scoring, as shown in Eq. 1. But not all text features are treated with same level of importance as some of the features have more importance or weight and some have less. Thus emphasis should be given on dealing with the text features based on their importance. This issue can be overcome by using weight learning method. Many researchers have been using various weight learning methods in their study. Binwahlan et al. (2009) introduced a novel text summarization model based on swarm intelligence technique known as Particle Swarm Optimization (PSO). The feature scores were adjusted using the weights resulting from the training using the PSO. The training set consist pairs of document and human reference summary. They implemented the sentence scoring using the following Eq. 2: where, Score (S) is the score of the sentence S, w 1 is the weight of the feature i produced by PSO, i = 1-5 showing that 5 text features where used and Score_f i (s) is the score of the feature i. The use of PSO for optimization have also been proven to be robust in other domains as well (Nacy et al., 2009, Balaji andKamaraj, 2011). Another weight learning approach was described by Bossard and Rodrigues (2011) who approximated the best weight combination using a genetic algorithm for their multi document summarizer. By using the genetic algorithm, a suitable combination of feature weights can be found. Table 1 lists some of the weight learning methods applied to text summarization. Weight learning method (Osborne, 2002) Conjugate gradient decent search method (Fattah and Ren, 2009) Mathematical Regression (MR) model (Binwahlan et al., 2009) Particle Swarm Optimization (PSO) (Dehkordi et al., 2009), Genetic Algorithm (GA) model (Bossard and Rodrigues, 2011) and (Suanmali et al., 2011) Besides optimizing feature weights, the impact of combining different features has been investigated by Hariharan (2010) for multi document summarization. In his study, the author showed that term frequency weight combined with position and node weight feature yields significantly better results.
The feature based method has been widely used by researchers because of its simple and direct approach to sentence selection for summarization. It is found that the combination of cue words, title words and location are what relied upon as primary features (Gupta and Lehal, 2010). An important issue to be noted in the context of multi document summary is that important or relevant information is usually spread across documents and feature based methods often fail to handle this problem. Besides that, the feature based method is knowledge poor in term of capturing contextual information contents that exist in the sentences and multiple documents. These limitations are due to the sentence scoring process which depends solely on flat feature representation of a sentence while omitting cross-document concepts and varying context in different documents.

Cluster based method:
The idea of clustering is to group similar objects into their classes. As far as multi documents are concerned, these objects refer to sentences and the classes represent the cluster that a sentence belongs to. By looking at the nature of documents that address different subjects or topics in the documents, some researchers try to incorporate the idea of clustering into their study. Using the concept of similarity, sentences which are highly similar to each other are grouped into one cluster, thus generating a number of clusters. The most common technique to measure similarity between a pair of sentences is the cosine similarity measure where sentences are represented as a weighted vector of tf-idf. Once sentences are clustered, sentence selection is performed by selecting sentence from each cluster. Sentence selection is then based on the closeness of the sentences to the top ranking tf-idf in that cluster. Those selected sentences are then put together to form the final summary Fig. 2. Typically, clustering algorithms can be categorized as agglomerative or partitional (Jain et al., 1999). In agglomerative clustering (also known as "bottom-up" approach), each sentence is initially considered a separate cluster by its own. This individual clusters are then merged into successively larger clusters. This iterative process ends when some stopping criterion is reached.
Whereas in partitional clustering approach, initially all sentences are grouped into one big cluster. Iteratively smaller clusters are generated by dividing the largest cluster into several sub-clusters. Each subcluster generated will then contain sentences with higher similarity. A well known partitional clustering algorithm is the K-Means algorithm. Radev et al. (2004) pioneered the use of cluster centroids for their multi-document summarizer, MEAD. Centroids are the top ranking tf-idf that represents the cluster. These cluster centroids are then used to identify the sentences in each cluster that are most similar to the centroid. Thus, the summarizer generates sentence which are most relevant to each cluster.
Taking the benefit of clustering approach, efforts have been put into making the overall process of summarizing multi document effective. One that is worth to be mentioned here is determining the optimal number of clusters, where Xia et al. (2011) adopted the co-clustering theory to find optimal clusters. They determine the weights of sentences and terms based on the sentence-term co-occurrence matrix. Sentence-term matrix is designed to represent diversity and redundancy within multiple articles.
Finally the top-weighted sentence in every cluster is picked out to form the summary, until a userpreferred summary length is met.
Some researchers employ clustering-based hybrid strategy (Yu et al., 2006) to combine local and global search for sentence selection. This approach does not depend only on similarity to cluster for sentence selection but also considers the overall document content similarity. Focus has also been given on strengthening clusters diversity. To achieve this, Aliguliyev (2010) used PSO algorithm by adding a mutation operation adopted from genetic algorithms to optimize intra-cluster similarity and inter-cluster dissimilarity.
Cluster based methods has been successful in its task to represent diversity and reduce redundancy within multiple articles. Although these can be considered the advantage of using clustering methods, as far as multi document is concerned, a summary cannot be meaningful enough if the relevance of a sentence is judged merely based on the clusters. This is because in clustering based method, eventually sentences are ranked according to the similarity with cluster centroid which simply represents frequent occurring terms. Thus, this method is also considered to be knowledge poor in term of its inability to capture contextual information contents that exist in the sentences.

Graph based method:
The fundamental theory of graph representation is the connection or linking between objects. These connections exist based on their underlying relation. In the case of text documents, the underlying relation is usually the similarity between objects-in this case, sentences.
Generally, a graph can be denoted in the form of G = (V, E), where V represents the graph's vertex or node and E is the edge between each vertex. In the context of text documents, vertex represents sentence and edge is the weight between two sentences. Using this approach, documents can therefore be represented as a graph where each sentence becomes the vertex and the weight between each vertex corresponds to the similarity between the two sentences. As in most literature concerning graph based approach, the most widely used similarity measure is the cosine similarity measure. An edge then exists if the similarity weight is above some predefined threshold. Figure 3 shows an example graph for multi document.  (Erkan and Radev, 2004b). For multi document each node represents a sentence Once the graph is constructed for a set of documents, important sentences will then be identified. It follows the idea that a sentence is considered important if it is strongly connected to many other sentences (Erkan and Radev, 2004b).
This approach differs from the cluster based approach where sentences are ranked based on its closeness to cluster centroid. Two well known graph based ranking algorithms are the HITS algorithm (Kleinberg, 1999) and the Google's PageRank (Brin and Page, 1998). Both methods have been traditionally used in Web-link analysis and social netstudys. Lexrank (Erkan and Radev, 2004b) and TextRank (Mihalcea and Tarau, 2004) are two successful graph-based ranking systems that implements these algorithms.
Further studies have been carried to make improvement through modification in the ranking algorithm. Wan and Yang (2006) assigned different weights to intra-document links and inter-document links. They give more priority to sentence with high inter-document links. In the study by Hariharan and Srinivasan (2009), they approach the graph based method differently i.e., by discounting the already selected sentence by removing the sentence from further consideration when ranking the remaining sentences.
Apart from sentence level information, Wan (2008) and Wei et al. (2010) devise the document-sensitive graph model to explore document impact on the graph-based summarization, by incorporating both the document-level information and the sentence-todocument relationship in the graph-based ranking process. The document-level relations are used to adjust the weights of the vertices and the strength of the edges in the graph.
The approach to graph based methods have resulted in positive feedback from the multi document summarization research communities as it was able to identify 'prestigious' sentences across the documents. The resulting graph is also able to capture distinct topics from unconnected sub-graphs. However since this approach depends heavily on sentence similarity to generate graph, it only treats sentence as bag of words without "understanding" the text. This would result the final summary to be not complete enough specifically for an informative summary generation. We will discuss further on this issue later in our proposed component based approach.
Knowledge based method: Most documents or articles will have its content related to a particular topic or event. These topics or events generally belong to a particular domain and each domain normally has its own common knowledge structure. Thus, there have been efforts made by researchers to utilize the background knowledge (i.e., ontology) to improve summarization results. In fact, many other applications have tailored their model to be ontology-driven (Shareha et al., 2009, Nasir andNoor, 2011).
Ontology, equipped with concise concepts and rich domain-related information, can capture the hidden semantic information. With the support of the ontology, information can be related with each other through the shared and common understanding of a domain (Khelif et al., 2007). Li et al. (2010) developed the Ontology-enriched Multi-Document Summarization (OMS) system to generate query-relevant summary from a collection of documents. OMS first links the sentences from documents onto a domain-related ontology, then maps the given query to a specific node in the ontology and finally extracts the summary from the sentences in the sub-tree rooted at the corresponding query node. Another example is the utilization of knowledge from UMLS (www.nlm.nih.gov/research/umls/), a medical oncology, to summarize biomedical documents (Verma et al., 2007). Here, the authors apply the medical ontology as dictionaries of valid concepts and choose sentences that contain only those words corresponding to concepts in the ontology. Kogilavani and Balasubramanie (2009) also utilized UMLS but as an alternative they used the ontology to expand user's natural language queries with synonyms and semantically related concepts.
In previous related study, Wu and Liu (2003) manually constructed a domain specific ontology for business news articles. They determine the main subtopics of the articles of interest by comparing the sentence words to the ontology. Sentences which are most "close" to the subtopics are then selected. A similar idea but with additional ontology features were proposed by Hennig et al. (2008) for sentence scoring. The features they used were tag overlap, subtree depth and subtree count.
Ontology can be useful for domain specific documents where key concepts pertaining to the domain can be identified. In most ontology based text summarization, the ontology functions to bootstrap the process of sentence selection by picking sentences which contain predefined ontology concepts. However it can be seen that the ontology is mainly used for similarity measure and as dictionary of valid concepts. One of the major concerns in ontology based summarization is the availability of the ontology itself. That is, this approach is only feasible when the ontology is available. Due to this reason, in most cases the ontology is manually constructed by experts. Unlike the previous three methods which can be applied to any domain, current ontology based method depends on a particular domain where the ontology design requires input from the domain experts.
Proposed component based approach: If we look back at previous approaches described in this study, we can observe that those approaches were mainly based on flat text feature representations without any attempts to "understand" the text. Moreover, until now, most text summarization models incorporate only bag of words as text representation and do not include much contextual information. We believe that providing comprehensive contextual information coverage would be ideal for summary creation.
In the context of news documents (which will be our research focus), different news sources reporting on a particular event tend to contain common components that make up the main story of the news. The common components of a news article consist of WHO, WHEN, WHERE, WHAT and HOW. For example, new articles on natural disaster events often contains components such as information about person, location, description of the disaster, the damages to human and properties, the relief efforts, organizations involved, the disruption of services and etc. Such occurrence of components with its information content description is what the readers usually search for while reading a news story. Moreover, as far as multi document is concerned, these components usually overlap each other and often reappears in different parts of the document as well as in documents from other news sources. We aim to capture these components' content information to better represent multiple document coverage of a news story.
Our proposed approach will incorporate ontology learning as part of our effort to learn the relationship linking certain pairs of components content. This is relevant to the understanding of the text. In contrast, existing ontology based methods discussed in the literature merely used ontology to identify important concepts in documents. For example, Wu and Liu (2003) perform term based mapping of sentences to ontology to find the most informative concepts in a document, while Hennig et al. (2008) classify sentence to nodes on the ontology to identify the main topics in a document. Their efforts were mainly focused on matching the ontology concepts which appear in the text, so that frequent occurring concepts can be labeled as important topics. As opposed to their approach, we do not use ontology for identifying important concepts or topics; instead we use the idea of ontology learning to capture the relations that exist among predefined components in the news documents. Ontology learning can also be used to generate terms which are relevant to the underlying domain, in order to capture only relations among the generated terms.
This way of utilizing component's content knowledge will benefit the summarization process in two ways. First, breaking documents down to their components and capturing those links between them would produce broad information coverage for the summary, thus generating an informative summary. The other benefit is that this approach gives an "intuitive thought" on the kind of information we know that is essential to be included in the summary. The latter is close to the way how humans prepare a news related summary.

CONCLUSION
This study provides a general survey on multi document summarization approaches. Indeed, this study has been tailored in a way that researchers whom are new to the area of text summarization can grasp the idea of various multi document summarization approaches. Four types of approaches have been discussed, namely the feature based method, cluster based method, graph based method and knowledge based method. It appears that each of these methods possess its own advantages towards multi document summarization. At the same time, there are some issues or limitations pertaining to those methods. For future improvement, we propose a novel approach, taking into account the generic components of a news story in order to generate a better summary which is well suited for an informative type summary generation. We belief that the proposed component based approach can alleviate some of the aforementioned limitations.