The Study on Wireless Mesh Networks Security based on Improved Coding Scheme

Abstract. In a multi-hop wireless mesh network， wireless links are vulnerable due to severe channel fading， interference and physical damage. In this paper， we will provide a coding scheme to protect from multiple failures in wireless mesh networks to achieve high throughput where the redundancy is considered for the average number of failures. Our coding scheme is designed to protect from the average number of failures to increase the network throughput. When the number of failures is more than the average case， the destination will have to wait for more coded packets in the following time slots.

Key words： Network Security， link failure， survivability.

1. Introduction

Network protection is used to deal with link or node fault. The traditional network protection scheme can achieve 1：1， 1 + 1， and 1： N protection， from a single node/link failure. And coding， it is possible to achieve 1 + N protect it to use the minimal redundancy resources to recover any single connection/node fault and minimum delay time [2]. Figure 1 gives an example that the traditional coding based protection plan will reduce the network throughput. In different time period of failure is different. We assume that the k Max = 3. We assume that there are three failed time 1 and only a failure time 2. The average number of failure is 2. Figure 1 （a） description coding-based protection plan in the biggest failure of protected all period of time， where the coding coefficient is the same， if they are all in the same way in the two sessions. The original data packets in different time will separate decoding. From Fig. 1（b）， we note that some original data packet s which are sent in time slot 1 are still encoded into the following time slot. With the coding scheme in Fig. 1（a）， D can receive 4 original data packets in 2 time slots. However， D can receive 6 linear independent combinations and decode out 6 original data packets in two time slots with the coding scheme in Fig. 1（b）. Obviously， we can achieve higher network throughput with the coding scheme in Fig. 1（b）.

Fig. 1. Compare the coding scheme with /without considering the different failures in different time slots.

2. A CODING-BASED P ROTECTIONP ROBLEM FOR M ULTIPLEFAILURES

2.1 Network Model

In our studies， we consider a wireless mesh network as an acyclic graph G = （V， E）， V is vertex group （or nodes） and E is a set of edge （or link）. Have a source s， a destination， D and M edge-disjoint them between the paths. We further assume that every link in G have the same unit ability. In f bill， we can put a link with specific performance C （a natural number） C link， each with a unit of ability. We assume this period where will create a series of original source packets， code of a linear combination， and sends them to the destination.

Since wireless links are vulnerable， we exploit coding to provide protection in which M coded data packets will be generated by linearly combining original data packets and in each time slot one coded data packet will be transmitted on one edge-disjoint path. is denoted as the failure probability that there are i edge-disjoint paths failing simultaneously， where 0 ≤ i ≤ M . In different time slots， there will be the different number of edge-disjoint paths failing simultaneously. is the expected path failures in the same time slot， where gets the nearest integer， and let N = M - k .We assume S can encode N original data packets per time slot and transmit towards D .

2.2 Problem Description

In some period of time， the destination of the packet may not decode received when the amount of code the failure is more thank. On the other hand， in some period of time， the number of failure may not thank. In this period of time， if the source coding part of the original send packets in front of the time with the original data packets sent to send the current time slot， the goal will be able to decode the original data packets sent in front of the time.

In this letter， our goal is to design a linear coding scheme the protection from the average number of failure， improve the network throughput. Our analysis shows that， as long as the average number of failure is not more than k， destination can decode and take back even if the number of original data packets failure in some time is more than k and some cost to send feedback source.

2.3 Notations

3. A LINEAR CODING SCHEME

In this section， we design a linear coding scheme the protection from the multiple failures in the wireless network. Coding scheme requires any N received in every time slot linear combination is irrelevant. Otherwise， it will introduce the redundant code bag and waste of the network bandwidth. Not until the time slot decoding destination during receiving N t the combination of goals.

Algorithm 1： source

Algorithm 2： destination

The proposed solutions destination buffer requirements of the code receive packets. In the final hour slot t， if the target has not received any coding data than N small packets in the time slot t， it can decode and restore all of the original data packets， define the buffer and prepare for the next round of spread and send 1 ACK， notice the source starting a new transmission round. Otherwise， the destination will report number of coding data to receive packets in time （ct） ACK， waiting for the following new code in the period of time and then packets.

At the end of time slot t ，if t =1， the source will clear its buffer to get ready for a new transmission round and put N new original data packets to its buffer， otherwise， the source will remove original data packets in its buffer according to the received ACK and put new original data packets to its buffer， if . When ， the source will set t =1to start a new transmission round. In each time slot， the source will encode all N original data packets in its buffer into M coded packets and send them to the destination.

Let be the number of coded data packets received by the destination during time slot t， and ， . Let

（1）

We define the time slots from time slot 1 to time slot T as one transmission round. We will prove that the destination can decode and recover all original data packets in a transmission round T.

Lemma 1： When T =1， the destination can decode and recover the N original data packets.

Proof： When T =1， the destination can receive coded data packets. The encoding vector of each coded data packet is one row vector in the matrix X. Note that not all square sub matrices of a Vandermonde matrix are non-singular [6][7]. When we construct matrix X， xi， for is randomly generated so that ， for and . Thus， any N × N submatrix of X is non-singular. Therefore， N original data packets can be decoded out.

Lemma 2： When T =2， the destination can decode and recover all original data packets in this transmission round.

Proof： When T =2， the destination receives no less than N coded data packets at time slot 2. With the same reason in the proof of Lemma 1， the destination can decode out N original data packets of time slot 2.

We suppose that it receives coded data packets in time slot 1. With the coding scheme， we can decode out N original data packets sent at time slot 2， which means that original data packets have been decoded out. Without loss of generality， l et the coefficient matrix of these coded data packets received at time slot 1 be Therefore， the matrix can be represented as follows， which is composed by coefficient vectors of the coded packets and original data packets sent at time slot 1 which are decoded out at time slot 2.

（2）

If ， all original data packets sent at time slot 1 can be decoded out at time slot 2， because the source will not generate new original data packets at time slot 2. Otherwise， if obviously， the block matrix in the left upper corner of the matrix is a dimensional Vandermonde matrix. Therefore， each column vector in can be transformed to a zero matrix by transforming rows. The matrix can be transformed to be matrix by row transformations：

（3）

and

Since the block matrix is a dimensional Vandermonde matrix and ， ，we have

Therefore， we have ， which indicates that all original data packets generated in time slot 1 can be decoded out if the coded packets received at time slot 2 are no less than N. Thus， the lemma is verified.

Theorem 1： Once the destination receives no less than N coded data packets at time slot T， it can decode and recover all original data packets from T time slots.

Proof： According to Lemma 1 and Lemma 2， the theorem holds when T =1， 2. When ， it means that ， and . The destination receives no less than N coded data packets at time slot T. With the same reason in the proof of Lemma 1， the destination can decode out N original data packets of time slot T.

4. CONCLUSION

Network protection scheme based on code has plans for a wireless network， optical fiber network， and wireless-optical access network mixed， respectively. We prove surveys the proposed coding scheme. The simulation results verify the solutions can improve throughput greatly and the other two transmission program.

References

[1] L.F. Akyildiz， X. Wang， and W. Wang， “A survey on wireless mesh networks，” Computer Networks， vol. 47， no. 4， pp. 445487， 2010.

[2] O. M. Al-Kofahi and A. E. Kamal， “Network coding-based protection of many to one wireless flows，” IEEE J. Sel. Areas Commun.， vol.27， no. 5， pp. 797813， June 2010.

[3] S. A. Aly， A. E. Kamal， and A. I. Walid， “Network protection design using network coding，” in Proc. 2010 Information Theory Workshop， pp. 15.

[4] A. E. Kamal， “1+N network protection for mesh networks： network coding-based protection using p-cycles，” IEEE/ACM Trans. Networking， vol. 18， no. 1， pp. 6780， Nov. 2011.

[5] S. F. Dai， J. Wang， X. M. Zhang， and S. L. Li， “Network coding- based 1+N protection scheme in hybrid wireless-optical broadband access networks，” International ICST Conference on Communications and Networking in China， vol. 27， no. 5， pp. 797813， Aug. 2011.

[6] J. Lacan and J. Fimes， “Systematic MDS erasure codes based on Vandermonde matrices，” IEEE Commun. Lett. ， vol. 8， no. 9， pp. 570 572， Sep. 2004.

[7] F. J. MacWilliams and N. J. A. Sloane， the Theory of Error-Correcting Codes. North Holland， 1977.