JP4774559B2 - Method and apparatus for estimating distance between nodes in communication network - Google Patents

Description

  The present invention relates to an inter-node distance estimation method and apparatus for improving end-to-end communication quality in the Internet, and more particularly to an end-of-end communication path using an overlay network logically formed on an IP network. The present invention relates to an inter-node distance estimation method and apparatus in a communication network capable of efficiently improving two-end communication quality.

  The Internet, which represents an IP network, has been developed and popularized to accommodate various applications. Recently, the Internet is sensitive to VoIP (Voice over IP) and QoS (Quality of Service) typified by streaming. The containment of time applications etc. is also developing rapidly.

Along with this, it is an important issue to realize technology ("end-to-end QoS management technology") on the Internet to avoid end-to-end congestion and improve quality. ing. However, there are problems as described below in realizing such a technique.
(1) The Internet has already become a social infrastructure, and it is difficult to expand new functions at the network layer, which greatly changes the existing network structure.
(2) The Internet is formed by a plurality of ASs (Autonomous Systems) having different management entities, and it is difficult to extend new functions to all ASs simultaneously.

  Under such circumstances, as a promising technology capable of improving end-to-end QoS without changing a lower network layer, for example, L.P. Zhi and P.M. Mohapra, “QRON: QoS-aware routing in overlay net-works,” IEEE J. MoI. Select. Areas Commun. , Vol. 22, pp. 29-40, January 2004. The QoS management technology using an overlay network described in (Non-Patent Document 1) is drawing attention. The overlay network is, for example, the WIDE project, “Integrated distributed environment by overlay network,” WIDE Progent Research Report, Part 17, 2002. As described in (Non-patent Document 2), this is a network that uses an existing link to form a logical (virtual) link in the upper layer according to the purpose and configure it.

The basic concept of QoS management by such an overlay network will be described with reference to FIG.
In FIG. 1, consider a case where communication is desired from node a to node c.
At this time, there are cases where the delay time is smaller than the delay time in the case of direct transfer from a to c via the detour path in which the transfer from a to b is once and then transferred from b to c (for example, IP (For example, due to inter-domain routing policy in the network). At this time, if the traffic can be detoured on the route (overlay node a → overlay node b → overlay node c) represented by the practical arrow using the overlay network formed by the overlay nodes a, b, and c, the QoS is determined. Can be improved.

  In fact, Kamei and Kawahara, “Traffic Engineering and its Effectiveness by End-Host Overlay Network,” Shingaku Sodai, BS-5-3, 2004. (See Non-Patent Document 3), S.A. Rewaskar and J.H. Kaur, “Testing the Scalability of Overlay Infrastructures,” Proc. PAM2004. April 2004. (See Non-Patent Document 4), S.A. Banerjee, T .; G. Grifin and M.M. Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004. (See Non-Patent Document 5), based on actual measurements, shows that there are many detour paths as described above in the real network.

However, in order to find such a detour route, it is necessary to measure the distance between any two nodes. The results of Non-Patent Document 3 and Non-Patent Document 5 are the evaluations when the ideal communication path calculation is performed using the quality information measured between all overlay nodes and the topology of the overlay network is a full mesh. Thus, no consideration is given to a decrease in scalability (system extensibility) when the total number of overlay nodes increases.
That is, when the total number of overlay nodes is large, there has been a problem that it is impossible in practice to calculate communication paths using quality measurement information between all overlay nodes.

  Further, not only in the overlay network, for example, in content distribution, when there are a plurality of servers, quality information between nodes is required when a server with a short distance is selected.

L. Zhi and P.M. Mohapra, “QRON: QoS-aware routing in overlay net-works,” IEEE J. MoI. Select. Areas Commun. , Vol. 22, pp. 29-40, January 2004. WIDE Project, “Integrated Distributed Environment with Overlay Network,” WIDE Progent Research Report, Part 17, 2002. Kamei, Kawahara, “Traffic engineering by end-host overlay network and its effectiveness,” Shingaku Sodai, BS-5-3, 2004. S. Rewaskar and J.H. Kaur, “Testing the Scalability of Overlay Infrastructures,” Proc. PAM2004. April 2004. S. Banerjee, T .; G. Grifin and M.M. Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004.

  As described above, in the basic concept of QoS management by the overlay network, there is a case where the delay time is once shorter via the detour path. However, in order to find a detour route, the distance between any two nodes had to be measured. However, the decrease in scalability (system scalability) when the total number of overlay nodes increases has not been considered. That is, when the total number of overlay nodes is large, it is not practical to calculate communication paths using quality measurement information between all overlay nodes.

(the purpose)
SUMMARY OF THE INVENTION An object of the present invention is to solve the above-mentioned problems and to estimate a distance between nodes in a communication network capable of estimating a distance between any two nodes without directly measuring the distance between all two nodes. It is to provide such a device.

The inter-node distance estimation method according to the present invention includes: (1) an inter-node distance estimation method for estimating a distance between nodes (round trip time: RTT, etc.) for N nodes connected to the Internet; Is mapped to a geometric coordinate space of dimension k, and each node on the global coordinate space is divided into K clusters, each node being a local coordinate space in the cluster to which it is mapped. have. That is, each node has two coordinate positions in the global coordinate space and the coordinate position in the local coordinate space. Using these coordinate positions, the distance between any two nodes is estimated.
Here, each node on the Internet is mapped to a virtual coordinate space. For example, it is assumed that the coordinate space has two dimensions, the coordinate position of the node a is (x_a, y_a), and that of the node b is (x_b, y_b). If it can be mapped to the coordinate space in this way, the distance between nodes can be calculated by sqrt [(x_a−x_b] ∧ 2+ (y_a−y_b) ∧ 2], that is, without measuring the distance between two nodes of interest each time, Once the coordinate position of the node is determined, it can be easily calculated.
Here, the nodes are divided into a plurality of clusters so that each node belongs to one of the clusters and has a local coordinate position in the cluster. In this way, when estimating the distance between two nodes belonging to the same cluster, the distance can be estimated using the local coordinate position.

In the inter-node distance estimation method of the present invention, (2) m landmark nodes are selected from the target N nodes, and the distance d (L_i, L_j) between the landmark nodes L_i and L_j is selected. ) And use it to group m landmark nodes into K clusters. Thereafter, each general node i (a node that is not a landmark node) measures the distance d (i, L_j) to each landmark node L_j, and the node i belongs to the cluster to which the nearest landmark node belongs. It is said.
Here, as a method for classifying m landmarks into K clusters, for example, a K-means method which is a typical statistical analysis method may be used.

In the inter-node distance estimation method of the present invention, (3) an m × m matrix D having a distance d (L_i, L_j) between landmark nodes L_i and L_j as elements is created, and a singular value for D Matrix decomposition called decomposition (single value decomposition: SVD) is performed, and the result is D = U · W · V ^T. Here, U and V are m × m orthogonal matrices, and W is a diagonal matrix. In addition, ^{V T} denotes a transposed matrix of V. Next, for the landmark node L_i, an m × 1 vector φ (L_i) = [d (L_i, L_1), d (L_i, L_2) having a distance d (L_i, L_j) between L_i and L_j as elements. ,..., D (L_i, L_m)] ^T , while extracting the first k columns of U and making it Uk (m × k matrix), φ ′ (L_i) = Uk ^T × φ A feature is that the k-dimensional vector φ ′ (L_i) obtained in (L_i) is set as the global coordinate position of the landmark node L_i.

The inter-node distance estimation method of the present invention is as follows: (4) An m × 1 vector φ ′ (i) = [with a distance d (i, L_j) between i and a landmark node L_j as an element for a general node i. d (i, L_1), d (i, L_2),..., d (i, L_m)] ^T is created, and then the global of the general node i is obtained by the same procedure as the method (3) above. It is characterized by calculating the coordinate position.

The inter-node distance estimation method of the present invention is (5) for mx landmark nodes L_ {l, x}, l_ {2, x},..., L_ {mx, x} belonging to a certain cluster x. Then, a matrix Dx of mx × mx having a distance d (L_ {i, x}, L_ {j, x}) between the landmark nodes L_ {i, x} and L_ {j, x} as elements. And singular value decomposition is performed on the Dx, and the result is Dx = Ux · Wx · Vx ^T. Next, with respect to the landmark node L_ {i, x}, a distance d (L_ {i, x}, L_ {j, x}) between L_ {i, x} and L_ {j, x} is used as an element. Mx × 1 vector φx (L_i) = [d (L_ {i, x}, L_ {1, x}, d (L_ {i, x}, L_ {2, x}),... d (L_ {i, x}, L_ {mx, x})] ^T , while extracting the first k columns of Ux and making it Uxk (mx × k matrix), φx ′ (L_i ) = Uxk ^T × φx (L_i), and the k-dimensional vector φx ′ (L_i) is a local coordinate position in the cluster x of the landmark node L_ {i, x}.

In the inter-node distance estimation method of the present invention, (6) the distance d (i_x, L_ {j, x}) between i_x and the landmark node L_ {j, x} is an element for the general node i_x belonging to the cluster x. Mx × 1 vector φx (i) = [d (i_x, L_ {1, x}), d (i_x, l_ {2, x},..., D (i_x, L_ {mx, x })] ^T is created, and thereafter, the local coordinate position of the general node i_x in the cluster x is calculated by the same procedure as the method (5).

In the inter-node distance estimation method of the present invention, (7) Lx nodes are selected from the cluster x, and the global coordinate position of the node j (j = 1,..., Lx) is represented by φx′G (j) ( k × 1D vector), local coordinate position is φx′C (j) (k × 1D vector), and Lx × k matrix PGx = [φx′G (1), φx′G (2) ,..., Φx′G (Lx)] ^T , PCx = [φx′C (l), φx′C (2),..., Φx′C (Lx)] ^T, and create TGx = PGx XPCx ^-1 (PCx ^-1 means inverse matrix, PCx x PCx ^-1 = unit matrix, satisfying) is calculated, and TGx is converted from the local coordinate space in the cluster x to the global one A local coordinate position is given as φx′C (y) for a node y in the cluster. When the as φx'G (y) = TGx × φx'C (y), it is characterized by estimating a global coordinate position φx'G (y) of the node.

The inter-node distance estimation method of the present invention uses (8) the global coordinate position φ ′ (i) of the node i obtained by the above method (4) or (7), and φ ′ (i) = [ (Fl_i, f2_i,..., Fk_i] where ^T is the distance between nodes i and j √ {(f1_i−f1_j) ∧2 + (f2_i−f2_j) ∧2 + ... + (fk_i−fk_j) ∧2} It is characterized by estimating by.

  The inter-node distance estimation method of the present invention is characterized in that (9) the distance between two nodes in the same cluster is estimated using the local coordinate position obtained by the above method (5) or (6). It is said.

  In the inter-node distance estimation method of the present invention, (10) the distance between the landmarks L_i and L_j is calculated by the method (8) using the coordinate position of each landmark node in the method (3). The result is δ (L_i, L_j), while the measured value of the distance between the landmarks L_i and L_j is d (L_i, L_j),

で計算されるαｋをスケールパラメータとし、上記（３），（４）の方法で求まる座標位置にαｋを乗ずることにより座標位置を補正することを特徴としている。

The coordinate position is corrected by multiplying the coordinate position obtained by the above methods (3) and (4) by αk, using αk calculated in step (3) as a scale parameter.

  According to the internode distance estimation method of the present invention, (11) the scale parameter in the cluster is calculated using only the landmark nodes belonging to a certain cluster in accordance with the same procedure as the method in (10) above, The coordinate position is corrected by multiplying the local coordinate position obtained by the procedure of the method (6) by the αk.

  The inter-node distance estimation apparatus according to the present invention includes (12) means for classifying a node into a plurality of clusters by any one of the methods (1) and (2), and a global method for landmark nodes by the method (3). Means for determining a coordinate position, a procedure for determining the global coordinate position of a general node by the method described in (4) or (7), and a local coordinate position by the method of (5) or (6) And a means for estimating the distance between nodes by the method (8) or (9), and a means for correcting the coordinate position by the methods (10) and (11).

  According to the present invention, it is possible to estimate the distance between any two nodes using only the information of the coordinate position without directly measuring the distance between all the nodes, for example, relaying a node with a short distance. By selecting as a node, it becomes possible to perform network management that can improve QoS.

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

FIG. 2 is a configuration diagram showing an example of a basic configuration of a network to which the present invention is applied.
Here, black circles are landmark nodes, and white circles are general nodes. Assume that N nodes are connected to this network.
The landmark node may be selected by the administrator of this network, or when each node connects to the network, it selects whether or not it will become a landmark node and becomes a landmark node. If there is, it may be notified to the already connected node.

FIG. 3 is a functional configuration diagram of the landmark node in FIG.
Each device shown in FIG. 3 is controlled by a computer.
First, the distance measurement management unit 11 in each landmark node measures the distance d (L_i, L_j) between itself (landmark node L_i) and L_j, and the result is obtained by the coordinate calculation / holding unit 12. Hold.
As this distance, a round trip time between nodes is measured (as another example, a one-way delay or a packet loss rate mapped to a distance (a function that increases the distance if the packet loss rate is large is previously determined). Using this, m landmark nodes are grouped into K clusters, for example, using a general statistical method called a k-mans method. May be performed by the network administrator or may be determined there by representing someone at the landmark node.

  In FIG. 3, a portion indicated by a dotted line is a function added to a representative landmark node as an example. Here, when the distance collection unit 13 collects distance information d (L_k, L_j) from other landmark nodes and transmits the result to the cluster calculation unit 14, the cluster calculation unit 14 performs the above-described procedure. It is grouped into individual clusters, and which landmark node belongs to which cluster is notified. FIG. 2 shows an example in which three clusters exist.

The distance collection unit 13 notifies the coordinate calculation matrix calculation unit 15 of the collected distance information. Therefore, an m × m matrix D having elements of the distance d (L_i, L_j) between the landmark nodes L_i and L_j is created, and a matrix called singular value decomposition (SVD) is used for D. Perform decomposition and set the result to D = U · W · V ^T. Here, U and V are m × m orthogonal matrices, and W is a diagonal matrix. In addition, ^{V T} denotes a transposed matrix of V. Next, the first k columns of U are extracted and set as a global coordinate calculation matrix Uk (m × k matrix). The result is notified to the coordinate calculation / holding unit 12 in another landmark node.

The coordinate calculation / holding unit 12 at the landmark node L_i is an m × 1 vector φ (L_i) = [d (L_i, L_1), d (L_i, L_2),..., D (L_i, L_m)]. ^T is created, and the k-dimensional vector φ ′ (L_i) obtained by φ ′ (L_i) = Uk ^T × φ (L_i) is set as the global coordinate position of the landmark node L_i, which is held.

The above-described procedure is a flow until the global coordinate position is calculated, but the same applies to the local coordinate position. Specifically, it is as follows.
The coordinate calculation matrix calculation unit 15 divides the distance d (L_i, L_j) between the landmark nodes L_i and L_j for each cluster, and mx landmark nodes L_ {1, x}, L_ belonging to the cluster x. For {2, x},..., L_ {mx, x}, the distance d (L_ {i, x},) between the landmark nodes L_ {i, x} and L_ {j, x}. An mx × mx matrix Dx having L_ {j, x}) as elements is created, singular value decomposition is performed on the Dx, and the result is Dx = Ux · Wx · Vx ^T. The first k columns of Ux are extracted and set as a local coordinate calculation matrix Uxk (mx × k matrix).
The result is notified to the coordinate calculation / holding unit 12 in another landmark node belonging to the cluster x.

The coordinate calculation / holding unit 12 at the landmark node L_ {i, x} has a distance d (L_ {i, x}, L_ {j, x}) between itself L_ {i, x} and L_ {j, x}. ) Mx × 1 vector φx (L_i) = [d (L_ {i, x}, L_ {1, x}), d (L_ {i, x}, L_ {2, x}), .., D (L_ {i, x}, L_ {mx, x})] ^T is created, and k-dimensional vector φx ′ (L_i) obtained by φx ′ (L_i) = Uxk ^T × φx (L_i) ) Is held as a local coordinate position in the cluster x of the landmark node L_ {i, x}.

Further, the coordinate position collection unit 16 at a certain landmark node in the cluster x selects Lx nodes from the cluster x, and the global coordinate position φx ′ of the node j (i = 1,..., Lx). G (j) (k × 1-dimensional vector) and local coordinate position φx′C (j) (k × 1-dimensional vector) are inquired and collected from each node. The collected coordinate position information is notified to the conversion matrix calculation unit 17. The transformation matrix calculation unit 17 calculates the Lx × k matrix PGx = [φx′G (1), φx′G (2),..., Φx′G (Lx)] ^T , PCx = [φx′C (l ), Φx′C (2),..., Φx′C (Lx)] ^T , and TGx = PGx × PCx ⁻¹ (PCx ⁻¹ means an inverse matrix, PCx × PCx ⁻¹ = unit) Matrix) is calculated, and TGx is converted into a transformation matrix for transforming the local coordinate space in the cluster x into a global one, and this is retained.

FIG. 4 is a functional configuration diagram of the general node in FIG.
The apparatus shown in FIG. 4 is also controlled by a computer.
The behavior of a general node that is not a landmark node will be described with reference to FIG.
The distance measurement management unit 21 measures the distance d (i, L_j) from the own node i to each landmark node L_j, and the node i belongs to the cluster to which the node belongs with respect to the nearest landmark node. Notify that.
The coordinate calculation / holding unit of the general node i_x belonging to the cluster x has an mx × 1 vector having a distance d (i_x, L_ {j, x}) between i_x and the landmark node L_ {j, x} as elements. φx (i) = [d (i_x, L_ {1, x}), d (i_x, L_ {2, x}), ..., d (i_x, L_ {mx, x})] Create ^T On the other hand, the local coordinate calculation matrix Uxk is received from the landmark node, and the k-dimensional vector φx ′ (i) obtained by φx ′ (i) = Uxk ^T × φx (i) As a coordinate position, keep it.

The global coordinate calculation / holding unit 24 receives the transformation matrix TGx held in the transformation matrix calculation unit 17 in the landmark node, calculates the local coordinate position of i_x itself as φx′C (i_x), Reading from the holding unit 22, a calculation of φx′G (i_x) = TGx × φx′C (i_x) is performed, and this is held as a global coordinate position of the node.
The distance estimation unit 23 is notified of the global coordinate position from the partner node j whose distance is to be estimated, and the global coordinate position of i itself is φ ′ (i) = [fl_i, f2_i,..., Fk_i]. ^{As T} , the distance between the nodes i and j is estimated by {square root} {(f1_i-f1_j) ∧2 + (f2_i-f2_j) ∧2 + ... + (fk_i-fk_j) ∧2}.
Alternatively, if the partner is in the same cluster, the partner's local coordinate position is notified and the distance between the two nodes is estimated.

In the first embodiment, the global coordinate position is calculated using the transformation matrix TGx. However, in the second embodiment, instead of the node i as the node i, the distance d (i, L_j) between i and the landmark node L_i is used. M × 1 vector φ (i) = [d (i, L_i), d (i, L_2),..., D (i, L_m)] ^T is created. 1 (Claim 3), the global coordinate position of the general node i is calculated by the same procedure.

The coordinate calculation / holding unit 12 according to the first embodiment calculates the coordinate position of the node. The coordinate position is corrected by multiplying the coordinate position by a scale parameter αk calculated below.
First, as a result of estimating the distance between the landmarks L_i and L_j using the coordinate position of each landmark node, δ (L_i, L_j) is obtained. On the other hand, the actually measured value of the distance between the landmarks L_i and L_j is d. (L_i, L_j)

で計算されるαｋをスケールパラメータとする。

Αk calculated in step 1 is used as a scale parameter.

  In addition, by using only the landmark nodes belonging to a certain cluster, the scale parameter in that cluster is calculated, and the local coordinate position is calculated by the procedure of the first embodiment. to correct.

It is a figure explaining the concept of the route control by an overlay network. It is a block diagram which shows an example of the basic composition of the network to which this invention is applied. It is a block diagram which shows the structural example of the landmark node in FIG. It is a block diagram which shows the structural example of the general node in FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 11 Distance measurement management part 12 Coordinate calculation / holding part 13 Distance collection part 14 Cluster calculation part 15 Coordinate calculation matrix calculation part 16 Coordinate position collection part 17 Transformation matrix calculation part 21 Distance measurement management part 22 Local coordinate calculation / holding part 23 Distance Estimator 24 Global coordinate calculator / holder

Claims (10)

In an inter-node distance estimation method for estimating a distance between nodes by computer control for N nodes connected to the Internet,
Each node is mapped to a geometric coordinate space of dimension k in advance, and each node on the global coordinate space is divided into K clusters defined in advance, and the coordinate position of each node in the global coordinate space is , The coordinate position in the local coordinate space in the cluster in which each node is mapped is held in the memory ,
The computer, by for each node with two coordinate positions in the coordinate position and the local coordinate space in the global coordinate space, Ru using the coordinate position read from the memory, the distance between any two nodes An inter-node distance estimation method in a communication network characterized by estimating. The inter-node distance estimation method in the communication network according to claim 1,
The computer in the node selects m landmark nodes from the target N nodes, and measures a distance d (L_i, L_j) between the landmark nodes L_i and L_j. The distance d is held in a memory, and then m landmark nodes are grouped into K clusters using the distance d read from the memory, and the grouped information is held in the memory. ,
Thereafter, each general node i that is not a landmark node measures the distance d (i, L_j) to each landmark node L_j, and the node i belongs to the cluster to which the nearest landmark node belongs. A method for estimating the distance between nodes in a network. The inter-node distance estimation method in the communication network according to claim 2,
The computer in the landmark node creates an m × m matrix D whose elements are the distance d (L_i, L_j) between the landmark nodes L_i and L_j, and holds this in the memory.
A matrix decomposition called singular value decomposition is performed on the matrix D to output D = U · W · V ^T (where U and V are m × m orthogonal matrices, W is a diagonal matrix, V ^T is the transpose matrix of V),
Next, for the landmark node L_i, the computer has an m × 1 vector φ (L_i) = [d (L_i, L_1), d () having a distance d (L_i, L_j) between L_i and L_j as elements. L_i, L_2),..., D (L_i, L_m)] ^T is created and held in the memory,
On the other hand, the first k columns of U read from the memory are extracted and set as Uk (m × k matrix), and k ′ dimension obtained by φ ′ (L_i) = Uk ^T × φ (L_i) A method for estimating a distance between nodes in a communication network, wherein a vector φ ′ (L_i) is a global coordinate position of a landmark node L_i. The inter-node distance estimation method in the communication network according to claim 2 ,
The computer in the landmark node receives landmarks for mx landmark nodes L_ {l, x}, L_ {2, x},..., L_ {mx, x} belonging to a certain cluster x. Create an mx × mx matrix Dx whose elements are distances d (L_ {i, x}, L_ {j, x}) between nodes L_ {i, x} and L_ {j, x} Singular value decomposition is performed on Dx, and the result is set as Dx = Ux · Wx · Vx ^T
Next, with respect to the landmark node L_ {i, x}, a distance d (L_ {i, x}, L_ {j, x}) between L_ {i, x} and L_ {j, x} is used as an element. Mx × 1 vector φx (L_i) = [d (L_ {i, x}, L_ {1, x}, d (L_ {i, x}, L_ {2, x}),... d (L_ {i, x}, L_ {mx, x})] ^T , while extracting the first k columns of Ux and making it Uxk (mx × k matrix), φx ′ (L_i ) = Uxk ^T × φx (L_i) The k-dimensional vector φx ′ (L_i) obtained as a local coordinate position in the cluster x of the landmark node L_ {i, x} A method for estimating the distance between nodes in a network. The inter-node distance estimation method in the communication network according to claim 2 ,
The computer in the landmark node is mx × having a distance d (i_x, L_ {j, x}) between i_x and the landmark node L_ {j, x} as an element with respect to the general node i_x belonging to the cluster x. 1 vector φx (i) = [d (i_x, L_ {1, x}), d (i_x, L_ {2, x},..., D (i_x, L_ {mx, x})]] ^T create and later more method according to claim 4, inter-node distance estimation method in a communication network, characterized in that to calculate the local coordinate position of the general node i_x cluster x. The inter-node distance estimation method in the communication network according to claim 2,
The computer in the general node selects Lx nodes from the cluster x, and sets the global coordinate position of the node j (j = 1,..., Lx) to φx′G (j) (k × 1-dimensional). Vector), local coordinate position is φx′C (j) (k × 1-dimensional vector), and Lx × k matrix PGx = [φx′G (1), φx′G (2),. φx′G (Lx)] ^T , PCx = [φx′C (l), φx′C (2),..., φx′C (Lx)] ^T is created, and TGx = PGx × PCx ⁻¹ ( PCx ⁻¹ means an inverse matrix, and PCx × PCx ⁻¹ = unit matrix is satisfied), and TGx is converted into a transformation matrix that converts the local coordinate space in the cluster x to a global one, and the cluster For some node y in the local coordinate position is given as φx′C (y) To come, φx'G (y) = TGx × as φx'C (y), inter-node distance estimation method in a communication network, characterized by estimating a global coordinate position φx'G (y) of the node. The inter-node distance estimation method in a communication network according to claim 6,
The computer in the general node uses the global coordinate position φ ′ (i) of the obtained node i, and φ ′ (i) = [(fl_i, f2_i,..., Fk_i] ^T , J is estimated by √ {(f1_i−f1_j) ∧2 + (f2_i−f2_j) ∧2 +... + (Fk_i−fk_j) ∧2} . The inter-node distance estimation method in the communication network according to claim 6 or 7,
The inter-node distance estimation method in a communication network, wherein the computer in the general node estimates the distance between two nodes in the same cluster using the obtained local coordinate position. The inter-node distance estimation method in the communication network according to claim 3,
The computer in the landmark node calculates the result of calculating the distance between the landmarks L_i and L_j by the method according to claim 7 using the obtained coordinate position of each landmark node, δ (L_i, L_j) On the other hand, the measured value of the distance between the landmarks L_i and L_j is d (L_i, L_j),

A method for estimating a distance between nodes in a communication network, wherein αk calculated in step (b) is used as a scale parameter, and the coordinate position is corrected by multiplying the coordinate position obtained by the method according to claim 3 by αk. A distance measurement management unit that measures a distance d (L_i, L_j) between its own landmark node L_i and another landmark node L_j;
A coordinate calculation / holding unit for holding the results measured by the distance measurement management unit;
A distance collection unit that collects distance information d (L_k, L_j) from other landmark nodes;
A cluster calculation unit that receives the results collected by the distance collection unit, groups them into K clusters, and notifies which landmark node belongs to which cluster;
The distance information collected by the distance collecting unit is received, and on the basis of the distance information, an m × m matrix D having a distance d (L_i, L_j) between landmark nodes L_i and L_j as elements is created. Is subjected to matrix decomposition called singular value decomposition, resulting in D = U · W · V ^T (U and V are m × m orthogonal matrices, W is a diagonal matrix, and V ^T is V (Transposed matrix), the first k columns of U are extracted and used as a global coordinate calculation matrix Uk (m × k matrix), and the result is notified to the coordinate calculation / holding unit in other landmark nodes. A matrix calculation unit for calculating coordinates,
Lx nodes are selected from the cluster x, the global coordinate position φx′G (j) (k × one-dimensional vector) of the node j (j = 1,..., Lx), the local coordinate position φx ′. A coordinate position collection unit that inquires and collects C (j) (k × 1D vector) from each node;
The coordinate position information collected by the coordinate collecting unit is received, and an Lx × k matrix PGx = [φx′G (1), φx′G (2),..., Φx′G (Lx)] ^T , PCx = [Φx′C (l), φx′C (2),..., Φx′C (Lx)] ^T is created (TGx = PGx × PCx ⁻¹ (PCx ⁻¹ is an inverse matrix, PCx × PCx ⁻¹ = unit matrix), and TGx is a transformation matrix that transforms the local coordinate space in the cluster x into a global transformation matrix, and includes a transformation matrix calculation unit that holds the transformation matrix. Landmark node device in the network.

Images