KR20130091123A - Node, method and device for setting routing in wireless mesh network - Google Patents

Abstract

Disclosed are a node, a routing setting method, and an apparatus in a wireless mesh network. In the wireless mesh network, a routing setting method includes: (a) obtaining jitter information of each node included in each of multiple paths from a source node to a destination node; And (b) setting routing from the source node to the destination node using the jitter information of each node. According to the present invention, by setting the routing in consideration of the jitter characteristic of the packet, there is an effect of ensuring the quality of jitter performance which is most important in OoS of real-time data transmission.

Description

Node and routing setting method and apparatus in wireless mesh network {NODE, METHOD AND DEVICE FOR SETTING ROUTING IN WIRELESS MESH NETWORK}

Embodiments of the present invention relate to a node, a routing configuration method and apparatus in a wireless mesh network, and more particularly, to a node, a routing configuration method and apparatus in a wireless mesh network considering jitter information.

A wireless mesh network consists of a mesh router and a mesh client. The mesh router acts as a bridge to connect different networks and as a gateway to the Internet and performs as a wireless backbone network. As a wireless terminal, the mesh client acts as a router for transmitting data as well as a host for directly transmitting and receiving data as in an ad hoc network. It also acts as a gateway to the mesh router.

1 is a diagram illustrating a structure of a general wireless mesh network. As shown in FIG. 1, the mesh routers 101 to 110 constituting the wireless mesh network 100 are connected wirelessly, and the nodes of the existing ad hoc network are composed of several hops between different mesh routers. Similarities can be found.

However, mesh routers have no mobility and energy constraints, and they are used as wireless infrastructure backbones that act as gateways and bridges that carry data rather than origins or destinations. It has different characteristics. In addition, most of the flow of data that must pass through the gateway between mesh routers. This is especially the case with voice or video data traffic that must satisfy the service quality.

As more kinds of data such as VoIP and video transmission are required in the wireless mesh network, various technologies are developed in the fields of scheduling and packet format for optimal real-time data transmission. It is becoming. However. Research on routing algorithms and protocols for quality assurance of real-time traffic is relatively incomplete.

Existing routing algorithms for wireless mesh networks include Minimum Hop (MH) and Expected Transmission in wireless mesh network protocols such as Optimized Link State Routing protocol (OLSR) and Ad Hoc On-demand Distance Vector-Spanning Tree (AODV-ST). Metrics such as Count (hereinafter referred to as ETX) are used. Academic Papers C.E. Koksal and H. Balakrishnan, "Quality-Aware Routing Metrics For Time-Varying Wireless Mesh Networks," IEEE JSAC, vol. 24, no. 11, pp. In 1984-94, Nov. 2006, the ETX algorithm is disclosed.

MH is a routing algorithm where the end-to-end transmission path is connected with the minimum hop because every link has a link cost of 1, and ETX broadcasts the inter-node probe in advance, As an algorithm considering the reception success rate, it is a routing algorithm that selects an end-to-end path with stable transmission success rate. However, in the conventional research, no routing algorithm considering jitter, which is a quality of service (QoS) parameter important for real time transmission, has not been studied.

In order to solve the problems of the prior art as described above, the present invention proposes a node, a routing setting method and apparatus in a wireless mesh network for setting up a routing in consideration of jitter information.

Other objects of the present invention may be derived by those skilled in the art through the following examples.

According to a preferred embodiment of the present invention to achieve the above object, in the routing setting method in a wireless mesh network, obtaining jitter information of each node included in each of the multiple paths from the source node to the destination node (a); And (b) setting the routing from the source node to the destination node using the jitter information of each node.

The nodes may calculate different jitter information according to the priority of traffic entering the nodes.

The jitter information at each node may be calculated using at least one of the priority of the traffic, the period of the traffic, the arrival rate of the traffic, and the service rate of the traffic.

The period of the traffic may be calculated using the transmission period of the traffic and the retransmission probability of the packet included in the traffic.

The step (b) may include: calculating end-to-end jitter variance of each of the multipaths using jitter information of each node included in each of the multipaths; And selecting (b-2) any one path among the multipaths having the minimum end-to-end jitter dispersion.

The end-to-end jitter variance of any one of the multipaths may be calculated using at least one of the sum of the variance of the jitter information of each node included in the one path and the sum of the covariances.

The step (a) is to obtain multipaths for all nodes between the source node and the destination node in the wireless mesh network, and jitter information of the nodes accumulated through the nodes included in each of the multipaths. (B-1) may calculate the end-to-end jitter variance of each of the multipaths using jitter information of each of the accumulated nodes.

The step (a) may obtain jitter information of the respective nodes flooded from the respective nodes.

Each node may flood a hello message of an optimized link state routing (OLSR) protocol including the jitter information to neighbor nodes of the nodes.

According to another embodiment of the present invention, an apparatus for setting a routing path in a wireless mesh network, the apparatus comprising: a jitter information acquisition unit for acquiring jitter information of nodes included in each of multiple paths from a source node to a destination node; And a routing setting unit configured to set routing from the source node to the destination node using the obtained jitter information of the nodes.

The routing setting unit may include: a jitter variance calculator for calculating end-to-end jitter variance of each of the multipaths using jitter information of each node included in each of the multipaths; It may include a path selector for selecting a path having the least end-to-end jitter distribution of the multi-path.

The end-to-end jitter variance of any one of the multipaths may be calculated using at least one of the sum of the variance of the jitter information of each node included in the one path and the sum of the covariances.

According to another embodiment of the present invention, in a node included in a wireless mesh network, at least one of the priority of the traffic entering the node, the period of the traffic, the arrival rate of the traffic, and the service rate of the traffic A jitter information calculator for calculating jitter information of the node; And a communication unit for flooding the jitter information to a neighboring node of the node.

The communication unit may flood the neighbor node with a hello message of an optimized link state routing (OLSR) protocol including the jitter information.

According to the present invention, by setting the routing in consideration of the jitter characteristic of the packet, there is an effect of ensuring the quality of jitter performance which is most important in OoS of real-time data transmission.

1 is a diagram illustrating a structure of a general wireless mesh network.
2 is a block diagram illustrating a detailed configuration of a node of a wireless mesh network according to an embodiment of the present invention.
3 is a diagram illustrating an example of a routing information exchange message according to an embodiment of the present invention.
4 is a block diagram illustrating a detailed configuration of a routing setting device for setting routing in consideration of jitter information according to an embodiment of the present invention.
FIG. 5 is a flowchart illustrating an overall flow of a method for setting routing in consideration of jitter information according to an embodiment of the present invention.
6 is a diagram illustrating a pseudo code for describing a routing setting method according to an embodiment of the present invention.
7 is a diagram illustrating a structure of a wireless mesh network for performance evaluation according to an embodiment of the present invention.
8 is a diagram illustrating a simulation result of a transfer rate of each routing setting method according to jitter bound required by a wireless mesh network according to an embodiment of the present invention.
FIG. 9 is a diagram illustrating a simulation result of an average and variance of end-to-end jitter of each routing setting method in a wireless mesh network environment according to an embodiment of the present invention.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the invention is not intended to be limited to the particular embodiments, but includes all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. Like reference numerals are used for like elements in describing each drawing.

Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings.

Jitter, a quality of server (QoS) parameter that is important for real-time transmission of data, refers to a deviation in delay speed that is changed by a change in a constant speed delay. If there is a large jitter delay variation in voice transmission, it is difficult to hear the correct voice. Therefore, hereinafter, a routing setting apparatus and method considering jitter information in a wireless mesh network will be described.

The wireless mesh network is composed of a plurality of wireless mesh routers and will be described with a mesh router as a node for the sake of clarity, and it is assumed that a source node means a starting point of data and a destination node means a destination of data.

According to an embodiment of the present invention, the wireless mesh network model may be described as follows. Each node in the network transmits time-slot-based statistical time-division multiplexing (TDM), and may use selective reject ARQ as an Automatic Repeat-Request (ARQ) protocol.

Examples of TDM transmission-based wireless mesh networks include IEEE 802.16 networks and Deterministic Synchronized Multichannel Extension (DSME) of the IEEE 802.15.4e standard.

According to the present invention, a packet transmitted between nodes may be configured by differentially setting a path according to priority and a model for differential may be assumed as follows.

The packet may have a non-preemptive based priority, and the priority of the packet may be set in ascending order according to the class. That is, a class 1 packet has a higher priority than a class 2 packet. Packets with the same priority may be subject to First-In First-Out (FIFO) transmission.

로 정의된다. m 번째 타임슬롯 구간은 m과 T가 모두 0이 아닐 때,

와 같이 정의된다. 노드 간 전송되는 패킷을 포함하는 트래픽은

의 전송 주기를 가지며 패킷 재전송 확률

를 고려한 트래픽의 주기

는

와 같이 정의된다. The network system follows a discrete time queuing process, and the timeslot is in the range where t is greater than or equal to zero.

. The m th timeslot interval is when both m and T are nonzero,

Respectively. Traffic that includes packets sent between nodes

Packet retransmission probability with a transmission period of

Frequency of traffic considering

The

Respectively.

Here, the packet retransmission probability may be expressed as in Equation 1 below.

[ Equation 1 ]

는 패킷 재전송의 제한 횟수를 의미한다. 즉 수학식 1은 패킷 에러가

번 이상 발생하는 경우 패킷 재전송을 하지 않는 전송 모델에서의 패킷 재전송 확률을 의미한다.Where p is the packet error probability,

Denotes a limit number of packet retransmissions. Equation 1 is a packet error

If it occurs more than once, it means the probability of packet retransmission in the transmission model that does not retransmit the packet.

패킷이며, 노드 i에서 클래스 n 트래픽의 도착율(arrival rate)은

로 정의된다. The traffic service rate of the network is

Packet, the arrival rate of class n traffic at node i is

.

로,

와 같이 계산할 수 있으며 노드 i의 유틸리티의 총 합은

로 정의된다.Thus, the utility of class n traffic on node i

in,

And the total sum of the utilities on node i is

.

2 is a block diagram illustrating a detailed configuration of a node constituting a wireless mesh network according to an embodiment of the present invention.

The node 200 may include a jitter information calculator 201 and a communicator 203.

The jitter information calculator 201 calculates jitter information of the node. In more detail, the jitter information calculator 201 may calculate jitter information of the node using at least one of a priority of traffic entering the node, a period of the traffic, an arrival rate of the traffic, and a service rate of the traffic. have.

According to an embodiment of the present invention, the jitter information calculated by the jitter information calculation unit 201 may include a probability mass function for a period of traffic, a priority of traffic, an arrival rate of traffic, and a service rate of traffic. PMF) and may be expressed as Equation 2 below.

& Quot; (2 ) & quot ;

는 확률 질량 함수로서 노드 i에서 클래스 n 트래픽의 m 번째 패킷이 경험하는 지터에 대한 랜덤 변수

가 j일 확률을 의미한다. 지터 랜덤 변수

는 노드 i를 지나는 클래스 n 트래픽의 m 번째 패킷과 (m+1) 번째 패킷의 타임슬롯에서의 위치 차이에 기반을 두고 있다.here,

Is a random mass function, a random variable for the jitter experienced by the m th packet of class n traffic at node i.

Is the probability of j. Jitter random variables

Is based on the positional difference in the timeslots of the m th packet and (m + 1) th packet of class n traffic passing through node i.

가 j일 확률은 관찰하고자 하는 클래스 n 트래픽보다 높은 우선 순위를 갖는 패킷이 a개 존재할 확률 (1), 관찰하고자 하는 클래스 n 트래픽보다 높은 우선 순위를 갖는 패킷이 a개 존재할 때 클래스 n 패킷은 k 개인 조건부 확률 (2) 및 관찰하고자 하는 클래스 n 트래픽보다 높은 우선 순위를 갖는 패킷이 a개 이며 클래스 n 패킷은 k 개일 때 관찰하고자 하는 트래픽의 m 번째 패킷이 경험하는 지터가 j일 조건부 확률 (3)의 곱으로 유도할 수 있다.

Is a probability that a packet has a higher priority than the class n traffic to be observed (1), and a class n packet is k when there is a packet having a higher priority than the class n traffic to be observed. The conditional probability that the jth experienced by the mth packet of the traffic to be observed is 3 when a private conditional probability (2) and a packet with a higher priority than the class n traffic to be observed and k class n packets are (3) Can be derived as a product of

 In more detail, the probability (1) of existence of a packet having a higher priority than class n traffic to be observed may be expressed by Equation 3 below.

& Quot; (3 ) & quot ;

은 관찰하려는 클래스 n 트래픽이 서비스에 들어가기 전에 더 높은 우선순위를 갖는 a개의 패킷이 타임슬롯을 차지하고 있을 확률이다. 높은 우선순위를 갖는 트래픽은

인 조건에서

의 확률로 도착함을 나타낸다. 이 식은 Bilateral geometric Function (BGF)에 근거하여 유도되며,

는 노드 i에서 클래스 1부터 n까지의 모든 재전송되는 패킷들과 우선순위가 높은 패킷들의 도착 확률을 의미한다. 이는

을 통해 얻을 수 있다.here,

Is the probability that a packet of higher priority occupies timeslot before class n traffic to observe enters service. High priority traffic

Under conditions

A probability of arrival. This equation is derived based on Bilateral geometric Function (BGF),

Denotes the arrival probability of all retransmitted packets and high priority packets of class 1 to n in node i. this is

You can get it through

Subsequently, when there are a packets having a higher priority than the class n traffic to be observed, the k n conditional probability 2 may be expressed by Equation 4 below.

[ Equation 4 ]

은 (m+1) 번째 타임슬롯에 도착하는 모든 클래스 n 패킷의 수,

는 (m+1) 번째 주기에 도착하는 클래스 n 트래픽 보다 높은 우선순위를 가진 패킷들과 ARQ 패킷들의 수를 모두 합친 수를 의미한다. here,

Is the number of all class n packets arriving in the (m + 1) th timeslot,

Denotes the sum of the number of ARQ packets and packets having higher priority than class n traffic arriving in the (m + 1) th period.

와 같이 계산될 수 있으며 여기서,

는 노드 i에서 (m+1)번째 주기에 도착하는 모든 클래스(n-1) 패킷의 수를 나타낸다. 단, 지터 특성을 관찰하고자 하는 트래픽의 (m+1) 번째 패킷보다 먼저 버퍼에 들어오는 패킷이여야 한다.this is

Can be calculated as

Denotes the number of all class (n-1) packets arriving at the (m + 1) th period in node i. However, it must be a packet entering the buffer before the (m + 1) th packet of the traffic for which the jitter characteristic is to be observed.

은 노드 i의 (m+1) 번째 타임슬롯에서 관찰하고자 하는 클래스 n 트래픽보다 높은 우선 순위를 갖는 패킷이 a개가 존재할 때, 클래스 n 패킷은 k 개인 확률을 나타내는 조건부 확률이다. 이는 T개의 타임슬롯에서 클래스 n 트래픽이 차지할 수 있는 슬롯의 수가

개이며, 한 타임슬롯을 차지할 확률이

인 경우에 대한 Binomial distribution으로 구할 수 있다. 즉, 하기의 수학식 5의 공식이 성립한다.In Equation (4)

Is a conditional probability that represents a probability that k class n packets have a packet having a higher priority than class n traffic to be observed in the (m + 1) th timeslot of node i. This is the number of slots occupied by class n traffic in T timeslots.

Dog, and the probability of taking a time slot

It can be obtained as Binomial distribution for. That is, the formula of Equation 5 below holds.

[ Equation 5 ]

조건을 만족해야 한다. Provided that the number k of class n packets and the number a of packets with higher priority than class n

The condition must be met.

Then, when there are a packets having a higher priority than the class n traffic to be observed and the class n packets are k, the conditional probability (3) that jitter experienced by the mth packet of the traffic to be observed is j It can be expressed as Equation 6.

&Quot; (6) "

인 범위 내에서의 triangle distribution 으로 나타난다. Equation (6) shows that there are a packets having a higher priority than class n traffic to be observed in the (m + 1) th time slot of node i. As a conditional probability that jitter is j,

It is represented by a triangle distribution within the range of.

는 노드 i에서 클래스 n 트래픽에 대한 일반적인 (generalized) 지터의 랜덤변수로써

로 나타낼 수 있다.Considering the ergodic characteristics of the traffic, the random variable that can be obtained from Equation 2

Is a random variable of generalized jitter for class n traffic at node i.

.

Accordingly, the probability mass function of Equation 2 may be expressed as a product of Equations 3, 4 and 6, and may be expressed as Equation 7 below.

[Equation 7]

Therefore, the jitter information calculated by the jitter information calculator 201 may be expressed as a probability mass function (PMF) for the period of traffic, the priority of traffic, the arrival rate of traffic, and the service rate of traffic as shown in Equation (7). .

The communication unit 203 floods the jitter information calculated by the jitter information calculator 201 to neighboring nodes.

According to an embodiment of the present invention, the communication unit 203 may transmit the jitter information in a routing path setting message and a field for including jitter information may be added to the existing routing information exchange message.

3 is a diagram illustrating an example of a routing information exchange message according to an embodiment of the present invention.

The routing information exchange message of FIG. 3 uses the Hello message defined in the RFC 3626 document to support jitter information exchange for support of link sensing, neighborhood detection, and later extended services in the optimized link state routing (OLSR) protocol. Message form with fields added.

As shown in FIG. 3, the Hello message-based jitter information transmission message of OLSR defined in RFC 3626 transmits jitter information calculated by a node to neighbor nodes. The J field 301 may allocate an existing reserved field of 10 bits and transmit jitter information based on a floating point number. However, the 32-bit single-precision and 64-bit double-precision formats defined in IEEE 754 have too many bits to apply to wireless mesh networks, and jitter information is always signed with a value greater than zero. Since no bits are used to indicate, follow the standard of floating point sign, exponent, and mantissa, but assign 0 bits, 3 bits, and 7 bits to each component so that the variance value of jitter information greater than 0 is 0 ~. It can express up to 128 and has an accuracy of 0.001 or higher. However, the bit allocation of the exponent part and the mantissa part is exemplary, and an embodiment in which the bit allocation of each floating point component is different according to the accuracy and jitter information dispersion required by the network is possible.

In addition, the message format described in FIG. 3 is merely exemplary, and the message format used in various modifications and other network protocols may be applicable thereto.

4 is a block diagram showing a detailed configuration of a routing setting device for setting routing in consideration of jitter information according to an embodiment of the present invention.

According to an embodiment of the present invention, the routing setting device may be included in each node and is a device for performing routing setting, and selects a path to a destination node using jitter information obtained from the nodes.

Referring to FIG. 3, the routing setting apparatus 400 may include a jitter information obtaining unit 401 and a routing setting unit 403.

The jitter information acquisition unit 401 receives jitter information of nodes included in each of the multiple paths from the source node to the destination node. The jitter information may be jitter information flooded by the communication unit 203 of the node 200.

The jitter information of nodes included in each of the multipaths obtained by the jitter information acquisition unit 401 may be recorded in the routing table together with the multipath information.

는 클래스 n 트래픽의 노드

부터

까지의 라우팅 경로를 의미하며, 기록된 경로

에 대한 종단간 지터 정보

는 각 노드를 거치며 축적되는 지터의 합이므로

를 계산하여 산출할 수 있다. 종단간 지터 정보

의 확률 질량 함수(PMF)는 각 경로상의 각 노드에서의 지터 변수

의 PMF의 convolution(

로 표기함)으로 구할 수 있으며, 하기의 수학식 8과 같이 표현할 수 있다.Information written to the routing table

Is a node of class n traffic

from

The routing path up to and including the recorded path

-To-end jitter information for

Is the sum of the jitter accumulated over each node,

It can be calculated by calculating. End-to-End Jitter Information

The probability mass function of is the jitter variable at each node on each path.

PMF convolution (

It can be expressed as, and can be expressed as shown in Equation 8 below.

&Quot; (8) "

는 노드

부터

까지의 종단간 지터 정보

의 확률 질량 함수를 의미한다.here,

Is a node

from

End-to-end jitter information

Means the probability mass function.

The routing setting unit 403 sets the routing from the source node to the destination node using the jitter information of the nodes obtained by the jitter information obtaining unit 401.

For example, the routing setting unit 403 may select a path having the minimum distribution of end-to-end jitter from the source node to the destination node.

According to an embodiment of the present invention, the routing setting unit 403 may include a jitter variance calculator 411 and a path selector 413.

The jitter variance calculator 411 calculates the end-to-end jitter variance of each of the multipaths using the jitter information of each node included in each of the multipaths.

Here, the path selector 413 may select a path having the minimum end-to-end jitter distribution among the multiple paths.

At this time, the end-to-end jitter distribution of any one path among the multiple paths calculated by the jitter variance calculator 411 uses at least one of the sum of the variance and the covariance of the jitter information of the nodes included in any one path. Can be calculated.

According to an embodiment of the present invention, the variance value of the jitter information may be expressed as in Equation 9 below.

&Quot; (9) "

는 노드 i에서 클래스 n 트래픽의 지터 분산을 의미한다. 즉, 수학식 7에서 얻을 수 있는 노드의 지터 확률 질량 함수(PMF)로부터 분산 계산 공식으로 유도된다.here,

Denotes jitter distribution of class n traffic at node i. That is, the variance calculation formula is derived from the jitter probability mass function (PMF) of the node obtained in Equation (7).

의 분산은 노드

부터

까지의 종단간 경로상에서 각 지터 변수의 분산의 합 및 공분산의 합으로부터 구할 수 있으며, 아래의 수학식10과 같이 표현할 수 있다.End-to-end jitter

Distribution of nodes

from

It can be obtained from the sum of the variance and the covariance of each jitter variable on the end-to-end path up to and can be expressed by Equation 10 below.

[Equation 10]

는 노드

부터

까지의 종단간 지터 분산,

는 클래스 n 트래픽의 노드 i 와 노드 j의 지터 변수간의 공분산을 의미한다.here,

Is a node

from

End-to-end jitter dispersion,

Denotes the covariance between the j j variables of node i and node j of class n traffic.

이며, 종단간 지터 분산은

와 같이 각 노드가 간단한 계산을 수행하여 산출할 수 있다. 시뮬레이션 결과 경로 선택부(413)에서 최소의 종단간 지터 분산을 가지는 경로를 선택하는 경우 지터 변수간 의존도(dependency) 여부에 따른 차이가 크지 않으므로 계산량을 줄여 전력 소모 및 시간 지연을 줄이기 위해 공분산

를 0으로 설정하고 계산하는 것이 가능하다.Jitter between nodes is independent of each other

End-to-end jitter dispersion is

Each node can calculate by performing a simple calculation. When the path selector 413 selects a path with the minimum end-to-end jitter variance, the difference in dependence between jitter variables is not large. Therefore, the covariance is reduced in order to reduce power consumption and reduce time delay.

It is possible to set to 0 and calculate.

를 라우팅 메트릭으로 설정한다. 즉 각 노드가 자신의 통신환경(트래픽의 주기, 트래픽의 우선순위, 트래픽의 도착율, 서비스율, 패킷 재전송율)로부터 지터 확률 질량 함수 및 분산을 수학식 9와 같이 계산하여 라우팅 메트릭으로 설정한다. 경로 선택부(413)에서 종단간 지터 분산을 최소화하는 경로를 선택하기 위해 지터 분산 산출부(411)는 수학식 10과 같이 라우팅 메트릭의 합인

을 최소화하는 경로를 선택하게 된다.Thus, the present invention provides jitter distribution of class n traffic at node i.

Is set to the routing metric. That is, each node calculates the jitter probability mass function and variance from its communication environment (traffic period, traffic priority, traffic arrival rate, service rate, packet retransmission rate) as Equation 9 and sets it as a routing metric. In order to select a path that minimizes end-to-end jitter variance in the path selector 413, the jitter variance calculator 411 may calculate a sum of routing metrics as shown in Equation 10.

You choose a path that minimizes

FIG. 5 is a flowchart illustrating an overall flow of a method for setting routing in consideration of jitter information according to an embodiment of the present invention.

Hereinafter, a process performed at each step will be described with reference to FIG. 5.

First, in step S500, the jitter information acquisition unit 401 obtains jitter information of nodes included in each of the multiple paths from the source node to the destination node.

In this case, the jitter information of each node may be calculated by varying the jitter information according to the priority of traffic entering each node, and the jitter information may be calculated from among the priority of traffic, the period of traffic, the arrival rate of traffic, and the service rate of traffic. It can be calculated using at least one.

In addition, each node may flood a hello message of an optimized link state routing (OLSR) protocol including jitter information to neighboring nodes of the respective nodes, and the jitter information acquisition unit 401 is a hello message flooded from each node. To receive jitter information of each node.

In more detail, in step S500, the jitter information acquisition unit 401 obtains the multipaths for all nodes between the source node and the destination node in the wireless mesh network, and accumulates through the nodes included in each of the multipaths. Obtain their jitter information.

In step S505, the jitter variance calculator 411 calculates the end-to-end jitter variance of each of the multipaths using jitter information of each node included in each of the multipaths.

Finally, in step S510, the path selector 413 selects a path having the minimum end-to-end jitter distribution among the multiple paths.

FIG. 6 is a diagram illustrating a pseudo code for explaining a routing setting method according to an embodiment of the present invention.

The notation and description of the variable using FIG. 6 in the pseudo code is as follows.

는 무선 메쉬 네트워크 내 모든 노드의 집합,

은 트래픽 우선순위에 따라 차등화 무선 메쉬 네트워크에서 다루는 클래스의 집합, s는 소스 노드,

은 경로 선택 알고리즘에서 클래스 n 트래픽의 경로로써 선택한 노드의 집합,

는 노드 i의 이웃 노드의 집합 (1 홉으로 연결되는 노드의 집합),

는 클래스 n 트래픽의 노드 s로부터 노드 i까지의 라우팅 비용, 즉 수학식 9과 수학식 10으로부터 구할 수 있는 지터 정보의 분산을 의미한다.

Is a set of all nodes in a wireless mesh network,

Is the set of classes covered by the differential wireless mesh network according to traffic priority, s is the source node,

Is the set of nodes selected as paths for class n traffic by the path selection algorithm,

Is a set of neighboring nodes of node i (a set of nodes connected by one hop),

Denotes the routing cost from node s to node i of class n traffic, i.e., the distribution of jitter information that can be obtained from equations (9) and (10).

Below is an explanation of each part of the pseudo code.

는 (One)

The

집합에 속한 모든 트래픽 클래스에 대해 소스 노드 s로부터 목적지 노드 i에 이르는 경로

를 저장하면서 수행된다. Initialization시 라우팅 알고리즘은 소스 노드 s에 대한 정보만을 가지고 있으므로

이다. 알고리즘의 시작 시 소스 노드 s에 대한 지터 정보의 분산 값

는 0이며 다른 모든 노드에 대해서는 무한대의 값을 가진다. 즉 임의의 노드 i에 대해서는 지터 정보의 분산 값은

로 표현된다. According to the routing setting method of the present invention, a network supported by a node to transmit traffic is provided.

Path from source node s to destination node i for all traffic classes in the aggregate

Is done while saving it. During initialization, the routing algorithm only contains information about the source node s.

to be. Variance value of jitter information for source node s at the start of the algorithm

Is 0 and has infinite value for all other nodes. That is, for any node i, the variance of jitter information is

Lt; / RTI >

(2)

및 지터의 확률 질량 함수는 트래픽 클래스 n에 대한 변수로 각 트래픽 클래스마다 서로 다른 분산값을 가지므로 각 트래픽 클래스마다 지터 최적화된 경로는 서로 다를 수 있다. 일례로 non-preemptive한 우선순위를 갖는 높은 클래스의 트래픽인 경우 다른 트래픽을 고려하지 않고 네트워크 환경이 가장 좋으며 적은 홉으로 전송되는 경로를 선택할 수 있다. 그러나 우선 순위가 낮은 트래픽의 경우 환경이 좋은 경로는 높은 클래스의 트래픽이 선점하여 오히려 지터가 크게 증가할 수 있으므로 상대적으로 적은 트래픽을 수용하는 우회 경로를 택하는 경우 등이 있다. 따라서, 알고리즘은 네트워크가 지원하는 모든 트래픽 클래스 즉,

집합에 속한 모든 트래픽 클래스에 대한 경로 설정을 수행한다.Jitter distribution on node i

Since the probability mass function of and jitter is a variable for traffic class n, each traffic class has a different variance value, so the jitter optimized path may be different for each traffic class. For example, in the case of high class traffic with non-preemptive priority, the network environment is best without considering other traffic, and the route transmitted with fewer hops can be selected. However, for low-priority traffic, a good environment may be a high-class traffic preempt, which may result in a significant increase in jitter. Thus, the algorithm is responsible for all traffic classes supported by the network,

Perform routing for all traffic classes in the set.

(3)

및 해당 경로에 대한 지터 정보의 분산

를 라우팅 테이블에 저장하며 동작하게 된다. 네트워크 프로토콜에 따라 네트워크 내 노드들이 라우팅 테이블 형성을 위해 이웃 정보를 요청하는 등, 경로 탐색을 수행하는 동안 알고리즘이 진행되며 네트워크 내 임의의 노드 i 에 대한 링크비용

및 경로 정보

를 저장해 나가며 네트워크 내 모든 노드

,

에 대한 경로 설정이 완료되면 알고리즘이 종료된다.Path from source node s to node i by the algorithm of the present invention

And distribution of jitter information for that path

Will be stored in the routing table. According to the network protocol, the algorithm proceeds during route discovery, such as nodes in the network requesting neighbor information to form a routing table, and link costs for any node i in the network.

And route information

All nodes in the network

,

The algorithm terminates when the path setting for is completed.

(4)

를 만족하는 노드 i, j의 쌍(pair) 중 지터 분산을 최소로 하는 노드 i, j의 쌍(pair)을 라우팅 테이블에 기록한다. 즉,

를 최소화하는 연결된 두 노드의 쌍 정보를 라우팅 테이블에 기록한다. 두 노드 i, j의 정보를 아래 알고리즘(5)~(7) 단계에 기록하기 위해 두 노드를 x, y라 명명하고 라우팅 정보 및 링크비용 정보를 저장한다.Algorithm (4) is performed by receiving jitter information from all nodes in the network according to algorithms (2) and (3), and each time each information is updated, each node has the routing information for all nodes i stored in the routing table. One-hop neighbor node j that is not recorded, i.e.

The pairs of nodes i and j that minimize jitter distribution among the pairs of nodes i and j satisfying are recorded in the routing table. In other words,

Record pair information of two connected nodes to minimize the number in routing table. In order to record the information of the two nodes i and j in the following algorithms (5) to (7), the two nodes are named as x and y, and routing information and link cost information are stored.

(5)

집합에 와 같이 y가 추가된다.Algorithm (5) adds the information of node y selected as the jitter optimal path among the 1-hop neighbor nodes that do not have the current routing information to the routing table for nodes x and y stored in the algorithm (4). to be. therefore,

On the set Y is added as

(6)

, 지터 분산)과 추가되는 노드 y의 지터 분산

을 합하여 구할 수 있다.Since the information of y was added to the routing table in the process of algorithm (5) for the nodes x and y stored in the process of algorithm (4), the link cost from source node s to node y, that is, the end-to-end jitter distribution, was recorded in the table. do. Since the variance of the sum of the independent random variables is equal to the sum of the variance of each random variable, the link cost is the link cost up to node x (

, Jitter dispersion) and jitter dispersion of node y added

It can be found by adding up.

(7)

에 노드 y를 추가하여 노드 s로부터 노드 y까지의 지터 최적 경로를 완성해 나간다. 이때

는 노드 y의 경로가 기존 라우팅 경로

의 맨 뒤에 추가됨을 의미한다. 즉, s를 시작으로

와 같이 경로가 연결됨을 나타낸다.The path of node y stored in the process of algorithms (4) to (6) is added to the routing table. That is, the routing path from source node s to node x

Add node y to complete the jitter optimal path from node s to node y. At this time

Is the path of node y

Added to the end of the. That is, starting with s

This indicates that the path is connected.

Hereinafter, the jitter performance of the network is verified by using the routing metric and the route setting method of the present invention in the OLSR protocol. For performance analysis of the routing configuration method proposed by the present invention and the routing configuration method used in the existing OLSR protocol, ETX and MH, which are representative OLSR-based routing configuration methods, are compared with the network structure of FIG.

The network structure used for performance analysis was analyzed based on the 40 node network of FIG. 7 of 15 node network, 30 node network and 40 node network, which are the main network structures used in performance evaluation such as broadcast scheduling method. 8 and 9 illustrate simulation results of jitter performance according to an exemplary embodiment of the present invention.

은 30 패킷, 5개의 트래픽 클래스가 각각 20%의 네트워크 용량(capacity)를 차지하며, 무선 메쉬 네트워크의 40 노드가 각 4 노드씩 랜덤하게 0.01, 0.02,

, 0.10 의 패킷의 재전송 확률

를 갖는 경우에 대해 10,000번의 실험을 수행하여 MH 및 ETX 라우팅 설정 방법과 지터 성능을 비교 분석 하였다.According to an embodiment of the present invention, the transmission period T of the traffic is 30 slots and the service rate of traffic per second in the differential wireless mesh network that follows the structure of FIG. 7 and supports five traffic classes.

30 packets, 5 traffic classes each occupy 20% of network capacity, and 40 nodes of the wireless mesh network are randomly selected by 0.01, 0.02,

0.10 packet retransmission probability

10,000 experiments were performed for the case of the MH and ETX routing setup and jitter performance.

는 probe의 송신 성공율

와 수신 성공율

로부터

와 같이 구할 수 있으며, MH는 모든 링크의 링크 비용이 1로, 종단간 전송 경로가 최소의 홉으로 연결되는 라우팅을 설정하는 방법이다. Link cost from node x to node y in ETX

Is the success rate of the probe

And reception success rate

from

MH is a method of configuring routing in which all link costs are 1 and end-to-end transmission paths are connected with the least hops.

8 is a diagram illustrating a simulation result of a transfer rate of each routing setting method according to jitter bound required by a wireless mesh network according to an embodiment of the present invention.

는 클래스 1의 높은 우선 순위를 갖는 트래픽의 경우 본 발명의 라우팅 설정 방법(Minimum Jitter Probability, 이하 MJP), ETX, MH의 경우가 각각 99%, 98%, 98%로 종단간 2 패킷 이내의 지터 범위를 만족하는 등 큰 차이가 없다. 그러나 클래스 5의 가장 낮은 우선 순위를 갖는 트래픽의 경우 MJP, ETX, MH가 각각 24%, 11%, 11%의 확률로 종단간 2 패킷 이내의 지터 범위를 만족하여 큰 성능 차이를 보인다. 클래스 3의 트래픽을 비교하면 MJP는 99%의 패킷이 종단간 지터 범위가 8 패킷 이내로 전달되었으며, ETX 및 MH의 경우 종단간 지터의 범위가 12 패킷으로 매우 큰 범위 값인 경우 비로소 99%의 패킷 전달율을 달성하는 등 확연한 지터 성능 차이를 보인다.Referring to Figure 8, the probability that a packet is transmitted with end-to-end jitter less than the required jitter range.

In case of traffic having a high priority of class 1, the jitter probability (MJP), 99%, 98%, and 98% of ETX and MH are jitter within 2 packets from end to end, respectively. There is no big difference such as satisfying the range. However, for the traffic with the lowest priority of class 5, MJP, ETX, and MH have 24%, 11%, and 11% probability of satisfying the jitter range within 2 packets from end to end, respectively. Comparing class 3 traffic, MJP says 99% of packets are delivered within 8 packets of end-to-end jitter range, and only 99% of packets are delivered when the end-to-end jitter range is 12 packets for ETX and MH. To achieve a significant jitter performance difference.

FIG. 9 is a diagram illustrating a simulation result of an average and variance of end-to-end jitter of each routing setting method in a wireless mesh network environment according to an embodiment of the present invention.

)가 0.2, 0.3,

, 1 인 경우마다 10,000번씩 시뮬레이션을 수행한 결과이다. 도 9에는 MJP, MH, ETX의 클래스 2, 3, 4 트래픽에 대한 종단간 지터의 평균 및 분산이 기록되어 있어, 그래프의 각 선분이 가리키는 지점으로부터 평균 지터를 확인할 수 있으며 그래프 위/아래에 기록된 숫자로부터 각 라우팅 설정 방법에 대한 분산을 알 수 있다. MH 와 ETX는 비슷한 지터 성능을 보이므로 선분이 거의 겹쳐있으며, 각 선분의 위에 표시된 숫자는 ETX에의한 종단간 지터의 분산, 각 선분의 아래에 표시된 숫자는 MH에 의한 종단간 지터의 분산을 나타낸다. 네트워크의 유틸리티가 1일 때, 클래스 2 트래픽의 평균 지터는 MJP, MH, ETX가 각각 1.1, 1.6, 1.6 패킷으로 평균 지터의 큰 차이는 없으나 MJP가 가장 좋은 성능을 보인다. 네트워크의 유틸리티가 1일 때, 클래스 4 트래픽의 평균 지터는 MJP, MH, ETX가 각각 4.0, 6.0, 6.0으로 MJP 알고리즘을 사용하면 우선순위가 높은 트래픽은 물론 우선순위가 낮은 트래픽도 종단간 지터를 보장할 수 있으며, 우선순위가 낮은 트래픽일수록 지터 QoS 차이가 극명하게 나타남을 알 수 있다.9, a network utility (

) Is 0.2, 0.3,

, 1 is the result of simulation 10,000 times. In Figure 9, the mean and variance of end-to-end jitter for class 2, 3, and 4 traffic of MJP, MH, and ETX are recorded so that the average jitter can be seen from the point indicated by each segment of the graph and recorded above / below the graph. The distribution of each routing setup method can be seen from the numbers. Since MH and ETX show similar jitter performance, the line segments are almost overlapping, with the numbers above each line representing the distribution of end-to-end jitter by ETX, and the numbers below each line representing the distribution of end-to-end jitter by MH. . When the utility of the network is 1, the average jitter of class 2 traffic is 1.1, 1.6, and 1.6 packets of MJP, MH, and ETX, respectively. There is no significant difference in average jitter, but MJP shows the best performance. When the network's utility is 1, the average jitter for class 4 traffic is MJP, MH, and ETX 4.0, 6.0, and 6.0, respectively. Using the MJP algorithm, low-priority traffic as well as high-priority traffic can be found. It can be assured that the lower priority traffic is more noticeable in jitter QoS differences.

Therefore, when the routing configuration method minimizes the variance of the probabilistic analysis of jitter of the present invention, it is possible to expect better jitter performance (smaller end-to-end jitter average and dispersion) than the MH and ETX based routing configuration methods. Within the jitter range, the packet transfer rate is superior to that of MH and EXT based routing methods.

Conventional jitter performance-based routing configuration method has a disadvantage in that it is difficult to guarantee QoS of real-time transmission traffic (VoIP, video transmission, etc.) in a wireless mesh network in that it does not consider jitter characteristics based on traffic priority, arrival rate, and service rate. In the present invention, in consideration of the jitter characteristic of the packet, it is effective to ensure the quality of the jitter performance which is most important in OoS of real-time data transmission.

In addition, embodiments of the present invention may be implemented in the form of program instructions that can be executed through various computer means and recorded on a computer readable medium. The computer readable medium may include program instructions, data files, data structures, etc. alone or in combination. The program instructions recorded on the medium may be those specially designed and constructed for the present invention or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Examples of program instructions, such as magneto-optical and ROM, RAM, flash memory and the like, can be executed by a computer using an interpreter or the like, as well as machine code, Includes a high-level language code. The hardware devices described above may be configured to operate as at least one software module to perform operations of one embodiment of the present invention, and vice versa.

As described above, the present invention has been described by specific embodiments such as specific components and the like. For those skilled in the art, various modifications and variations are possible from these descriptions. Accordingly, the spirit of the present invention should not be construed as being limited to the embodiments described, and all of the equivalents or equivalents of the claims, as well as the following claims, belong to the scope of the present invention .

100: wireless mesh network 101 to 110: mesh router
200: node 201: jitter information calculation unit
203: communication unit 301: J field
400: routing setting device 401: jitter information acquisition unit
403: routing setting unit 411: jitter dispersion calculator
413: path selector

Claims (16)

In the routing setting method in a wireless mesh network,
Acquiring jitter information of each node included in each of the multiple paths from the source node to the destination node; And
And (b) establishing a routing from the source node to the destination node using the jitter information of the nodes. The method of claim 1,
Wherein each node calculates the jitter information differently according to the priority of traffic entering the nodes. The method of claim 2,
And the jitter information in each of the nodes is calculated using at least one of the priority of the traffic, the period of the traffic, the arrival rate of the traffic, and the service rate of the traffic. The method of claim 3,
The period of the traffic is calculated using the transmission period of the traffic and the retransmission probability of the packet included in the traffic. The method of claim 1,
The step (b)
(B-1) calculating end-to-end jitter variance of each of the multipaths using jitter information of each node included in each of the multipaths; And
(B-2) selecting one of the multipaths with the least end-to-end jitter distribution. The method of claim 5,
The end-to-end jitter distribution of any one of the multipaths is calculated using at least one of the sum of the variance of the jitter information of each node included in the one path and the sum of the covariances. . The method of claim 5,
The step (a) obtains multiple paths for all nodes between the source node and the destination node in the wireless mesh network, and collects jitter information of the nodes accumulated through the nodes included in each of the multiple paths. Earned,
The step (b-1) is to calculate the end-to-end jitter distribution of each of the multi-path using the accumulated jitter information of the nodes. The method of claim 7, wherein
And wherein step (a) obtains jitter information of each of the nodes that are flooded from each of the nodes. 9. The method of claim 8,
Wherein each node floods a hello message of an optimized link state routing (OLSR) protocol including the jitter information to neighboring nodes of the nodes. In the routing path setting apparatus in a wireless mesh network,
A jitter information acquisition unit for acquiring jitter information of nodes included in each of multiple paths from a source node to a destination node; And
And a routing setting unit configured to set routing from the source node to the destination node by using the obtained jitter information of the nodes. The method of claim 10,
And each of the nodes calculates the jitter information differently according to the priority of traffic entering the nodes. 12. The method of claim 11,
The jitter information is calculated using at least one of the priority of the traffic, the period of the traffic, the arrival rate of the traffic, and the service rate of the traffic. The method of claim 10,
The routing setting unit,
A jitter variance calculator for calculating end-to-end jitter variance of each of the multipaths using jitter information of each node included in each of the multipaths; And
And a path selector for selecting a path having a minimum end-to-end jitter distribution among the multipaths. The method of claim 13,
The end-to-end jitter distribution of any one of the multipaths is calculated using at least one of the sum of the variance of the jitter information of each node included in the one path and the sum of the covariances. . A node included in a wireless mesh network,
A jitter information calculator configured to calculate jitter information of the node using at least one of a priority of traffic entering the node, a period of the traffic, an arrival rate of the traffic, and a service rate of the traffic; And
And a communication unit for flooding the jitter information to a neighbor node of the node. 16. The method of claim 15,
And the communication unit floods a hello message of an optimized link state routing (OLSR) protocol including the jitter information to the neighboring node.

Images