CROSS-LAYERED RESOURCE ALLOCATION METHOD BASED ON WEIGHTED DESYNC IN WIRELESS AD-HOC NETWORK

Abstract

Provided is a Weighted DESYNC based cross-layered resource allocation method. The method includes, with respect to each of a plurality of nodes constituting a routing path, calculating a link quality value with the next node, receiving a link quality value from at least one neighbor node, and based on the link quality values in the calculating of the link quality value and the receiving of the link quality value, calculating a weight factor for synchronizing a transmission yield.

Claims

1. A Weighted DESYNC based cross-layered resource allocation method, which is performed on each of a plurality of nodes constituting a routing path, the method comprising: calculating a link quality value with the next node; receiving a link quality value from at least one neighbor node; and based on the link quality values in the calculating of the link quality value and the receiving of the link quality value, calculating a weight factor for synchronizing a transmission yield.

2. The method of claim 1, wherein the calculating of the link quality comprises calculating a link quality value with the next node on the basis of a signal to noise ratio (SNR) with the next node and an amount of an allocated time slot.

3. The method of claim 2, wherein the receiving of the link quality comprises receiving a link quality value from at least one neighbor node by a Route Request (RREQ) occurring during a routing process.

4. The method of claim 3, wherein the calculating of the weight factor comprises calculating the weight factor based on a result obtained by comparing a local average data rate and its own data rate.

5. The method of claim 4, wherein the calculating of the weight factor comprises calculating the weight factor on the basis of an average of differences between a link quality value of the next node and link quality values received from 1-hop neighbor nodes.

6. The method of claim 5, wherein the calculating of the weight factor comprises calculating its own firing phase information in the next frame on the basis of firing phase information and weight information received from 2-hop-within-neighbor nodes.

7. The method of claim 5, wherein the calculating of the weight factor comprises, if there is a node belong to a plurality of paths, performing firing the number of times that the node belongs to the plurality of paths.

8. The method of claim 7, wherein the calculating of the weight factor comprises using a firing message including Path info for distinguishing a path that the corresponding node belongs.

9. The method of claim 8, wherein the path information comprises ID information on the next nodes of the corresponding node.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate exemplary embodiments and together with the description serve to explain the principles of the invention.

[0026] In the drawings:

[0027] FIG. 1 is a conceptual diagram illustrating an end-to-end transmission yield and delay issue according to a link quality;

[0028] FIG. 2 is a conceptual diagram illustrating a firing message structure according to the present invention;

[0029] FIG. 3 is a flowchart illustrating a resource allocation method according to the present invention;

[0030] FIG. 4 is a conceptual diagram illustrating a link quality reception method according to the present invention;

[0031] FIG. 5 is a conceptual diagram illustrating the condition of a weight factor according to the present invention;

[0032] FIG. 6 is a conceptual diagram illustrating an operation of a node having two or more paths; and

[0033] FIG. 7 is a conceptual diagram illustrating path information included in a firing message structure according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION

[0034] Hereinafter, exemplary embodiments disclosed in this specification will be described in detail with reference to the accompanying drawings, and the same or similar elements are designated with the same numeral references regardless of the numerals in the drawings and their redundant description will be omitted. The suffixes “module” and “unit” for elements used in the following description are given or used interchangeably only for facilitation of preparing this specification, and thus they are not granted a specific meaning or function. In describing exemplary embodiments disclosed in this specification, a specific description for publicly known technologies to which the invention pertains will be omitted when the description is judged to obscure the gist of the embodiments disclosed in the specification. Also, it should be understood that the accompanying drawings are merely illustrated to easily explain exemplary embodiments disclosed in this specification, and therefore, they should not be construed to limit the technical idea disclosed in this specification but be construed to cover all modifications and alternatives falling within the spirit and scope of the present invention.

[0035] Although the terms “first,” “second,” etc., may be used herein to describe various elements, these elements should not be limited by these terms. The above terms are used only to distinguish one component from another.

[0036] When it is mentioned that a certain component is “coupled with” or “connected with” another component, it should be understood that the certain component is directly “coupled with” or “connected with” to the other component or a further component may be located therebetween. In contrast, when it is mentioned that a certain component is “directly coupled with” or “directly connected with” another component, it will be understood that a further component is not located therebetween.

[0037] The singular forms ‘a,’ ‘an,’ and ‘the’ include plural reference unless the context clearly dictates otherwise.

[0038] It will be further understood that the terms “comprises,” “comprising,” “includes,” and/or “including” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or a combination thereof.

[0039] The present invention suggests a method for determining an optimized weight factor so as to improve an end-to-end transmission yield and minimize a queuing delay on a path of W-DESYNC.

[0040] In order to improve an end-to-end transmission yield and minimize a queuing delay on a path, it is preferable to synchronize a transmission yield on a path. In order to design such a weight factor, an accurate link quality reception through a cross-layered design should be accompanied.

[0041] FIG. 2 is a conceptual diagram illustrating a firing message structure according to the present invention.

[0042] Referring to FIG. 2, in order to resolve a conventional technique issue, a firing message structure is complemented. In more detail, Path info is added to a firing message used in existing W-DESYNC.

[0043] Path info, as information necessary for distinguishing a path that a corresponding node belongs, may include ID information of the following next node on a path with respect to a corresponding node in ID info.

[0044] FIG. 3 is a flowchart illustrating a resource allocation method according to the present invention.

[0045] Referring to FIG. 3, in order to use a newly suggested weight factor, a firing phase time slot occupation method (step 3) and a data time slot occupation method (step 4) will be improved from a logical firing method of an existing distributed biomimetic resource allocation method (for example, MH-DESYNC) after routing. In more detail, a transmission yield of a node on a path is to be synchronized through a weighted-DESYNC (W-DESYNC) method. As a result, an end-to-end transmission yield may be improved and a queuing delay may be minimized.

[0046] In order to describe a resource allocation method according to the present invention, first, a link quality will be defined.

[0047] A node i may receive a signal to noise ratio (SNR) to the next node j on a path through a cross-layered design. At this point, the SNR considers transmission power, noise power, and path loss.

[0048] Through SNR.sub.i received in such a manner and the amount of a time slot that the node i receives (for example, bandwidth BW.sub.i), based on Shannon's Theorem, a link quality d.sub.i,j between the node i and the node j may be defined as the following Equation 1.

d.sub.i,j=BW.sub.i×log.sub.2(1+SNR.sub.i,j)  [Equation 1]

[0049] FIG. 4 is a conceptual diagram illustrating a link quality reception method according to the present invention.

[0050] Referring to FIG. 4, a link quality is received through RREQ occurring from a routing process from a node N1 to a node N4.

[0051] At this point, based on a node N2, the node N2 may receive d.sub.N1,N2 received from the node N1, d.sub.N2,N3 that the node N2 itself transmits to a node N3, and d.sub.N3,N4 that the node N2 overhears when the node N3 transmits information to the node N4.

[0052] Here, the overhearing refers to a case that when the node N3 transmits RREQ to the node N4, the node N2 receives RREQ that is not the information that the node N3 transmits to the node N2.

[0053] Then, the definition of a weight factor will be described. For this, first, the condition of a weight factor may be defined by the following Equation 2.

0<w<w.sub.max  [Equation 2]

[0054] In order to operate normally according to the equation of W-DESYNC, a weight factor should be greater than 0. Moreover, in order to prevent a specific terminal from monopolizing a resource, it should not have a too large value.

[0055] Accordingly, in terms of a structure, when a transmission yield of a node is less than a local average data rate, a weight factor should be increased, and when a transmission yield of a node is greater than a local average data rate, a weight factor should be decreased.

[0056] FIG. 5 is a conceptual diagram illustrating the condition of a weight factor according to the present invention.

[0057] Referring to FIG. 5, based on the node N2, since a data rate of the node N2 is lower than its Local average data rate, a weight factor w.sub.N2(t) should be increased.

[0058] When a weight factor is designed, a set of 1-hop neighbor nodes of the node i may be defined as N.sub.1(i) and a weight factor of the node i in a frame t may be defined as w.sub.i(n). Accordingly, in a frame t+1, a weight factor w.sub.i(n+1) of the node i is defined as the following Equation 3 through d.sub.i(n) obtained through Equation 1 and d.sub.i(n) of a 1-hop neighbor node j (j∈N.sub.1j≠i).

[00001]$\begin{array}{cc}{\omega }_i\left(n+1\right)={\omega }_i\left(n\right)+\frac{1}{.Math.N_1.Math.}.Math.\underset{j\in N_1,j\ne i}{.Math.}.Math.\left(d_j\left(n\right)-d_i\left(n\right)\right)& \left[\mathrm{Equation}.Math..Math.3\right]\end{array}$

[0059] Through the Equation 3, after calculating an average of differences between a link quality d.sub.i(t) and a link quality d.sub.i(n) received from 1-hop neighbor nodes to a weight factor w.sub.i(n) of the node i in a frame n, the node i may determine whether to increase or reduce the weight factor w.sub.i(n) and then, apply it to a weight factor w.sub.i(n+1) in a frame n+1.

[0060] In relation to a W-DESYNC based cross-layered resource allocation method according to the present invention, an embodiment of an update method when a node belongs to one path will be described below.

[0061] In the W-DESYNC method, each node i calculates forward mid and backward mid values through firing phase information and weighted information of 2-hop neighbor nodes that each node i receives.

[0062] For example, if a node i receives a firing message of a node k, forward mid and backward mid values may be calculated by the following Equation 4 through firing phase information φ.sub.1 and a weight factor w.sub.i(n) of the node i and firing phase information φ.sub.k and a weight factor w.sub.k(n) of the node k. At this point, the weight factor is calculated through the Equation 3.

[00002]$\begin{array}{cc}{\phi }_k=\mathrm{floor}.Math..Math.{\phi }_i-\frac{{\omega }_i}{{\omega }_k+{\omega }_i}.Math.\left({\phi }_i-{\phi }_k-1\right).Math.+1.Math..Math.{\phi }_k=\mathrm{floor}.Math..Math.{\phi }_i+1+\frac{{\omega }_i}{{\omega }_i+{\omega }_k}.Math.\left({\phi }_k-{\phi }_i-1\right).Math.& \left[\mathrm{Equation}.Math..Math.4\right]\end{array}$

[0063] Here, the first equation means Forward Mid and the second equation means Backward Mid.

[0064] When Firing phase information of a forward node having the greatest influence on itself is defined as φ.sub.forward and its weight factor is defined as w.sub.forward, and firing phase information of a backward node having the greatest influence on itself is defined as φ.sub.backward and its weight factor is defined as w.sub.backward, its firing phase information in the next frame may be calculated by the following Equation 5.

[00003]$\begin{array}{cc}{\phi }_i^{\prime }\left(D\right)=\mathrm{round}.Math..Math.\frac{{\omega }_{\mathrm{forward}}+{\omega }_i}{{\omega }_{\mathrm{forward}}+{\omega }_{\mathrm{backward}}+2.Math.{\omega }_i}.Math.\left({\phi }_{\mathrm{backward}}-{\phi }_{\mathrm{forward}}\right).Math.+{\phi }_{\mathrm{forward}}& \left[\mathrm{Equation}.Math..Math.5\right]\end{array}$

[0065] At this point, the node occupies a resource from a forward mid value of its forward node to a backward mid value of its backward node. In synchronizing a transmission yield, each path calculates a weight factor and synchronizes a transmission yield, separately.

[0066] In relation to a W-DESYNC based cross-layered resource allocation method according to the present invention, an embodiment of an update method when two or more nodes belong to one path will be described below.

[0067] When one node belongs to two or more paths, as firing is performed the number of times that the node belongs to paths, a separate resource may be allocated to each path. For this, the above-defined firming message structure becomes required.

[0068] In more detail, when firing is performed on one node several times, in order to calculate a weight factor that matches each path, a distinction on which path each firing belongs to is required. For this, additional data, that is, new Path Info, is to be included in a firing message and transmitted.

[0069] If the node i is a node that performs firing more than two times, a weight factor of the node i is defined as w.sub.i.sup.j(n). j is the ID of the next node to be transmitted of the node i.

[0070] FIG. 6 is a conceptual diagram illustrating an operation of a node having two or more paths.

[0071] Referring to FIG. 6, in relation to two paths 1-2-3-4 and 6-2-6-7 as a node 2 used in the both paths performs firing two times, one frame receives a data time slot used in the path 1-2-3-4 and a data time slot used in the path 6-2-6-7 separately.

[0072] Additionally, a weight factor w.sub.2.sup.3(n) of the node 2 used in the path 1-2-3-4 and a weight factor w.sub.2.sup.6(n) of the node 2 used in the path 6-2-6-7 are calculated separately.

[0073] FIG. 7 is a conceptual diagram illustrating path information included in a firing message structure according to the present invention.

[0074] Referring to FIG. 7, as described with reference to FIG. 6, the node 2 performs firing two times according to the number of overlapping paths, and during each firing, is required to distinguish which path each firing belongs to in order to match a transmission yield in each corresponding path.

[0075] For this, the firing message structure includes each Path Info and inserts the ID of a node 6 and the ID of a node 3 to each Path Info.

[0076] In a wireless ad-hoc network according to the present invention, the effect of a W-DESYNC based cross-layered resource allocation method will be described as follows.

[0077] In a wireless ad-hoc situation, when a node itself receives an allocated resource through W-DESYNC, in order to determine an optimized weight factor, the node may receive a transmission yield on a path through a cross-layered design.

[0078] Then, as a weight factor is determined based on the received information in such a manner, it is possible to synchronize the transmission yields of all nodes on a path. As a result, an end-to-end transmission yield may be improved and a queuing delay may be minimized.

[0079] The invention can also be implemented as computer-readable codes in a computer-readable recording medium. The computer-readable recording medium is any data storage device that can store data which can thereafter be read by a computer system. Examples of the computer-readable recording medium include a Hard Disk Drive (HDD), a Solid State Disk (SSD), a Silicon Disk Drive (SDD), a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, and an optical data storage. Further, the record medium may be implemented in the form of a carrier wave (e.g., Internet transmission). Therefore, the foregoing detailed description is to be regarded as illustrative and not restrictive. The scope of the present invention should be determined only by the reasonable interpretation of the appended claims so as to encompass all such modifications and equivalents.