Wireless Pers Commun https://doi.org/10.1007/s11277-017-5056-8

Link State Routing Based on Compressed Sensing Samane Kargar1 • Faramarz Hendessi1 • T. Aaron Gulliver2

 Springer Science+Business Media, LLC, part of Springer Nature 2017

Abstract In table routing protocols such as link state routing, every node in the network periodically broadcasts its link state and the state of its neighbors. These routing updates result in the transmission of a large number of packets. Some of these packets contain correlated or even redundant data which could be compressed if there is central management in the network. However, in autonomous networks, each node acts as a router, in which case central coordination is not possible. In this paper, compressed sensing is used to reduce routing traffic overhead. This can be done at nodes which have greater processing capabilities and no power consumption limitations such as backbone nodes in wireless mesh networks. A method is proposed to select a subset of nodes and thus a subset of links to probe their state. The sensed states are encoded to generate a low dimension sampled vector. This compressed link state vector is broadcast to the entire network. Nodes can then reconstruct link states from this vector using side information. Performance results are presented which demonstrate accurate anomaly detection while adapting to topology changes. Further, it is shown that a proper choice of weighting coefficients in the sampling process can improve detection performance. Keywords Network protocols  Wireless networks  Mesh networks  Compressed sensing  Routing protocols  Network management  Diffusion wavelet transform

& T. Aaron Gulliver [email protected] 1

Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan 83111-84156, Iran

2

Department of Electrical and Computer Engineering, University of Victoria, PO Box 1700, STN CSC, Victoria, BC V8W 2Y2, Canada

123

S. Kargar et al.

1 Introduction In autonomous networks with distributed network management, each node acts as a router so that additional packets must be transmitted to disseminate routing information. Nodes broadcast link state information and the network status of their neighbors which can lead to significant traffic overhead. Some routing protocols organize the packet transmissions between nodes. For example, on-demand routing protocols reduce the routing overhead, but the tradeoff is an increase in the network delay [1]. Another approach to reducing this overhead is flood control which limits packet transmissions in the network. For example, optimized link state routing (OLSR) selects some nodes as multipoint relays (MPRs) and only these nodes participate in packet flooding [2]. Other protocols use classification methods to reduce the overhead. For example in on-demand link state (LOLS) routing [3], short term and long term link states are considered. The short-term state represents the current cost of a link while the long-term state denotes the typical link cost. These states are advertised in the network based on the node distances, so nodes are classified by the distances between them. Short term link state information is sent to nearby nodes frequently while long-term state information is sent to far nodes less often. Opportunistic routing has also been employed to reduce the overhead by using route discovery during packet forwarding [4–6]. In this paper, compressed sensing based routing is proposed to reduce routing overhead. Link state information is compressed by selecting a subset of links on some predefined paths and coding them before it is broadcast. Nodes in the network recover the information using side information such as the sparsity of link state changes and reconstruction methods. The coefficients of the network graph and the link state weights are used to reduce the link dependencies and thus improve the reconstruction performance. With most routing methods, each routing update in a network with N nodes and L links involves N broadcasts of L link states. These updates have significant redundancy, as each link state is sent by 2 nodes. Further, if the network is stable and the link state changes are limited to a few links, this information can be compressed to reduce the routing overhead. The proposed approach selects a subset of nodes in the network to gather information regarding a number of specified paths and links in the network and broadcasts only this information. The notation employed in this paper is as follows. • Advertiser node A subset of nodes which have been selected to flood the coded information collected from links in the network. • Sampling path A path which starts from an advertiser node and traverses a number of links whose states are sampled. • Sampling depth The number of links in each sampling path. • Anomaly A significant change in a link state which is not detected. The proposed compressed sensing solution requires that the following questions be answered. • How many advertiser nodes (s) should be selected to gather and broadcast link state information? • How should advertiser nodes be selected? • What is the optimum sampling depth (d)? • How should the sampling paths be selected to optimize the information gathered, i.e. the sampling matrix generation method? In this paper, these questions are answered as follows.

123

Link State Routing Based on Compressed Sensing

• We show that a fraction s  0:25 of the nodes is sufficient for advertising coded link state information. • A selection method is developed for advertiser nodes that can be applied to any network. • A sampling path selection technique is presented which provides sufficient paths and links in these paths (sampling depth) for adequate reconstruction of the link states. • Weighting factors are suggested to limit the link dependencies and improve sampling performance. Results are presented which show that link anomalies can be identified accurately using information from only 25% of the nodes. For the Waxman topology model with b = 0.5 (which will be described later), the average detection accuracy for an 81 node network is 0.95 without weighting and 0.99 with weighting. The rest of the paper is organized as follows. The compressed sensing problem is introduced in Sect. 2. Section 3 describes the proposed algorithm for link state sampling as a compressed sensing problem, and this algorithm is adapted in Sect. 4 to incorporate topology changes. Some performance results are presented in Sect. 5. In Sect. 6, weighting factors are proposed for link state compression and the corresponding performance improvement is demonstrated. Finally, some conclusions are given in Sect. 7.

2 Compressed Sensing Compressed sensing (CS) was proposed for sparse center point, and discrete signal and image representation and recovery. Although compressed sampling has existed for over four decades, the subject of compressed sensing (CS) was only recently developed in 2008 by Cande`s, Romberg and Tao [7–11], and Donoho [12]. Compressed sensing is based on the fact that a low-dimensional collection of linear projections of a sparse signal contain enough information for reconstruction. It has a wide range of applications including error correction, imaging, image compression, and radar. In [13], the application of compressed sensing to network data was considered. It was shown that creating a sparse representation of network data is not as straightforward as other types of data such as images. However, by associating a graph with the network topology such that the vertices of the graph represent the nodes of the network and the edges between vertices represent the data relationships between adjacent nodes (for example the existence of links and their quality), effective algorithms for sparse representation of network data have been developed. Graph wavelets and diffusion wavelets are two transformations that have been used for sparse representation of network data. Graph wavelets [14] are a generalization of discrete wavelets in which the transformations are not orthogonal. Diffusion wavelets use an orthonormal basis for the transformation [15]. Compressed sensing has been widely employed in the field of wireless sensor networks [16–19]. In wireless sensor networks, a fusion center is used to compress information from an ensemble of spatially distributed sensor nodes. Energy and bandwidth are scarce resources in sensor networks, so the goal is to reduce resource consumption. The application of compressed sensing in IP-based networks and network monitoring was considered in [20–25]. Diffusion wavelet transforms were used to obtain sparse representations for network traffic and link delay information. However, this requires knowledge of the network topology and routing, which may not be available. Further, sampling algorithms which are applicable to an arbitrary topology have not yet been developed. Thus in this

123

S. Kargar et al.

paper, we propose a sampling algorithm for a general network and show that it can be used to effectively compress network information. It has been shown that a signal having a sparse representation can be recovered from a small set of linear, non-adaptive compressive measurements. This was first proposed for a real-valued, finite-length, one-dimensional, discrete-time signal x. Suppose that x is a column vector in RN with elements x[n], n = 1, 2,…, N, and w is a basis for RN so that it contains vectors fwgNi¼1 such that x¼

N X

a½iwi

ð1Þ

i¼1

These vectors can be formed into a matrix w = [w1, w2,…, wN], giving x ¼ Wa

ð2Þ

where a = [a1, a2,…, aN]. Thus, a provides equivalent representations of the signal x in the w domain. If there is a representation of x that has only k non-zero elements, k  N, then it is said to be a sparse signal in this domain. The sparse signal x can then be represented by its k sparse representation in a. The process of converting a signal into the w domain and discarding N-k zero samples is not efficient. Fortunately, there is a more efficient means of obtaining a sparse representation. Consider the following sampling equation of x y ¼ Ax

ð3Þ

If A is an N 9 N matrix then y is a length N vector. Thus, there are N equations and N unknowns, so this system of equations has a unique solution. However, if A is an M 9 N matrix, then y will be a length M vector, and with M equations and N unknowns, M [ N, there will be multiple solutions for x, but considering sparsity, one of these solutions will be the best. In compressed sensing, the sparsity of x is the basis of low dimensional sensing

Fig. 1 The compressed sensing process for a binary signal with a binary sampling matrix [26]

123

Link State Routing Based on Compressed Sensing

and reconstruction. Figure 1 illustrates the compressed sensing process [26]. The elements of vector x and sampling matrix A belong to the {0,1} domain. Each element of y is a linear combination of some nonzero samples of x so its elements belong to {Nþ g. In CS the sampling process is not adaptive, which means that nothing needs to be known about x except that it is sparse. Thus, the sampling matrix A does not depend on the signal x. In the next section, compressed sensing is used to develop a network routing algorithm.

3 Compressed Sensing Link State Routing In this section, the broadcast of link states in a network is characterized as a compressed sensing problem. As described in Sect. 2, when a vector x with dimension N has k  N nonzero elements, or just k significant elements, only s samples of x are sufficient to describe x. In the link state routing problem, x is a length L differential link state vector, differential_link_state. In a stable network, the link state will change very slowly. However, when a change does occur, one or more links will be affected and these are reflected in the differential_link_state vector. Thus, this is a sparse vector with k  L nonzero elements corresponding to the links that have changed. The compressed sensing problem is then sampled linkss1 ¼ sampling matrixsL  differential link stateL1

ð4Þ

where differential_link_state is the vector of differences in the link states from the previous link states, and sampled_links is the coded link states which will be broadcast by the advertiser nodes. The sampling_matrix is a matrix which is used to encode differential_link_state. The reconstruction is given by    glink state  ð5Þ differential link state ¼ min differential  1

glink state is defined by where differential glink state sampled links ¼ sampling matrix  differential

ð6Þ

The notation kvk1 , called the 1 norm of v, denotes the number of nonzero samples in v. Each row of the sampling matrix determines which link states should be combined to generate an element of sampled_links. The elements of sampled_links are broadcast in the network by an advertiser node. It is clear that the advertiser node should be a node whose associated link states are used to generate sampled_links. A packet is composed of a header and a message. The header contains information regarding the sender and receivers, and the packet sequence number. The message contains the IP address of the neighbor nodes of the sender node. Thus for a node with l1 links and another with l2 links, the headers will have the same length, so there is no difference in the header lengths of advertiser node packets with l1 elements and l2 elements. Thus, a node which generates the greatest number of elements in sampled_links should be chosen as an advertiser node, as this will reduce the number of sampled_links vectors that are transmitted. The sampling method and sampling_matrix construction and the link state table updating are now considered. This includes properties of the sampling matrix such as the matrix dimension and the number of ones in each row of the matrix.

123

S. Kargar et al.

• Sampling matrix dimension, selection of s in sampling matrixsL : The key to compressed sensing is a low dimensional sampling of the signal vector. The value of s should be determined based on properties of this vector such as its sparsity. Baraniuk [26] showed that a random sampling matrix with the restricted isometry property (RIP) should have sampling dimension s [ ck log L=k , where k is the sparsity of the signal vector which has dimension L, and c is a constant chosen to provide acceptable accuracy. However, in a graph problem where elements of the signal vector are node states and sampling is limited by the existence of connections between nodes, a random sampling matrix is not the best choice. Thus, a generalized sampling matrix is considered which leads to a larger value of s. • Number of ones in each row of the matrix: Determining the number of ones in each row of the matrix (sampling depth), means that in generating each element of y in (3), how many elements of the signal vector x in (3) should participate. In a problem where the signal vector is centralized, this parameter does not have a significant impact on CS performance. However, in a network monitoring problem, any collection of data requires a packet transmission between nodes and so has an effect on performance. • Sampling method: It is more important that all nodes of the network recognize the sampling matrix, so it must be deterministic and computable by every node. Further, as mentioned earlier, an advertiser node should broadcast as many elements of the sampled_links vector as possible. To overcome these limitations, we provide a sampling method which is deterministic and can be obtained before packet communications in the network. The proposed method selects a node from the advertiser node list and then generates sni sampling matrix rows where sni is the number of nodes connected to this node. Thus, this advertiser node will broadcast sni elements from sampled_links. The packet length with this method is equal to that of other methods, but the packets contain more information as the message includes elements of sampled_links rather than just information regarding neighbor nodes. Results are presented in Sect. 6 which can be used to choose the lowest sampling depth for each row in the sampling matrix in order to obtain an acceptable accuracy in the reconstruction process at the nodes. These results can also be used to select the optimum sampling matrix dimension.

3.1 Model Description Suppose there are N nodes in the network with L links between nodes. These links can be directed. Three well-known topology models, namely grid, Waxman and full mesh, are considered. The Waxman model has a random topology with nodes uniformly distributed and edges added according to the distances between nodes. The probability of an edge between nodes i and j is     1 if there is a link between nodes i and j ð7Þ p li;j ¼ a:edi;j=bdmax where li;j ¼ 0 if there is no link between nodes i and j where a [ 0; b  1, d is the distance from node i to node j, and dmax is the maximum distance between any two nodes [27]. The complexity of the Waxman model can be changed by means of the link existence probability distribution. In this paper, the

123

Link State Routing Based on Compressed Sensing

exponential probability distribution is employed with b = 0.2 for the low complex model and b = 0.5 for the high complexity model. Figure 2 shows examples of two network models with N = 9. The grid network in Fig. 2a has L = 12 links between nodes. The node degrees are f4; 3; 2g, so that one node has degree 4, four nodes have degree 3, and four nodes have degree 2. The expected number of links for each node from (7) and (8) is El = 2.67. Thus, each node must broadcast information for approximately 2.67 link states for each topology update. The values for the high complexity Waxman model shown in Fig. 2b are L = 16 and El = 3.5. PN di 2L ð8Þ El ¼ i¼1 ¼ N N Typical routing metrics are latency, loss rate, or link bandwidth, which can be added along paths. For example, the latency of a path is the sum of the latencies of the links on the path, or log (1-loss rate) of a path accounts for the sum of the losses on the links. In this paper, a routing metric is not employed as the goal is to detect anomalous links in the network. The network topology can be expressed as N N1 ¼ link matrixNL  LL1

ð9Þ

where N is a vector of node_ids, L is a vector of link_ids, and link_matrix describe which links are connected to which nodes. In link-state based routing protocols, each node needs to have a full vector of link states and complete form of link_matrix. Topology update methods attempt to gather this information from the entire network.

3.2 Static Algorithm The static algorithm involves two steps. First, we select a basis set of M paths to monitor. This selection only needs to be done once at setup. Then in the second step, based on continuous monitoring of the selected path, the anomalous links in the network are detected.

Fig. 2 a Grid topology, b Waxman topology with b = 0.5

123

S. Kargar et al. Table 1 Algorithm 1: Path selection algorithm Procedure select path

1.

Initialization • Set matrix A and R as empty matrices • Set the list of advertiser nodes and existing nodes empty 2. Repeat step 1 for the S advertiser nodes Step 1: •

Find an advertiser node (n1): If there is a node not in existing nodes, select the node with the largest degree from them. Else select the largest degree node which has not selected as advertiser yet.

• Repeat Step 2 for each neighbor of n1 (n2) Step 2: Repeat this step to select n3 to nD o o o o

Compute the path correlation with matrix R for each link Select paths with the least correlation Select paths continued with the least degree node from them Select paths continued with the least id node from them

o o o o

Add selected path to matrix A Update matrix R Add selected nodes in step 1 and step 2 to existing nodes list Add selected node in step 1 to advertiser nodes list

Step 2.2:

As shown in Table 1, the proposed algorithm selects the node with the highest degree as the first advertiser node and sets all links connected to it as the first links of the corresponding selected paths. For example, in the network in Fig. 2a, node 5 has degree 4 and so is the highest degree node. The four paths which start from node 5 are the first links of the selected paths (shown in matrix A below), and matrix R shows the links in the selected paths. advertiser nodes ¼ fn5 g 2

ð10Þ

3

p1 : n5 n2 6 p2 : n5 n4 7 A¼4 p3 : n5 n6 5 p4 : n5 n8 2

0 6 0 R¼4 0 0

0 0 0 0

0 0 0 0

1 0 0 0

0 0 0 0

0 1 0 0

0 0 1 0

0 0 0 0

ð11Þ

0 0 0 1

0 0 0 0

0 0 0 0

3 0 0 7 5 0 0

ð12Þ

This step is repeated until s advertiser nodes are selected. In each run of step 1, the algorithm in step 2 for each neighbor node of the selected advertiser node is executed. In

123

Link State Routing Based on Compressed Sensing

step 2 for each link of this neighbor node, the correlation with the previous set paths is computed and the least degree node with the least correlation is selected. This step is repeated until a length d path is obtained for each neighbor of the advertiser node. For example for the network in Fig. 2a, path p1 starts at node n5 and continues to node n2 with degree 3 we have 2 choices for the third node (one of the links between node 2 and node 5 which was selected previously). We select the node that leads to a path with the least correlation with the previously selected paths in R. p11 : fn5 ; n2 ; n1 g ) L1 ¼ f100100000000g ) C1 ¼ L1  R0 ¼ ½ 1 1

1

ð13Þ

p12 : fn5 ; n2 ; n3 g ) L2 ¼ f010100000000g ) C2 ¼ L2  R0 ¼ ½ 1 1

1

ð14Þ

In this step C1 and C2 are equal and we select the node with least degree, but n1 and n3 have the same degree and so we select the node with the least id, n1 . This step is repeated for d nodes in each path where d is the depth of sampling. In Sect. 6 we show that about 0.2 9 N nodes are sufficient for advertising the network about link states. Paths selected using this algorithm are less correlated but we want to use all links connected to the selected nodes to increase the information in the packets from the advertiser nodes, and there are some limitations on path selection. In Sect. 6 it is shown that the proposed algorithm reduces the packet transmissions required for topology updates with the highest possible information transmission and acceptable accuracy. Further, in Sect. 7 it is shown that using weighting in the sampling process can increase the probability of anomaly detection.

3.3 Packet Structures Compressed sensing for disseminating link states is suitable for stable networks. At the start, static routing should be used to inform nodes about the network topology and usual link states. Then compressed sampling of the link states is executed. The packet format with compressed sampling of the link states is described in Table 2.

4 Algorithms for Topology Changes During normal operation, new links may appear or disappear, and nodes may enter or exit the network. These changes may cause changes in the sampling matrix. In this section, we consider these changes and adapt the proposed algorithm to these changes.

4.1 Link or Node Addition In a wireless network, nodes may have a new connection to each other due to changes in medium or policies or over time. In this case, nodes which are connected to this new link should advertise the entire network using an interrupt message including the node_ids. Nodes which receive this message update their topology table and add the new link to their lists and then run Algorithm 1 with the new topology. When a new node joins the network, it may generate links with network nodes. These nodes detect the new link and advertise it. Network nodes that receive this advertisement update their topology table and run Algorithm 1. • To provide new nodes with the topology table or matrices in (9),

123

S. Kargar et al. Table 2 Packet format with compressed sampling of the link states

In each time interval of link state updating •

The node which is defined as advertiser node in Algorithm 1 , execute step 1 for all its neighbors until the sampling depth reaches 0: o step 1: Send code req messages to all neighbors Status sum = 0 Sampling depth = d

USN Interface ID Status sum (link state add to this value) Sampling depth (in each traveling of nodes, decrease by 1) o

After step 1 is completed for each neighbor, a node status message containing the status sum of each path with its Interface ID related to the first neighbor of the path is broadcast in the network.

USN Status code

Advertiser node ID Interface ID . . .

Status code • •

Interface ID

Network nodes that receive a node status message update the status code of each path. If all status codes belonging to the current USN were updated, the reconstruction process is executed and the link state vector is returned.

we suggest that one of its neighbors, for example, the neighbor with the lowest degree, provides this information after it has updated its topology.

4.2 Link or Node Deletion Link deletion may happen when the link state is unacceptable or for other reasons. When this happens, nodes connected to it advertise this to other network nodes using an interrupt message and Algorithm 1 is run. When a node leaves the network, all corresponding links are deleted and so an interrupt message is broadcast to all network nodes regarding these deletions. Thus, in Algorithm 1, a node with degree 0 means that the node has left the network and should be ignored.

123

Link State Routing Based on Compressed Sensing

5 Simulation Results As discussed previously, the link state metric can be any link parameter which is important for link management. In this paper, we assume the link metric is throughput. At the start of the simulations, all nodes are announced regarding their link throughput. After a specified interval of time, the proposed method is run. The throughput of the links is compared with the defined throughput and the difference is saved in the differential link state vector. The link throughputs are generated randomly using a normal distribution with mean 0 and variance 0.05. Then k = 3 links are randomly selected as anomalous links and its throughput would change from the set point of throughput. The simulations were run for 1000 iterations and repeated 10 times, and the average taken. The probability of detection error is used performance evaluation which is given by Probability of detection error undetected anomaly links þ false detection of normal links as anomaly links ¼ total number of links probability of accurate detection ¼ 1  probability of detection error

ð15Þ

ð16Þ

Two scenarios are considered for simulation. In the first scenario, the ratio of the number of advertiser nodes to the total number of network nodes is varied between 0.1 and 0.3. In the second scenario, the sampling depth is varied with a constant advertiser node ratio. Simulation is run for 4 model of topology.

5.1 The Number of Advertiser Nodes As described in Sect. 5, the compressed sensing problem is adapted to link state sensing for nodes in a network. Baraniuk   [26] showed that a random sampling matrix with RIP properties and s [ ck log N=k , can provide acceptable detection accuracy. N is the number of links L, k is the estimated number of links with anomalous behavior, and c is a constant. A lower bound on the number of links that should be sampled is then   Ylim [ ck log L=k ð17Þ For example in the network shown in Fig. 2a, Ylim is 8 for c = 1.2 and k = 3. Thus more than 8 paths should be sampled to accurately reconstruct the link state vector with 12 elements. The average number of links connected to each node is less than 3, so at least 3 nodes are required for accurate reconstruction. When compressed sensing is employed there are limitations such as the connections between links, so there are limitations on the sampling matrix randomness which can decrease the detection accuracy. This is compensated for by increasing the number of sampled links. The sampling algorithm is executed on grid networks with 36, 49, 64, and 81 nodes, Waxman b = 0.2, Waxman b = 0.5 and full mesh topologies for various values of Ylim . The simulation results are shown in Fig. 3.

123

S. Kargar et al.

1 0.9

probability of accurate detection

0.8 wxman with beta=0.5

0.7

full mesh waxman with beta=0.2 grid

0.6 0.5 0.4 0.3 0.2 0.1 0 0.1

0.15

0.2

0.25

0.3

0.35

sample node to totl nodes ratio

Fig. 3 Probability of detection versus the advertiser node ratio

Figure 3 shows that 0.25 of the nodes are sufficient to broadcast their coded link states in the network for acceptable detection of anomalous links as the probability of correct detection of anomaly links is more than 95%.

5.2 The Number of Cooperating Links Per Sampling Row In random sampling matrices such as Gaussian random matrices, 0 and 1 appear in a row with equal probability. However, a sampling matrix for compressed sensing has no limitations on the number of 1s in a row, but this is not the case in a network application. In the application of compressed sensing to networks, each 1 in a row of the sampling matrix denotes that a packet transmission should occur between two nodes, so one goal of the sampling algorithm is to reduce the number of links that cooperate in a row of the sampling matrix. The question is then how many links should be sampled in each row of this matrix. Figure 3 can be used to determine the first dimension of the sampling matrix, but the sampled path length is not easily determined. In the other words, when an advertiser node starts state sampling from one of its links, the number of links before termination is not clear. Figure 4 show this for a node with 2 links and sampling depth of 3. The sampling algorithm was run on networks with 36, 49, 64, and 81 nodes in the grid, Waxman b = 0.2 and b = 0.5, and full mesh topologies for various values of d. The simulation results are shown in Fig. 5. A link selection limit of 0.5L is used where L is the number of links in the network. The simulation results demonstrate that d = 4 and s = 0.25N are suitable for accurate anomaly detection.

123

Link State Routing Based on Compressed Sensing

5.3 Throughput Improvement The network peorformance with compressed sensing of links is now compared with general link state routing methods. Simulation using NS3 was conducted with the four topologies and 0.25 of the nodes selected for broadcast. The results in Table 3 show an improvement in network performance of more than 70%.

6 Weighted Compressed Sensing Link State Routing In sampling, it may happen that a group of links appear together when sampled. For example in Fig. 6, links {l1, l2} appear with each other in sampling. This group of links is denoted as ill links in this paper. When an ill link is an anomaly link, it cannot be detected with the proposed compressed sampling link state method and results in a fault in the reconstruction phase. In this section, a weighting of the sampling matrix is proposed to identify ill links by their weighting coefficients.

6.1 Diffusion Wavelets Coifman and Maggioni [15] introduced diffusion wavelets in 2006. Diffusion wavelets are applicable in functions supported on a graph through the use of diffusion operators. Using the diffusion wavelet transform on a network graph, a new representation of a graph function can be obtained which is sparse and in an orthogonal form. The diffusion wavelet transform is based on a diffusion operator, D, which is defined over a network graph. For a graph with E vertices, D is an E 9 E matrix where Di,j is proportional to the correlation or similarity between the function values at vertices i and j. The diffusion operator is dilated by powers of two and translated to obtain orthonormal wavelet bases. Details regarding splitting the space into scaling and wavelet subspaces, and the extraction of diffusion wavelet coefficients, are given in [15].

Fig. 4 A network graph with 9 nodes. The selected path is shown for one advertiser node

123

S. Kargar et al. 1

0.99

probability of accurate detection

0.98

0.97 full mesh

0.96

grid waxman with beta=0.2 waxman with beta=0.5

0.95

0.94

0.93

0.92

0.91

0.9 3

3.5

4

4.5

5

5.5

6

6.5

7

7.5

8

sampling depth

Fig. 5 Detection probability versus the sampling depth Table 3 Reduction in packet transmissions with the proposed algorithm versus the OLSR and the NS3 algorithms

Topology

Packet transmission reduction N = 36

N = 49

N = 64

N = 81

Grid

0.748

0.754

0.732

0.765

Waxman (b = 0.2)

0.737

0.817

0.812

0.815

Waxman (b = 0.5)

0.747

0.775

0.798

0.804

Full mesh

0.755

0.783

0.821

0.821

6.2 Weighting Coefficients In this paper, the network links are graph vertices and the existence of an edge between two vertices depends on the sampling matrix. If there is a sampling path which includes links i and j, then there is an edge between vertices i and j. The strength of Di,j is the number of paths which include links i and j. For example for the sampling matrix in (18), the diffusion operator and network graph are shown in (19) and Fig. 7, respectively. 3 2 1 0 0 1 0 1 61 0 1 0 1 07 7 6 60 1 1 0 0 17 7 6 ð18Þ sampling matrix ¼ 6 1 0 1 1 0 0 7 60 1 0 0 1 17 7 6 40 1 0 1 1 05 1 0 0 1 1 0

123

Link State Routing Based on Compressed Sensing Fig. 6 Ill links in sampling

Fig. 7 The network graph corresponding to the sampling_matrix in (18)

2 6 6 6 D¼6 6 4

0 0 2 3 2 1

0 0 1 1 2 2

2 1 0 1 1 1

3 1 1 0 2 1

2 2 1 2 0 1

1 2 1 1 1 0

3 7 7 7 7 7 5

ð19Þ

For a diffusion operator generated from this description of the network graph, the diffusion wavelet coefficients are generated using the method in [15], so the differential_link_state vector can be expressed as D differential link stateL1 ¼ QLL differential link stateL1

ð20Þ

Using (5), this can be rewritten as D sampled links ¼ sampling matrix  D differential link state ¼ sampling matrix  Q  differential link state

ð20Þ

123

S. Kargar et al.

comparision of weigthening for full mesh topology 1

0.95

probability of annomlly link detection

0.9 DWT weights random weights

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5 0.2

0.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

sampling nodes per total nodes

Fig. 8 Probability of detection for different weighting factors

Thus in the sampling procedure, each node computes the diffusion wavelet coefficients individually and uses them in the encoding operation. The simulation results for the Waxman topology with b = 0.2 and d = 4 given in Fig. 8 demonstrate that the use of weighting coefficients can significantly improve the reconstruction performance. These results also indicate that random weighting coefficients cannot improve reconstruction.

7 Conclusion In this paper, a new link state anomaly detection method was proposed based on compressed sensing. This algorithm was shown to decrease the management packet transmission rate by up to 70% while providing acceptable accuracy in detecting anomalous links. It was shown that in a network with good connections between nodes, the proposed compressed sensing link state algorithm can detect anomalies in the network by broadcasting only 1/4 of the packets required by other methods. A basis set of paths was determined which fully describes the links in the network. Measurements of the basis set are used to infer the state of all links. Further, it was shown that the proposed approach adapts quickly to topology changes. The performance was examined with both grid and Waxman networks. Further, a weighting method based on diffusion wavelet coefficients was proposed to improve the node reconstruction performance. This method increased the

123

Link State Routing Based on Compressed Sensing

accuracy of the proposed compressed sensing link state anomaly detection method by as much as 98% with less than 1/4 of the packet transmissions required with other methods.

References 1. Perkins, C., Belding-Royer, E., & Das, S. (2003). Ad hoc on-demand distance vector (AODV) routing. Internet Engineering Task Force, RFC 3561. 2. Herberg, U., Cole, R., & Clausen, T. (2013). Definition of managed objects for the optimized link state routing protocol, version 2. draft-ietf-manet-olsrv2-mib-11. 3. Nelakudit, S., et al. (2005). Blacklist-aided forwarding in static multihop wireless networks. In Proceedings of the IEEE communications society conference on sensor and ad hoc communications and networks (pp. 252–262). 4. Trivin˜o-Cabrera, A., & Can˜adas-Hurtado, S. (2011). Survey on opportunistic routing in multihop wireless networks. International Journal of Communication Networks and Information Security, 3(2), 170–177. 5. Akyildiz, I. F., & Wang, X. (2005). A survey on wireless mesh networks. IEEE Communications Magazine, 43(9), S23–S30. 6. Biswas, S., & Morris, R. (2004). Opportunistic routing in multi-hop wireless networks. ACM SIGCOMM Computer Communication Review, 34(1), 69–74. 7. Cande`s, E. J. (2006). Compressive sampling. In Proceedings of the international congress of mathematicians, Madrid, Spain (pp 1433–1452). 8. Cande`s, E. J., Romberg, J., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2), 489–509. 9. Cande`s, E. J., Romberg, J. K., & Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8), 1207–1223. 10. Cande`s, E. J., & Tao, T. (2006). Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52(12), 5406–5425. 11. Cande`s, E. J., & Romberg, J. (2006). Quantitative robust uncertainty principles and optimally sparse decompositions. Foundations of Computational Mathematics, 6(2), 227–254. 12. Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289–1306. 13. Haupt, J., Bajwa, W. U., Rabbat, M., & Nowak, R. (2008). Compressed sensing for networked data. IEEE Signal Processing Magazine, 25(2), 92–101. 14. Crovella, M., & Kolaczyk, E. (2003). Graph wavelets for spatial traffic analysis. In Proceedings of the IEEE INFOCOM, San Francisco, CA (pp. 1848–1857). 15. Coifman, R. R., & Maggioni, M. (2006). Diffusion wavelets. Applied and Computational Harmonic Analysis, 21(1), 53–94. 16. Quer, G., et al. (2009). On the interplay between routing and signal representation for compressive sensing in wireless sensor networks. In Proceedings of the information theory and applications workshop, San Diego, CA (pp. 206–215). 17. Bajwa, W., Haupt, J., Sayeed, A., & Nowak, R. (2006). Compressive wireless sensing. In Proceedings of the international conference on information processing in sensor networks, Nashville, TN (pp. 134–142). 18. Fazel, F., Fazel, M., & Stojanovic, M. (2011). Random access compressed sensing for energy-efficient underwater sensor networks. IEEE Journal on Selected Areas in Communications, 29(8), 1660–1670. 19. Srisooksaia, T., Keamarungsi, K., Lamsrichan, P., & Araki, K. (2012). Practical data compression in wireless sensor networks: A survey. Journal of Network and Computer Applications, 35(1), 37–59. 20. Tian, H., Roughan, M., Sang, Y., & Shen, H. (2011). Diffusion wavelets-based analysis on traffic matrices. In Proceedings of the international conference on parallel and distributed computing, applications and technologies, Gwangju, South Korea (pp. 116–121). 21. Coates, M., Pointurier, Y., & Rabbat, M. (2007). Compressed network monitoring. In Proceedings of the IEEE/SP workshop on statistical signal processing, Madison, WI (pp. 418–422). 22. Coates, M., Pointurier, Y., & Rabbat, M. (2007). Compressed network monitoring for IP and all-optical networks. In Proceedings of the SIGCOMM conference on internet measurement, San Diego, CA (pp. 241–252).

123

S. Kargar et al. 23. Lee, O., Kim, J. M., Bresler, Y., & Ye, J. C. (2011). Compressive diffuse optical tomography: Noniterative exact reconstruction using joint sparsity. IEEE Transactions on Medical Imaging, 30(5), 1129–1142. 24. Bowden, R. A., Roughan, M., & Bean, N. (2011). Network link tomography and compressive sensing. ACM SIGMETRICS Performance Evaluation Review, 39(1), 351–352. 25. Xu, W., Mallada, E., & Tang, A. (2011). Compressive sensing over graphs. In Proceedings of the IEEE INFOCOM, Shanghai, China (pp. 2087–2095). 26. Baraniuk, R. G. (2007). Compressive sensing. IEEE Signal Processing Magazine, 24(4), 118–124. 27. Waxman, B. M. (1988). Routing of multipoint connections. IEEE Journal of Selected Areas in Communications, 6(9), 1617–1622. Samane Kargar received the M.Sc. degree in Electrical and Computer Engineering from Isfahan University of Technology, Isfahan, Iran, in 2003. She is currently pursuing the Ph.D. degree in Electrical and Computer Engineering at Isfahan University of Technology, Isfahan, Iran. Her research interests include signal processing, compressed sensing, mobile ad hoc networks (MANETs) and wireless mesh networks (WMNs). Thr author figure has been sent as an attachment.

Faramarz Hendessi received the B.S. in Electronic Engineering from the Sistan and Balouchestan University, Iran in 1986. He received the M.S. degree in Electrical Engineering from Isfahan University of Technology, Iran in 1988 and the Ph.D. degree in Electrical Engineering from Carleton University, Canada. He is now an Associate Professor in the Department of Electrical and Computer Engineering, Isfahan University of Technology, Iran. His current research interests include wireless and mobile networks, network and design and management, network security, RFID and its applications, software engineering and library and information management and solutions. He is a Member of Consulting Group, Iran Data Company, Ministry of Information and Communication Technology, Iran. He is also a Member of Consulting Group, Iran Mobile Company, Ministry of Information and Communication Technology, Iran.

123

Link State Routing Based on Compressed Sensing T. Aaron Gulliver received the B.Sc.(Eng.) and M.Sc.(Eng.) degrees in Electrical Engineering from the University of New Brunswick, Fredericton, New Brunswick, in 1982 and 1984, respectively, and the Ph.D. degree in Electrical Engineering from the University of Victoria in 1989. He is now a Professor in the Department of Electrical and Computer Engineering at the University of Victoria. His research interests include algebraic coding theory, information theory, cryptography, design and construction of error correcting codes decoding and implementation of error correcting codes, soft decision decoding of block codes, turbo codes and iterative decoding, error control coding for computer memories, ultra-wideband and spread spectrum communication systems, mobile and personal communications, OFDM, smart grid and green communications.

123