KR101975104B1 - A method and apparatus for network formation in dynamic networks - Google Patents

Abstract

The present invention can change the network according to the dynamic network environment by adjusting the transmission range by changing the transmission power according to the policy by the nodes constituting the network. At this time, the initial state can be determined such that the number of nodes of the changed network converges on a fixed network that does not change.
According to an embodiment of the present invention, there is provided a network forming method performed by a network forming apparatus that connects a source node and an end node via a plurality of intermediate nodes, the method comprising: generating a state space satisfying a Markov property, Determining a state transfer probability, a utility function, and a discount factor; Determining a policy of the agent to determine whether a transmission range of an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes changes; And forming an initial state of the network by using an extreme probability distribution based on the determined policy.

Description

[0001] METHOD AND APPARATUS FOR NETWORK FORMATION IN DYNAMIC NETWORKS [0002]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for forming a network in a dynamic network, and a network forming method and apparatus for determining a transmission range in an intermediate node according to a policy.

In the latest network application technologies such as autonomous vehicles, UAV (unmanned aerial vehicle) and Internet of things, the members of network have high mobility, and the change of network configuration member is frequent. Such a dynamic network has a problem that a channel state inside the network becomes unstable, resulting in a high link failure rate.

Therefore, even in such a dynamic network environment, it is necessary for the network members to appropriately evolve the network topology and to form a robust network by determining and changing the connection among the members depending on the environment of the network.

The present invention provides a network forming apparatus and method for changing a transmission range by changing a transmission power according to a policy by a node constituting the network itself.

The present invention provides a network forming apparatus and method, in which nodes constituting a network change their transmission ranges and change their networks according to dynamic network changes.

The present invention provides a network forming apparatus and method in which even in a dynamic network environment, convergence is made to a fixed network in which the number of nodes included in the network is constant.

The present invention provides a network forming apparatus and method for determining an initial state of a network to converge to a fixed network more quickly.

According to an embodiment of the present invention, there is provided a network forming method performed by a network forming apparatus that connects a source node and an end node via a plurality of intermediate nodes, the method comprising: generating a state space satisfying a Markov property, Determining a state transfer probability, a utility function, and a discount factor; Determining a policy of the agent to determine whether a transmission range of an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes changes; Based on the determined policy, forming an initial state of the network by using a limiting distribution.

Wherein the state space represents a set of states indicating the number of valid nodes that have received the data from an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes, Wherein the state transition probability represents a probability of transition from a current state to a next state by the action, and the utility function is operable to move from the current state to the next state The network throughput improvement and the transmit power consumed, and the discount factor may be a network formation method that indicates the degree of utility reduction over time.

The policy may be a first policy that optimizes a state-value function, which is a cumulative utility function at a particular time, or a first policy that optimizes a state-value function that is a cumulative utility function at a particular time, 2 < / RTI > policy.

The intermediate node may be a network formation method of encoding data received from the source node or another intermediate node in a Galois field.

Wherein the action increases the transmission range if the action is greater than 0 or decreases the transmission range if the action is less than 0 or does not change the transmission range if the action is 0 Network formation method.

The discount factor may be a network formation method that is determined based on the consistency of the channel environment of the dynamic network.

The initial state indicates a state having a maximum probability distribution of probability when a policy includes an action of 0, or a state corresponding to a case in which the eigenvalue is equal to 1 when the policy does not include an action of 0 Lt; RTI ID = 0.0 > a < / RTI > row eigenvector of the matrix.

The utility function may be a network formation method that uses weights to balance the compensation of the network throughput and the cost of the transmitted power consumed.

According to an embodiment of the present invention, there is provided a network forming method performed by a network forming apparatus that connects a source node and an end node via a plurality of intermediate nodes, the network forming method comprising: Identifying a number of valid nodes that receive data from the agent included in the validated node; Determining an action using a policy that forms the initial state; And updating the transmission range of the data according to the determined action.

According to an embodiment of the present invention, there is provided a network forming apparatus, wherein the network forming apparatus includes a processor, the processor connects a source node and an end node via a plurality of intermediate nodes, The policy of the agent that determines whether the transmission range of the agent, which is the intermediate node that transmits data among the plurality of intermediate nodes, is changed, is determined by determining the state space, action space, state transfer probability, utility function, And may be a network forming apparatus that forms an initial state of the network by using an extreme probability distribution based on the determined policy.

According to an embodiment of the present invention, there is provided a network forming apparatus, wherein the network forming apparatus includes a processor, and when the source node and the end node are connected through a plurality of intermediate nodes, Determining a number of valid nodes that receive data from the agent included in an initial state of the network formed based on the policy, determining an action using the policy forming the initial state, and determining, based on the determined action, Lt; RTI ID = 0.0 > a < / RTI >

According to an embodiment of the present invention, it is possible to provide a network forming apparatus and method for changing a transmission range by changing the transmission power according to a policy of a node constituting the network itself.

According to an embodiment of the present invention, it is possible to provide a network forming apparatus and method for changing a network by changing the transmission range of the nodes constituting the network according to a dynamic network change.

According to an embodiment of the present invention, it is possible to provide a network forming apparatus and method in which even in a dynamic network environment, the number of nodes included in a network is converged to a fixed network.

According to an embodiment of the present invention, a network forming apparatus and method for determining an initial state of a network to converge to a fixed network more quickly can be provided.

1 is a diagram showing a source node, an intermediate node, and an end node constituting a network according to an embodiment of the present invention.
2 is a diagram illustrating a method of initializing a network according to an embodiment of the present invention.
3 is a diagram illustrating a method of changing a network, in accordance with an embodiment of the present invention.
4 is a diagram illustrating a change in transmission range according to an action according to an embodiment of the present invention.
5 is a diagram illustrating an algorithm 1 for determining a policy according to an embodiment of the present invention.
6 is a diagram illustrating an algorithm 2 for changing a network with the transmission of a packet, according to an embodiment of the present invention.
7 is a diagram illustrating a simulation illustrating the number of nodes according to network size, in accordance with an embodiment of the present invention.
8 is a diagram illustrating a simulation according to a second policy according to an embodiment of the present invention.
9 is a diagram illustrating simulation of a convergence rate according to a second policy according to a discount factor, in accordance with an embodiment of the present invention.
10 is a diagram illustrating a simulation according to a weight w in a network connection, according to an embodiment of the present invention.
11 is a diagram illustrating a network connection according to a link failure rate according to an embodiment of the present invention.

Specific structural or functional descriptions of embodiments are set forth for illustration purposes only and may be embodied with various changes and modifications. Accordingly, the embodiments are not intended to be limited to the particular forms disclosed, and the scope of the present disclosure includes changes, equivalents, or alternatives included in the technical idea.

The terms first or second, etc. may be used to describe various elements, but such terms should be interpreted solely for the purpose of distinguishing one element from another. For example, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component.

It is to be understood that when an element is referred to as being "connected" to another element, it may be directly connected or connected to the other element, although other elements may be present in between. The singular expressions include plural expressions unless the context clearly dictates otherwise. In this specification, the terms " comprises ", or " having ", and the like, are used to specify one or more of the described features, numbers, steps, operations, elements, But do not preclude the presence or addition of steps, operations, elements, parts, or combinations thereof.

Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art. Terms such as those defined in commonly used dictionaries are to be interpreted as having a meaning consistent with the meaning of the context in the relevant art and, unless explicitly defined herein, are to be interpreted as ideal or overly formal Do not.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a diagram showing a source node, an intermediate node, and an end node constituting a network according to an embodiment of the present invention.

The network may include a source node 110, an intermediate node 120, and a terminal node 130. Each source node 110 may be coupled to an independent set of end nodes 130. For example, the source node 110 may multicast data to a plurality of end nodes 130. The source node 110 may transmit data and the end node 130 may receive data.

If data is directly transmitted from the source node 110 to the terminating node 130, the intermediate node 120 may not be used. The intermediate node 120 receives data from the source node 110 and sends the data to the terminating node 130 when the data is not directly transmitted from the source node 110 to the terminating node 130 relay function.

, 종단 노드(130)의 수를

, 중간 노드(120)의 수를

라고 한다면, 네트워크에 있는 총 노드의 수는

를 나타낼 수 있다.The number of source nodes < RTI ID = 0.0 > 110 &

, The number of end nodes 130

, The number of intermediate nodes 120

, The total number of nodes in the network is

Lt; / RTI >

The intermediate node 120 may have mobility and the intermediate node 120 may be a wired / wireless device. The intermediate node 120 may also adjust the transmission power to determine the transmission range at which the data can be transmitted.

는 특정한 시간(

)에서 중간 노드(

)의 전송 범위의 반지름(radius)를 나타내며,

는 특정한 시간(

)에서 중간 노드(

)에서 다른 중간 노드

로의 유클리디안 거리(Euclidean distance)를 나타낸다. 만약 중간 노드

의 전송 범위에

가 있다면,

는

로부터 데이터를 수신할 수 있다. 여기서, 유클리디안 거리는 노드 사이의 직선거리를 나타낼 수 있으며, 최단거리는 직선거리에 포함될 수 있다. 일례로, 중간 노드(

)에서 다른 중간 노드(

)로의 유클리디안 거리는 직선거리를 나타낼 수 있으며, 또한 최단거리를 나타낼 수 있다.For example,

Is a specific time

) To the intermediate node (

Represents the radius of the transmission range of the transmission range,

Is a specific time

) To the intermediate node (

) To another intermediate node

And the Euclidean distance to the Euclidean distance. If the intermediate node

In the transmission range of

If so,

The

Lt; / RTI > Here, the Euclidean distance may represent a straight line distance between nodes, and the shortest distance may be included in a straight line distance. For example, an intermediate node

) To another intermediate node (

) Can indicate a straight line distance, and can also indicate a shortest distance.

라고 한다면, 중간 노드(

)가 다른 중간 노드(

)로부터 링크의 연결에 성공할 확률은

일 수 있다. The link between the source node, the intermediate node, and the terminating node may be connected, or the connection may fail. For example, the probability that a link between intermediate nodes will fail

, The intermediate node (

) To another intermediate node (

The probability of successful linking of links from

Lt; / RTI >

The connection between intermediate nodes can form a network. For example, a multi-hop ad hoc network may be formed through the connection of intermediate nodes. The transmission of data from the source node to the end node can be determined by the path by the intermediate node selected among the plurality of intermediate nodes, the throughput / speed of the data transmission, and the like.

)는 중간 노드

에서 평가한 다른 중간 노드

의 가치를 나타낼 수 있다. 이때, 노드 가치 함수는 다음의 수학식 1과 같을 수 있다.The node value represents a value obtained by quantifying how the other intermediate nodes contribute to the data transfer. The node value function (

) Is an intermediate node

Other intermediate nodes evaluated by

Can be expressed. At this time, the node value function can be expressed by Equation 1 below.

에서

는 중간 노드(

)와

의 종단 노드(

) 간의 홉(hop)의 수를 나타낼 수 있다. At this time,

in

Is an intermediate node (

)Wow

The end node (

The number of hops between the first and second frames.

)로부터 종단 노드(

)까지 홉(hop)의 수와

와 중간노드(

) 사이의 거리가 감소하는 것으로 노드 가치를 정의함으로써,

는 전송 에너지 소모를 최소화 할 수 있는 가까운 중간 노드(

)에 연결하고, 동시에 중간 노드(

)가 적은 홉수로 종단 노드(

,

)와 연결됨으로써 노드 가치 함수(

)는 증가할 수 있다. 그러므로, 적절한 중간 노드(

)를 선택하는 것에 의해서, 중간 노드(

)는 더 적은 전송 전력을 소비하고 데이터 전송의 딜레이(delay)를 줄일 수 있다.Intermediate node (

) To the end node (

The number of hops up to

And intermediate nodes (

By defining the node value by decreasing the distance between nodes,

Lt; RTI ID = 0.0 > (e. G., ≪ / RTI &

), And at the same time,

) To the end node (

,

) And the node value function (

) Can be increased. Therefore, a suitable intermediate node (

), The intermediate node (

) Can consume less transmit power and reduce the delay of data transmission.

a) Network Coding Based Encoding Process

)는 데이터(

)를 특정한 시간(

)에서 생성할 수 있다`. 그리고 소스 노드는 생성된 데이터를 전송 전력(

)으로 전송할 수 있고, 이때 함수 g는 유/무선 채널의 경로 손실 모델(path loss model)에 기반하여 결정될 수 있다. 소스 노드에서 전송 범위의 반지름(

)은 시간과 관계없는 독립적인 값이다.Source node (

) Is the data (

) To a specific time (

). The source node then transmits the generated data to the transmit power (

), Where the function g may be determined based on the path loss model of the wired / wireless channel. The radius of the transmission range at the source node (

) Is an independent value independent of time.

)에서 중간 노드(

)가 소스 노드(

)의 전송 범위에 위치하고 있다면, 중간 노드(

)는 데이터(

)를 소스 노드로부터 수신하고 버퍼(

)에 데이터를 저장할 수 있다. 데이터는 타임 스탬프(time stamp)에 따라 구별되어 저장될 수 있다. 예를 들면, 저장된 후, 오랜 시간이 지난 데이터는 버퍼의 앞쪽에 위치할 수 있다. At a specific time (

) To the intermediate node (

) Is the source node (

), The intermediate node (

) Is the data (

) From the source node and sends the buffer

). ≪ / RTI > The data can be stored separately according to a time stamp. For example, after being stored, data over a long period of time may be located in front of the buffer.

Packets have a limited life span (e.g., time to live (TTL)), and packets with expired lifetimes can be discarded.

)는 버퍼(

)에 저장된 같은 타임 스탬프(time stamp)를 가진 패킷을 조합함으로써 네트워크 코딩을 수행할 수 있고, 그 결과 인코딩된 인코딩 데이터(

)를 미래 시간(

)에서 생성할 수 있다. 여기서, 인코딩 데이터(

)는 다음의 수학식 2로 표현될 수 있다 Intermediate node (

) Is a buffer (

), And can thus perform network coding, and as a result, the encoded encoded data (< RTI ID = 0.0 >

) To the future time (

). ≪ / RTI > Here, the encoded data (

) Can be expressed by the following equation (2)

는 중간 노드(

)의 글로벌 코딩 계수(global coding codfficient)를 나타낸다. 네트워크 코딩은 갈로이스 필드(GF)영역에서 수행될 수 있고, 연산자

및

는 갈로이스 필드영역에서 각각 덧셈과 곱셈을 나타낼 수 있다. 다만, 네트워크 코딩은 갈로이스 필드영역에서만 수행되는 것은 아니며, 본 발명은 다른 영역에서 네트워크 코딩이 수행되는 것도 포함할 수 있다.

Is an intermediate node (

) ≪ / RTI > Network coding may be performed in the Golay field (GF) area,

And

Can represent addition and multiplication, respectively, in the Galois Field field. However, the network coding is not performed only in the Galois field area, and the present invention may include the network coding performed in another area.

)은 다음의 수학식 3과 같이 형성 될 수 있다. 여기서, 패킷(

)은 조합된 데이터의 타임 스탬프(

)를 가지며, 글로벌 코딩 계수(

)는 헤더(header)에 위치하며, 인코딩 데이터(

)는 페이로드(payload)에 위치할 수 있다.When coding is performed, data with the same time stamp is combined, and the packet (

Can be formed as shown in the following Equation (3). Here, the packet (

) Is the time stamp of the combined data (

), And a global coding coefficient (

) Is located in the header, and the encoded data (

) May be located in a payload.

)가 특정한 시간(

)에 인코딩된 인코딩 데이터(

)를 수신한 경우, 중간 노드(

)는 수신한 데이터를 재조합하고 특정한 시간(

)에 인코딩된 인코딩 데이터(

)를 다음의 수학식 4를 따라 생성할 수 있다. If the intermediate node (

) At a certain time (

) Encoded data (

), The intermediate node (

) Recombine the received data and transmit it at a specific time (

) Encoded data (

) Can be generated according to the following equation (4).

)는 중간 노드(

)에서 일시적으로 사용하는 코딩 계수이다. 여기서, 로컬 코딩 계수와 종래의 글로벌 코딩 계수를 연산함으로써 글로벌 코딩 계수를 업데이트 할 수 있다. 하기 기술할 패킷은 로컬 코딩 계수가 아닌 글로벌 코딩 계수를 포함할 수 있다.Here, the local coding coefficient,

) Is an intermediate node (

) Is a temporary coding coefficient. Here, the global coding coefficient can be updated by calculating the local coding coefficient and the conventional global coding coefficient. Packets to be described below may include global coding coefficients rather than local coding coefficients.

)는 크기가

인 갈로이스 필드영역으로부터 균일하고(uniformly) 임의적으로(randomly) 선택될 수 있다.(즉,

) 네트워크 코딩은 RLNC에 의한 코딩에 한정되지 않고, NC-SVD(Network Coding Singular Value Decomposition) 또는 NC-EGD(Network Coding Eigen Decomposition) 또는 NC-UHM(Network Coding Unitary Hessenberg Matrix)와 같은 다른 네트워크 코딩 방법에 의해서도 수행될 수 있다. In the present invention, network coding can be performed based on RLNC (Random Linear Network Coding). So the local coding coefficients (

) Is the size

Uniformly and arbitrarily selected from the galois field field (i.e.,

) Network coding is not limited to coding by RLNC but may be applied to other network coding methods such as NC-SVD (Network Coding Singular Value Decomposition) or NC-EGD (Network Coding Eigen Decomposition) or NC-UHM (Network Coding Unitary Hessenberg Matrix) As shown in FIG.

b) Source Reconstruction at Terminal Nodes

)의 벡터 및 글로벌 코딩 계수 행렬(global coding codfficient matrix)은 다음의 수학식 5와 같이 표현될 수 있다.The end node can decode the received data. Network coded data (

) And a global coding coefficient matrix can be expressed by the following Equation (5).

2 is a diagram illustrating a method of initializing a network according to an embodiment of the present invention.

In step 301, the network forming device may determine a state space, an action space, a state transition probability, a utility function, and a discount factor satisfying the Markov property.

)을 나타낸다. The state (s, s) represents the expected number of effective nodes in the transmission range of the agent, which is the intermediate node that transmits data. A state space (S) is a set of states

).

개수 일 수 있으며, 채널의 링크 실패율(link failure rate,

)을 고려할 경우

개수 일 수 있다. 여기서, 네트워크 형성 장치가 데이터를 수신한 유효 노드의 수를 알 수 있는 경우와 달리, 알 수 없는 경우 에이전트의 전송 범위 내에 있는 노드(node)의 개수와 링크 실패율을 이용하여 기대값(expectation value)을 통해 유효 노드의 수는 계산될 수 있다. Here,

And the link failure rate of the channel,

) Is considered

Lt; / RTI > Unlike the case where the network forming apparatus can know the number of valid nodes receiving the data, if the number of valid nodes is unknown, the expectation value is calculated using the number of nodes in the agent's transmission range and the link failure rate, The number of valid nodes can be calculated.

)에서 상태(s)는 노드(node)의 이동성(mobility)과 채널의 링크 실패율로 인해 노드 밀도(

)가 정확한 값이 아닐 수 있기 때문에, 중간 노드의 전송 범위의 반지름(

)에 의해서 직접적으로 결정될 수 없다. 따라서, 네트워크가 상태(s)에 의해 형성될 경우, 동적 네트워크에 따라 중간 노드의 전송 범위의 반지름(

)이 변화하여 네트워크가 형성될 수 있으므로, 강인한(robust) 네트워크를 형성할 수 있고, 자세한 과정은 이하 서술한다. 이하, 강인한 네트워크는 각각의 노드가 정책에 따라 전송 범위를 결정하고, 네트워크의 환경의 동적변화에 따라, 네트워크를 지속적으로 변화/진화시켜 네트워크의 데이터 전송 성공률 및 데이터 전송량을 유지 및 향상 시킬수 있다. If it is a dynamic network,

) State (s) is the node density due to the mobility of the node and the link failure rate of the channel

) May not be accurate, the radius of the transmission range of the intermediate node (

). ≪ / RTI > Therefore, when the network is formed by state s, the radius of the transmission range of the intermediate node according to the dynamic network (

Can be changed to form a network, so that a robust network can be formed, and a detailed procedure will be described below. Hereinafter, a robust network determines the transmission range according to a policy, and each node continuously changes / evolves the network according to the dynamic change of the environment of the network, thereby maintaining and improving the data transmission rate and data transmission rate of the network.

)의 전송 범위

, 현재 시간(

)의 전송 범위

라고 할 때, 현재 시간(t)에서의 액션(a)는

로 표현될 수 있다. 즉, 액션은 이전 시간과 비교한 현재 시간의 전송 범위의 변화 여부를 결정할 수 있다. 이때, 전송 범위는 에이전트로부터의 거리, 반지름, 면적등 다양하게 표현될 수 있다. The action (action, a) represents the change of the transmission range compared with the transmission range of the agent's previous time. Previous time (

) Transmission range

, current time(

) Transmission range

, The action (a) at the current time (t) is

. ≪ / RTI > That is, the action can determine whether the transmission range of the current time compared to the previous time has changed. At this time, the transmission range can be expressed in various ways such as the distance from the agent, the radius, and the area.

In this case, if a> 0, the transmission range of the agent is increased at the current time compared to the previous time. If a = 0, the transmission range of the agent does not change at the current time compared to the previous time. And reduces the transmission range of the agent at the current time.

)은 액션(a)인 경우 상태(s)에 있는 노드가 다른 상태(s')로 이전할 확률을 나타낸다. 이때, 상태(s)를 현재 상태, 상태(s')을 다음 상태라 할 수 있다. 네트워크 내 노드 분포 밀도가

인 경우에, 상태 이전 확률은 다음의 수학식 6과 같이 표현될 수 있다. 이때,

는 특정한 시간(

)에서 전송 범위(

)에 포함되는 노드의 수를 나타낸다. State transition probability,

) Represents the probability that a node in state (s) will move to another state (s') in case of action (a). At this time, the state (s) may be the current state, and the state (s') may be the next state. The distribution density of nodes in the network is

, The state transition probability can be expressed by the following Equation (6). At this time,

Is a specific time

) To the transmission range (

The number of nodes included in the network.

개의 노드가 포함되는 확률을 나타내며, 액션(a)가 0보다 작은 경우 전송 범위에

가 포함될 확률을 나타내며, 액션(a)가 0인 경우 전송 범위에 변화가 없어

=

일 수 있다.Equation (6) shows that when the action (a) is larger than 0,

(A) is smaller than 0, it indicates the probability that the node is included in the transmission range

, And if the action (a) is 0, there is no change in the transmission range

=

Lt; / RTI >

Equation (6) can be proved based on the Kolmogorov definition of the conditional probability. The state transition probability of Equation (6) can be expressed by the following Equation (7).

로 표현될 수 있음.)At this time, if the number of valid nodes to which the data is transmitted is known, Equation (7) can be calculated using the number of valid nodes. Alternatively, if the number of valid nodes is not known, the expected value using the number of intermediate nodes located in the transmission range and the link failure rate of the channel can be calculated, and the equation (7) can be calculated

Can be expressed as.

I) If the action is greater than 0, more nodes may be included in the transmission range due to an increase in transmission range, and Equation (7) may be verified by the following procedure.

Ii) In the same way as when the action is larger than 0, the case where the action is smaller than 0 can also be proved, and the same result can be obtained.

를 통해 액션이 0보다 크거나 작은 경우와 동일한 결과를 나타낼 수 있다. Iii) If the action is 0

The same result can be obtained when the action is greater than or less than zero.

)는 네트워크 처리량(network throughput) 의 향상(improvement)과 관련된 보상(reward,

) 및 소비되는 전송 전력에 대한 비용(cost)를 포함한다. 즉, 유틸리티 함수는 다음의 수학식 8와 같이 표현될 수 있다. The utility function (utility function,

) Is a reward related to the improvement of network throughput,

) And the cost for the transmitted power to be consumed. That is, the utility function can be expressed by the following equation (8).

At this time, the weight (weight, w) is a value between 0 and 1 and can be used to maintain a balance between the reward and the cost. For example, if w = 1, the cost for the additional consumed transmit power associated with action (a) is not taken into consideration, only an improvement in network throughput can be considered. Conversely, when w = 0, only the cost for the additional consumed transmission power can be considered without considering the network throughput enhancement associated with the compensation (R (s, s')).

If a > 0 in Equation (8), the cost may increase because more power is consumed to widen the transmission range. Conversely, if a < 0, then - (1-w) * a in equation (8) becomes positive and the value of the utility function can be increased.

)는 0보다 크거나 같도록 설정될 수 있다. The utility function is generally a non-negative value, and the constant u is used for this purpose. Thus, utility functions,

) May be set to be greater than or equal to zero.

는 다음의 수학식 9와 같이 정의될 수 있다. 이때,

는 상태(s)인 경우 네트워크 처리량을 나타내고,

는 상태(s')인 경우 네트워크 처리량을 나타낸다. Functions related to reward

Can be defined as the following equation (9). At this time,

Represents the network throughput in the state s,

Represents the network throughput in the state s'.

)는 0에서 1사이의 값으로, 예측한 미래 유틸리티 함수의 값이 시간에 따라 감소하는 정도를 나타낸다. 따라서, 디스카운트 팩터(

)를 이용하여 미래의 유틸리티 함수의 값을 누적한 장기적인 관점의 현재 상태의 가치를 결정할 수 있다. The discount factor (discount factor,

) Is a value between 0 and 1, indicating the degree to which the value of the predicted future utility function decreases over time. Therefore, the discount factor (

) Can be used to determine the value of the current state in the long term, which accumulates the values of future utility functions.

The discount factor may be determined based on the consistency of the network dynamic environment. For example, if the condition of the network is static, that is, if the network does not change, then the value of the predicted future utility function will increase to a higher value in order to impose a higher weight, use. On the other hand, in the case of a network with low consistency of the dynamic environment, the discount factor may be a small value.

The state space S, the action space A, the state transition probability, the utility function, and the discount factor satisfy the Markov property and can be proved through the following process. The Markov characteristic can be expressed by the following equation when a continuous event occurs, the future event is affected only by the current event regardless of the past event.

는 연속적인 이벤트(sequence of event)로서,

는 특정한 시간(

)에서의 액션(a)와 상태(s)를 포함하는 이벤트를 나타낸다. 초기의 전송 범위는

를 나타내며, 이에 따른 상태는

을 나타낸다.

Is a sequence of events,

Is a specific time

) &Lt; / RTI &gt; in the event (a) and the state (s). The initial transmission range is

And the state corresponding thereto is

.

) 및 상태(

)일 경우, 상태 이전 확률은 새로운 상태

로 상태를 이전 시키며, 이는 다음의 수학식 10과 같이 표현될 수 있다. 이때,

는 상태가

에서

로 이전할 때 추가적으로 포함되는 노드를 나타낼 수 있다.action(

) And status (

), The state transfer probability is the new state

, Which can be expressed by the following equation (10). &Quot; (10) &quot; At this time,

Is in a state

in

Lt; RTI ID = 0.0 &gt; node &lt; / RTI &gt;

는 다음의 수학식 11과 같은 과정을 통해 표현될 수 있다. In the same way,

Can be expressed by the following Equation (11).

는 다음의 수학식 12와 같이 표현될 수 있다.Thus, in a similar manner,

Can be expressed by the following equation (12).

At this time, according to Equation (13), Equation (12) can be expressed as Equation (14).

From Equation (14), the following Equation (15) can be derived, so that the Markov property that the future event is determined only by the current event regardless of the past event can be proved.

In step 202, the network forming apparatus may determine the policy of the agent to determine whether the transmission range of the agent, which is an intermediate node for transmitting data among the plurality of intermediate nodes, is changed.

The nodes of the network can change the transmission range by changing the transmission power, and the degree of change of the transmission range can be determined according to each policy of the nodes of the network. That is, the nodes of each network can change the transmission range setting according to the environment of the network.

The policy of the nodes of the network may be a first policy indicating an optimal policy and a second policy approximating a first policy taking into account the computational complexity. Details of the first policy and the second policy are described in detail below.

In step 203, the network forming apparatus can form an initial state of the network by using the extreme probability distribution based on the determined policy.

A node in the network can change the transmission range according to the policy, and as a result, the network can be stationary. That is, the number of nodes constituting the network may not change. That is, even if it is a dynamic network, if the iteration of changing the transmission range according to the policy is repeated, the network can be fixed.

At this time, according to the set condition of the initial state of the network, the convergence to the fixed network can be processed more quickly. That is, the initial state of the network can be set to converge to a fixed network.

3 is a diagram illustrating a method of changing a network, in accordance with an embodiment of the present invention.

At step 301, the network forming device can determine the number of valid nodes receiving data from the agent included in the initial state of the network. Here, the initial state may be formed based on the policy of the agent which is the intermediate node. The network forming apparatus can confirm the number of valid nodes receiving data from the agent among the intermediate nodes included in the initial state of the formed network so as to converge more quickly.

In step 302, the network forming device may determine an action using a policy that forms an initial state of the distributed nodes. The action can be determined according to the policy of each node. At this time, the policy may mean the first policy, which is the optimal policy, or the second policy, which is approximated to the first policy in consideration of the calculation complexity.

In step 303, the network forming apparatus can update the transmission range of data in each agent according to the determined action. That is, depending on the determined action, it may be determined whether the transmission range of the data in the agent is increased or decreased. The transmission range of the data in each agent can be updated based on the transmission range of the determined data. After the update, it can be repeated from step 301 to step 303 again, and can be converged into a static network through repetition.

4 is a diagram illustrating a change in transmission range according to an action according to an embodiment of the present invention.

a) If the action is greater than 0

)에서 데이터를 전송하는 에이전트의 전송 범위는 미래 시간(

)에서 증가할 수 있다. 예를 들면, 현재 시간(

)에서 에이전트의 전송 범위에 포함된 중간 노드의 수가 5개이며, 이중에서 데이터를 전송 받는 유효 노드의 수는 4개이다 (여기서 에이전트도 유효 노드의 수에 포함된다). 미래 시간(

)에서 에이전트의 전송 범위는 증가하였으며, 그 결과 중간 노드의 수는 10개이며, 이중에서 데이터를 전송 받는 유효 노드의 수는 7개 이다.As can be seen in Figure 4A, the current time (

The transmission range of the agent transmitting data in the future time (

). &Lt; / RTI &gt; For example, the current time (

, The number of intermediate nodes included in the transmission range of the agent is 5, and the number of effective nodes receiving data is 4 (the agent is included in the number of effective nodes). Future Time (

), The range of the agent is increased. As a result, the number of intermediate nodes is 10, and the number of valid nodes receiving data is 7.

b) If the action is 0

)에서 데이터를 전송하는 에이전트의 전송 범위는 미래 시간(

)에서 전송 범위와 동일할 수 있다. 예를 들면, 현재 시간(

)에서 에이전트의 전송 범위에 포함된 중간 노드의 수가 5개이고, 이중에서 데이터를 전송 받는 유효 노드의 수는 4개 이다. 미래 시간(

)에서 에이전트의 전송 범위는 동일하며, 그 결과 중간 노드의 수는 5개이며, 이중에서 데이터를 전송 받는 유효 노드의 수는 4개 이다.As can be seen in Figure 4b, the current time (

The transmission range of the agent transmitting data in the future time (

) May be the same as the transmission range. For example, the current time (

), The number of intermediate nodes included in the transmission range of the agent is five, and the number of effective nodes receiving data is four. Future Time (

), The transmission range of the agent is the same. As a result, the number of intermediate nodes is 5, and the number of effective nodes receiving data is 4.

c) if the action is less than 0

)에서 데이터를 전송하는 에이전트의 전송 범위는 미래 시간(

)에서 감소될 수 있다. 예를 들면, 현재 시간(

)에서 에이전트의 전송 범위에 포함된 중간 노드의 수가 5개이며, 이중에서 데이터를 전송 받는 유효 노드의 수는 4개이다. 미래 시간(

)에서 에이전트의 전송 범위는 감소되었으며, 그 결과 중간 노드의 수는 4개이며, 이중에서 데이터를 전송 받는 유효 노드의 수는 3개 이다.As can be seen in Figure 4c, the current time (

The transmission range of the agent transmitting data in the future time (

). &Lt; / RTI &gt; For example, the current time (

), The number of intermediate nodes included in the transmission range of the agent is five, and the number of effective nodes receiving data is four. Future Time (

), The transmission range of the agent is reduced. As a result, the number of intermediate nodes is 4, and the number of effective nodes receiving data is 3.

5 is a diagram illustrating an algorithm 1 for determining a policy according to an embodiment of the present invention.

가 0으로 설정되는 경우 제1 정책을 결정하는 algorithm 1을 수행할 수 있고,

가 0으로 설정되지 않은 경우 제2 정책을 결정하는 algorithm 1을 수행할 수 있다. In step 502 of FIG. 5

Is set to &quot; 0 &quot;, algorithm 1 can be performed to determine the first policy,

Is set to 0, algorithm 1 can be performed to determine the second policy.

를 만족할 때까지

를 업데이트하며, 단계(503)에서 조건을 만족하는 정책을 결정하고, 단계(504)에서 결정된 정책을 리턴할 수 있다.Briefly, Algorithm 1, step 501 represents initializing the network, step 502

Until

, Determine a policy that satisfies the condition at step 503, and return the policy determined at step 504.

Hereinafter, a method for determining the first policy and the second policy will be described in detail.

a) First policy

의 함수로서,

로 표현될 수 있다. 만약, 상태-가치 함수(state-value function,

)를 최대화 할 수 있다면, 정책은 최적화(optimal)될 수 있다. The change in the transmission range at each node can be determined according to the policy of the node. That is,

Lt; / RTI &gt;

. &Lt; / RTI &gt; If the state-value function,

) Can be maximized, the policy can be optimized.

)는 특정한 시간(

)에서의 상태(s)의 가치를 평가하는 함수로 현재 상태(s)에서 다음 상태(s')로의 변화를 통해 얻어지는 유틸리티 함수의 값과, 미래의 연쇄적인 상태변화로인해 얻어지는 유틸리티 함수의 시간에 따른 디스카운트 팩터를 곱한 누적 유틸리티를 나타내며, 다음의 수학식 16과 같이 표현될 수 있다. Here, the state-value function,

) Is a specific time

(S) from the current state (s) to the next state (s') and the value of the utility function obtained due to future chain state changes , And can be expressed as Equation (16). &Quot; (16) &quot;

)의 곱으로 표현될 수 있다.The expected value of the state-value function can be expressed as: &lt; EMI ID = 17.0 &gt; That is, the expected value is the state-value function and the state transfer probability (

). &Lt; / RTI &gt;

는 모든 정책에서 최대의(maximum) 상태-가치 함수를 의미할 수 있으며, 다음의 수학식 18과 같이 표현될 수 있다. 여기서,

는 모든 상태(every state)에서 정책에 의해 결정되는 액션에 의해 성취되는 최적의 상태-가치 함수를 의미할 수 있다. Optimal state-value functions

May denote the maximum state-value function in all policies and can be expressed as: &lt; EMI ID = 18.0 &gt; here,

Can mean an optimal state-value function that is achieved by an action determined by the policy in every state.

은 최적의 상태-가치 함수

를 유도하는 정책을 나타내며, 다음의 수학식 19와 같이 정의될 수 있다. 또한, 수학식 19는 Bellman 최적 방정식(optimality equation)으로 알려져 있다. Therefore,

The optimal state-value function

And can be defined as the following equation (19). &Quot; (19) &quot; Also, equation (19) is known as the Bellman optimal equation.

에 의해서, 각각의 상태(s)에서 최적의 액션

은 다음의 수학식 20과 같이 결정될 수 있다. 이와 같은 최적의 정책

은 제1 정책이라고 할 수 있다.Given the optimal policy

In each state s,

Can be determined according to the following equation (20). Such an optimal policy

Is the first policy.

로 설정된 경우, 다음의 수학식 21과 같이 algorithm 1은 제2 정책이 아닌 제1 정책으로 수렴할 수 있다. In algorithm 1 of FIG. 5 (502)

The algorithm 1 can converge to the first policy instead of the second policy, as shown in the following equation (21).

)(for all

)

b) the second policy

로서

로 표현될 수 있다. 이때, 근사화된 최적의 정책을 제2 정책이라고 할 수 있다. 제2 정책은 다음의 수학식 22을 통해 표현될 수 있다.In fact, due to the complexity of the computation of the first policy, an approximate optimal policy that can reduce the complexity of computation is becoming popular. The approximate optimal policy is

as

. &Lt; / RTI &gt; At this time, the approximated optimal policy can be called the second policy. The second policy can be expressed by the following equation (22).

)에 의한 상태-가치 함수

와 제1 정책(

)에 의한 상태-가치 함수

의 차이는 최적 레벨(optimality level)

에 의해 제한되어 있다. Second policy (

) State-value function

And the first policy (

) State-value function

The difference between the optimal level (optimality level)

Lt; / RTI &gt;

The second policy may be determined using algorithm 1 of FIG. If the iteration stops according to the following condition (23), then the second policy can be determined by algorithm 1.

)(for all

)

에 의존하게 되므로, 수학식 23과 algorithm 1에서 수렴하는 속도는 디스카운트 팩터

에 의해 조절될 수 있다. Equation 23 and algorithm 1 are the discount factors

, The convergence rate in the equation (23) and the algorithm 1 becomes the discount factor

Lt; / RTI &gt;

Thus, by using the policy, each node can change the transmission range for the dynamic network, resulting in a robust network.

6 is a diagram illustrating an algorithm 2 for changing a network with the transmission of a packet, according to an embodiment of the present invention.

Briefly, Algorithm 2, step 601 determines an initial state such that the number of nodes converges to a fixed network, step 602 causes the node to store the received packets in a buffer when the network is operational , Step 603 forms a network coded packet according to equation (4) if the buffer is not empty, step 604 confirms the current state s, and step 605 moves the action Step 606 changes the transmission range based on the action, and step 607 transmits the network coded packet to a plurality of receivers through a broadcast scheme.

At this time, a method of determining the initial state in step 601 will be described in detail below.

A node in the network can change the transmission range according to the policy, and as a result, the network can be stationary. That is, the number of nodes constituting the network may not change. The initial state of the network can be set so that convergence to the fixed network can be processed more quickly.

일 때, 상태 이전 확률(

)을 나타내며, 상태 이전 확률(P(s, s'))은 현재 상태 s에서 다음 상태 s'으로 이전할 확률을 나타낸다. The (s, s ') component of the state transition matrix P is P (s, s'), which can be expressed by the following equation (24). This means that the best action

, The state transfer probability (

), And the state transition probability P (s, s ') represents the probability of transition from the current state s to the next state s'.

) 및 극한확률분포(limiting distribution,

)에서 극한확률분포의 구성요소(

)은 다음의 수학식 25를 통해 계산될 수 있다. The limiting matrix,

) And limiting distribution,

) Component of the extreme probability distribution (

) Can be calculated by the following equation (25).

는 무한번의 상태 이전(infinite number of state transitions)을 한 이후, 상태 s에 수렴할 확률을 나타낸다. 따라서, 초기 상태(initial state,

)는 다음의 수학식 26과 같이 최대의 극한확률분포의 구성요소(

)을 갖는 상태를 선택함으로써 결정될 수 있다. Here, the components of the extreme probability distribution

Represents the probability of converging to state s after infinite number of state transitions. Therefore, the initial state (initial state,

) Is a component of the maximum likelihood distribution as shown in the following equation (26)

). &Lt; / RTI &gt;

The determined initial state network can be formed with a very high probability similar to a stationary network. In this case, the fixed network may mean a case where the number of nodes of the network has converged to a fixed network where the number of nodes has not changed since the state transfer has occurred several times.

a) If the policy includes action (a) = 0

번째 행은 상태 이전 확률(

)의 정의에 의해서 다음 수학식 27과 같인 표현될 수 있다. When the policy includes action (a) = 0, the transmission range may not be changed. The state transition matrix (P)

The second row is the state transfer probability (

The following equation (27) can be obtained.

는 상태 스페이스(S)에서

를 제외하는 것을 의미할 수 있다. 이때 상태 이전 행렬(P)는 다음의 수학식 28과 같이 표현될 수 있다.

In the state space S

Can be excluded. At this time, the state transition matrix P can be expressed by the following equation (28).

In this case, the matrix component Q of the normal form P is a non-negative matrix composed of non-negative elements, R is a positive matrix composed of positive elements, 0 is a matrix with zeros, I represents an identity matrix. In this case, the size of the unit matrix I may be the number of states whose action (a) is zero. For example, if P is a 4 * 4 matrix, then Q / R / 0 / I can all be a 2 * 2 matrix or Q / I can represent a 1 * 1 matrix 0 / R 3 * 3 matrix , Or may represent P in other ways.

Thus, the limiting matrix can be expressed as: &lt; EMI ID = 29.0 &gt;

되며, F는

로 표현될 수 있다. 이때, 극한확률분포(limiting distribution,

)의 구성요소인

는 다음의 수학식 30과 같이 표현될 수 있다.Here, since Q is a value between 0 and 1

And F is

. &Lt; / RTI &gt; At this time, the limiting distribution,

), Which is a component of

Can be expressed by the following equation (30).

는 행렬 FR의 (i, j)번째 구성요소를 나타내며,

로서 상수를 나타낼 수 있다. 그러므로 초기 상태(

)는 다음의 수학식 31과 같이 결정될 수 있다.here,

Represents the (i, j) -th element of the matrix FR,

Can be expressed as a constant. Therefore,

Can be determined as shown in the following equation (31).

If the initial state is determined via Equation 31, the network can converge more quickly to a fixed network where the number of nodes does not change. This is because the initial state is similarly formed in a fixed network with a high probability.

b) If policy does not include action (a) = 0

(A) = 0 is not included in the policy, the state transition matrix P can not be expressed as in Equation (28), unlike the case where the policy includes the case in which action (a) = 0.

If the action is greater than 0, this may mean widening the transmission range of the agent, and the s-th row (sth row) of the state transition matrix P may be expressed by the following Equation (32).

Similarly, if the action is less than 0, this may mean reducing the agent's transmission range, and the s-th row (sth row) of the state transition matrix P may be expressed as:

When the action includes a case where the action is 0, the state transition matrix P corresponds to the equation (28), and when the action does not include the case where the action is 0, the state transition matrix P is expressed by the following equation (34) Can be expressed as.

및

는 양의 원소로 구성된 행렬을 나타낼 수 있다. 일례로, upper triangular matrix는 정사각행렬의 주대각선을 기준으로 아래쪽 원소들이 모두 0인 경우를 의미하며, 다음의 수학식 35로 표현될 수 있다. 또한, lower triangular matrix는 정사각행렬의 주대각선을 기준으로 위쪽 원소들이 모두 0인 경우를 의미하며, 다음의 수학식 36으로 표현될 수 있다.Where U represents an upper triangular matrix, L represents a lower triangular matrix,

And

Can represent a matrix of positive elements. For example, the upper triangular matrix means that all the lower elements are 0 based on the main diagonal of the square matrix, and can be expressed by the following equation (35). In addition, the lower triangular matrix means that all the upper elements are 0 based on the main diagonal of the square matrix, and can be expressed by the following equation (36).

은 양의 성분을 가지는 행렬을 나타낼 수 있다. 예를 들면, n=2인 경우

로서, 행렬을 구성하는 원소는 양의 성분일 수 있다. 왜냐하면, Q1/Q2 모두 양의 원소를 가지는 행렬이며, L/U는 확률을 나타내기 때문이다.The normal form of the state transition matrix P expressed by Equation (34), when n is 2 or more,

May represent a matrix having positive components. For example, when n = 2

, The element constituting the matrix may be a positive component. Because Q1 / Q2 are both positive matrices, and L / U represents probability.

At this time, since the state transition matrix P is a stochastic matrix, the perron-Frobenius theorem has a unique eigenvalue and can guarantee that the largest eigenvalue is one.

)은 아이겐밸류(eigenvalue) 1(

)과 관련된 상태 이전 행렬(P)의 행 아이겐벡터(row eigenvector) 일 수 있다. 그리고 초기 상태는 수학식 26에 보이는 가장 큰 극한확률분포(largest limiting distribution)을 갖는 상태가 될 수 있다. Therefore, the limiting distribution,

) Is the eigenvalue 1 (

And a row eigenvector of the state transition matrix P associated with the state transition matrix P. And the initial state can be the state having the largest maximum limiting distribution shown in equation (26).

7 is a diagram illustrating a simulation illustrating the number of nodes according to network size, in accordance with an embodiment of the present invention.

The simulation of FIGS. 7 to 13 below assumes that a plurality of intermediate nodes 120 transmit data from the source node 110 to the plurality of end nodes 130 using network coding. At this time, each intermediate node follows its own policy, which may mean that each intermediate node determines a change in the transmission range based on the number of nodes in the transmission range through each policy.

FIGS. 7 to 13 show a network formed by using a policy according to the proposed strategy, and may also provide a simulation for comparing performance with a network formed by another strategy.

7, in a network formed by two source nodes, two end nodes and a plurality of intermediate nodes, the number of intermediate nodes can be determined according to the PPP whose node density is 4/5. Here, the 4/5 node density corresponds to only one example for the simulation, and the node density may be a different value. Also, PPP can be used to account for the situation where the mobile node, which is the intermediate node in the simulation, is actually distributed.

The size of the network represents the size of the area, and the size of three different networks can be considered. The results of the simulation are based on the results of 1000 independent simulations. Here, the size of the area may indicate the size of the area where the source node, the intermediate node, and the end node are expanded.

When the size of the network is 36, 64, and 100, the lines 712, 722, and 732 in each square box 710, 720, and 730 represent intermediate values of simulation results. That is, when the network size is 36, the intermediate value is 29, the intermediate value is 51 when the network size is 64, and the intermediate value is 80 when the network size is 100.

The top of box 711,721 and 731 of each square box represents the 25th percentile and is relatively small in the bottom of boxes 713,723 and 733 of each square box, Represents the 75th percentile.

Here, PPP can be a random function that returns the number of nodes included in the area using area and density. Thus, in the case of 1000 independent runs, the spectrum of the numerical values from each independent trial can be represented by the median (50th percentile) 29, the 25th largest number, and the 75th smallest number down. Therefore, it can be shown that the longer the square box, the greater the variance.

Thus, it can be confirmed that the intermediate node is generated by the PPP based on the node density.

8 is a diagram illustrating a simulation according to a second policy according to an embodiment of the present invention.

의 값을 기준으로 수학식 23을 만족하는 제2 정책을 결정할 수 있다. 이때, 일례로, 상태 스페이스(S)는 20이며 액션 스페이스(A)는 5로서,

및

를 나타낸다.Each agent that transmits data can determine the second policy by FIG. When deciding on the second policy,

A second policy that satisfies the expression (23) can be determined on the basis of the value At this time, for example, the state space S is 20, the action space A is 5,

And

.

는 상태 스페이스(S)에 포함되는 모든 상태(s)에 대해(즉,

) 반복(iteration)이 증가할수록 0에 수렴하는 것을 나타낸다. As can be seen in the simulation of FIG. 8,

For all the states s included in the state space S (i.e.,

) As the iteration increases, it converges to zero.

를 만족할 때 종결될 수 있다.. 따라서 많은 반복(iteration)이 수행된 이후 반복이 종결될 경우, 결국

를 만족하게 된다. 따라서, 제안된 알고리즘은 수렴하는 것을 나타낼 수 있다.Here, iteration

If the iteration is terminated after a lot of iterations have been performed,

. Thus, the proposed algorithm can indicate convergence.

가 0.3 및 0.9에 따라 수렴하는 속도가 상이한 것을 확인할 수 있다. 즉, 디스카운트 팩터

= 0.3일 때(801)가

= 0.9일 때(802)보다 더 빨리 수렴할 수 있다. 디스카운트 팩터

에 따른 수렴 속도의 차이는 도 9에서 자세히 살펴본다.Discount Factor

Are converged at 0.3 and 0.9, respectively. That is, the discount factor

= 0.3 (801)

= 0.9, it can converge faster than (802). Discount Factor

The difference in the convergence speed according to FIG.

9 is a diagram illustrating simulation of a convergence rate according to a second policy according to a discount factor, in accordance with an embodiment of the present invention.

에 따라 수렴하는 속도가 결정되는 것을 확인할 수 있다. 즉, 도 9는 제2 정책에 따라 노드가 자신의 전송 범위를 결정하고 네트워크가 수렴할 때까지 실행되는 반복(iteration)이 디스카운트 팩터

에 따라 결정되는 것을 나타낼 수 있다. Discount Factor

The convergence speed is determined according to the following equation. That is, FIG. 9 shows that the iteration, which runs until the node determines its transmission range and the network converges according to the second policy,

As shown in FIG.

는 0에서 1사이의 값을 가지며, 디스카운트 팩터

가 크다는 것은 상대적으로 예측된 미래의 상태-가치에 더 큰 가중치를 부과할 수 있다는 것을 의미할 수 있다. Discount Factor

Has a value between 0 and 1, and the discount factor

A larger value can mean that we can impose a larger weight on the relatively predicted future state-value.

가 상대적으로 클 경우, 예측된 미래의 상태-가치에 큰 가중치를 두게 되므로 상태-가치 함수가 수학식 22를 만족하며 수렴하는데 더 오랜 시간이 소비될 수 있다. 즉, 다시 말하면, 제2 정책을 결정하기 위해 상대적으로 더 많은 반복을 해야 하므로, 더 오랜 시간이 소비될 수 있다. Thus, the discount factor

A relatively large weight is assigned to the predicted future state-value, so that the state-value function satisfies (Equation 22) and a longer time can be spent to converge. In other words, a longer time may be consumed since relatively more iterations are required to determine the second policy.

가 상대적으로 작을 경우, 상태-가치 함수가 수학식 22를 만족하며 수렴하는데 더 짧은 시간이 소비될 수 있다. 즉, 다시 말하면, 제2 정책을 결정하기 위해 상대적으로 더 적은 반복을 해야 하므로, 더 짧은 시간이 소비될 수 있다.Conversely, the discount factor

Is relatively small, the state-value function may satisfy Equation (22) and a shorter time may be consumed to converge. That is, in other words, a shorter time may be consumed since relatively few iterations are required to determine the second policy.

10 is a diagram illustrating a simulation according to a weight w in a network connection, according to an embodiment of the present invention.

Figure 10 shows the simulation results in terms of the number of links set in the network for the size of the network. Also, FIG. 11 can show the simulation results in terms of the number of links and algebraic connectivity in the network according to the link failure rate.

The number of links constructed in the network can be quantified by counting the number of links established in the network as a quantitative unit that measures the degree of network connectivity.

In contrast, algebraic connectivity is a qualitative unit that evaluates the degree of network connectivity, which can indicate how well the components of the network are connected.

Figure 10 shows the effect of the weight (w) of the utility function on network connectivity. In this case, the weight w is a value between 0 and 1, and can represent the weight of the reward in the utility function. This is because the weight w is used to balance the reward and the cost of the transmitted power.

Thus, if the weight w is high, the network may mean that it weights more than the cost of the transmit power, and vice versa, if the weight w is low, it may mean that more weight is applied to the cost of the transmission power than the reward.

), 디스카운트 팩터는 0.5(

)를 가정한다.Figure 10 shows that there is no link failure rate

), The discount factor is 0.5 (

).

FIG. 10 shows that the number of links is proportional to both the network size and the weight (w). That is, in the case of a high weight (w), the intermediate node widens the transmission range to include a large number of links, thereby providing a gain in network throughput rather than the consumption of the transmission power.

11 is a diagram illustrating a network connection according to a link failure rate according to an embodiment of the present invention.

가 증가할 때, 더 많은 링크의 수(1110, 1120. 1130)를 나타낸다. 이는, 네트워크가 대략적으로 같은 수의 유효 노드를 유지하기 위함이다. 즉, 채널의 링크 실패율이 증가하더라도, 같은 수의 유효 노드를 유지하기 위해, 더 많은 링크의 수를 포함해야 하기 때문이다. 따라서, 도 11(a)는 링크 실패율이 증가하더라도, 거의 일정한 유효 노드의 수(1111, 1121, 1131)를 나타내는 것을 확인할 수 있다.11 (a) shows the link failure rate

(1110, 1120, 1130) when the number of links increases. This is so that the network maintains approximately the same number of valid nodes. That is, even if the link failure rate of the channel increases, it is necessary to include a larger number of links in order to maintain the same number of valid nodes. Therefore, FIG. 11A shows that the number of valid nodes 1111, 1121, and 1131 is almost constant even if the link failure rate increases.

가 증가할 때, 대수적 연결정도(algebraic connectivity)가 네트워크의 사이즈에 관계없이 증가하는 것을 나타낸다. 이는, 불안정한 채널을 극복하기 위해 더 긴밀하게 연결된 네트워크를 구성하기 때문이다. 11 (b) shows the link failure rate

Indicates that algebraic connectivity increases regardless of the size of the network. This is because they form a more tightly coupled network to overcome unstable channels.

Therefore, by considering the link failure rates of the channel, it indicates that the number of nodes in the network can be changed to a fixed network without changing.

Meanwhile, the method according to the present invention may be embodied as a program that can be executed by a computer, and may be embodied as various recording media such as a magnetic storage medium, an optical reading medium, and a digital storage medium.

Implementations of the various techniques described herein may be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or combinations thereof. Implementations may be implemented in a computer program product, such as an information carrier, e.g., a machine readable storage device, such as a computer readable storage medium, for example, for processing by a data processing apparatus, Apparatus (computer readable medium) or as a computer program tangibly embodied in a propagation signal. A computer program, such as the computer program (s) described above, may be written in any form of programming language, including compiled or interpreted languages, and may be stored as a stand-alone program or in a module, component, subroutine, As other units suitable for use in the present invention. A computer program may be deployed to be processed on one computer or multiple computers at one site or distributed across multiple sites and interconnected by a communications network.

Processors suitable for processing a computer program include, by way of example, both general purpose and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The elements of a computer may include at least one processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer may include one or more mass storage devices for storing data, such as magnetic, magneto-optical disks, or optical disks, or may receive data from them, transmit data to them, . &Lt; / RTI &gt; Information carriers suitable for embodying computer program instructions and data include, for example, semiconductor memory devices, for example, magnetic media such as hard disks, floppy disks and magnetic tape, compact disk read only memory A magneto-optical medium such as a floppy disk, an optical disk such as a DVD (Digital Video Disk), a ROM (Read Only Memory), a RAM , Random Access Memory), a flash memory, an EPROM (Erasable Programmable ROM), an EEPROM (Electrically Erasable Programmable ROM), and the like. The processor and memory may be supplemented or included by special purpose logic circuitry.

In addition, the computer-readable medium can be any available media that can be accessed by a computer, and can include both computer storage media and transmission media.

While the specification contains a number of specific implementation details, it should be understood that they are not to be construed as limitations on the scope of any invention or claim, but rather on the description of features that may be specific to a particular embodiment of a particular invention Should be understood. Certain features described herein in the context of separate embodiments may be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment may also be implemented in multiple embodiments, either individually or in any suitable subcombination. Further, although the features may operate in a particular combination and may be initially described as so claimed, one or more features from the claimed combination may in some cases be excluded from the combination, Or a variant of a subcombination.

Likewise, although the operations are depicted in the drawings in a particular order, it should be understood that such operations must be performed in that particular order or sequential order shown to achieve the desired result, or that all illustrated operations should be performed. In certain cases, multitasking and parallel processing may be advantageous. Also, the separation of the various device components of the above-described embodiments should not be understood as requiring such separation in all embodiments, and the described program components and devices will generally be integrated together into a single software product or packaged into multiple software products It should be understood.

It should be noted that the embodiments of the present invention disclosed in the present specification and drawings are only illustrative of specific examples for the purpose of understanding and are not intended to limit the scope of the present invention. It will be apparent to those skilled in the art that other modifications based on the technical idea of the present invention are possible in addition to the embodiments disclosed herein.

110: source node
120: intermediate node
130: terminating node

Claims (11)

A network forming method performed by a network forming apparatus for connecting a source node and an end node via a plurality of intermediate nodes,
Determining a state space, an action space, a state transfer probability, a utility function, and a discount factor satisfying a Markov property;
Determining a policy of the agent to determine whether a transmission range of an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes changes; And
Based on the determined policy, forming an initial state of the network by using an extreme probability distribution
Lt; / RTI &gt;
And the initial state is a state in which the maximum probability distribution has a maximum probability distribution, and the maximum probability distribution indicates a probability of converging to a specific state in which the number of nodes forming the network does not change after an infinite number of states are transferred,
Network formation method
The method according to claim 1,
Wherein the state space represents a set of states indicating the number of valid nodes that have received the data from an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes,
Wherein the action space indicates a set of actions indicating a change in the transmission range to which the data can be transmitted from the agent,
The state transition probability indicates a probability of transition from the current state to the next state by the action,
Wherein the utility function comprises a network throughput enhancement and a transmit power consumed when moving from the current state to the next state,
Wherein the discount factor is indicative of a decrease in utility function over time.
3. The method of claim 2,
The policy includes:
A first policy to optimize the state-value function, which is a cumulative utility function at a particular time, or
Value function by the first policy is a second policy indicating a state-value function whose error with the state-value function by the first policy is less than a predetermined value.
3. The method of claim 2,
Wherein the intermediate node comprises:
Wherein data received from the source node or another intermediate node is encoded in a Galois Field.
3. The method of claim 2,
The action includes:
Increasing the transmission range if the action is greater than 0,
Or if the action is less than zero, reducing the transmission range,
Or if the action is 0, the transmission range is not changed.
3. The method of claim 2,
The discount factor comprises:
A network formation method determined based on network consistency.
3. The method of claim 2,
In the initial state,
If the policy includes a case where the action is 0, it indicates a state having the maximum probability distribution of probability,
Or when the policy does not include a case where the action is 0, the eigenvalue represents a row eigenvector of the state transition matrix associated with 1. [
3. The method of claim 2,
Wherein the utility function uses a weight that adjusts the balance of the compensation of the network throughput enhancement and the cost of the transmitted power to be consumed.
A network forming method performed by a network forming apparatus for connecting a source node and an end node via a plurality of intermediate nodes,
Confirming the number of valid nodes receiving data from the agent included in the initial state of the formed network based on the policy of the agent which is the intermediate node;
Determining an action using a policy that forms the initial state; And
Updating the transmission range of the data according to the determined action
Lt; / RTI &gt;
Wherein the initial state represents a state having a maximum probability distribution of probabilities and the probability distribution of probabilities represents a probability of converging to a specific state in which the number of nodes forming the network does not change after an infinite number of states are transferred,
Network formation method.
A network forming apparatus comprising:
Wherein the network forming apparatus comprises a processor,
The processor comprising:
Connecting a source node and an end node through a plurality of intermediate nodes,
An action space, a state transfer probability, a utility function, and a discount factor satisfying a Markov property,
Determining a policy of the agent for determining whether a transmission range of an agent that is an intermediate node for transmitting data among the plurality of intermediate nodes changes,
Based on the determined policy, forming an initial state of the network by using an extreme probability distribution,
And the initial state is a state in which the maximum probability distribution has a maximum probability distribution, and the maximum probability distribution indicates a probability of converging to a specific state in which the number of nodes forming the network does not change after an infinite number of states are transferred,
Network forming device.
A network forming apparatus comprising:
Wherein the network forming apparatus comprises a processor,
The processor comprising:
When connecting a source node and an end node via a plurality of intermediate nodes, confirms the number of valid nodes that receive data from the agent included in the initial state of the network formed based on the policy of the agent that is the intermediate node,
Determining an action using the policy that forms the initial state,
Updates the transmission range of the data according to the determined action,
Wherein the initial state represents a state having a maximum probability distribution of probabilities and the probability distribution of probabilities represents a probability of converging to a specific state in which the number of nodes forming the network does not change after an infinite number of states are transferred,
Network forming device.

Images