CN105282267B - A kind of network entity City-level localization method based on landmark clustering - Google Patents

Abstract

The invention discloses a city-level positioning method for network entities based on landmark clustering, which includes the following steps: A: Deploy detection sources in multiple different geographical locations; B: Measure the round-trip between each detection source and all physical landmarks Delay; C: Divide all physical landmarks into different groups according to area, and obtain the average delay vector of each area; D: Measure the round-trip delay between each detection source and the network entity to be located; E: Calculate the time to be located The relative delay vector from the network entity to each area; F: Select the minimum relative delay vector, and the area corresponding to the minimum relative delay vector is the location of the network entity to be located. Compared with network entity positioning technology based on network measurement, this invention can effectively avoid the impact of network congestion, load balancing, heterogeneous networks and poor network equipment performance on network delay expansion and delay jitter, and significantly improve physical landmarks. The number of mines while improving the city-level positioning accuracy of network entities can provide reliable landmarks for network city-level positioning.

Description

A city-level positioning method for network entities based on landmark clustering

technical field

The invention relates to the technical field of information security, in particular to a city-level positioning method for network entities based on landmark clustering.

Background technique

Network entity positioning, also known as IP positioning, refers to determining the location of the network entity corresponding to the IP address in geographic space, and its essence is to obtain the mapping relationship between the IP address of the network entity and the geographic location of the network entity. Because mastering the geographical location of an IP address can provide users with various targeted and personalized efficient services, in recent years, IP positioning technology has gradually attracted the attention of commercial companies, government agencies and even individuals. The geographical location of the address can push advertisements to target groups and provide location-based services (Location Based Service, LBS) and other services; government agencies can push information such as local weather forecasts and natural disaster warnings to different regions through the geographical location of IP addresses Individuals can also judge credit card fraud, deal with spam and improve P2P (Peer to Peer) network performance based on the geographical location of the IP address.

The network entity positioning technology based on network measurement is one of the main ways to obtain high-precision positioning results. However, factors such as network congestion, load balancing, heterogeneous networks, and poor performance of network equipment often cause problems such as network delay expansion and delay jitter, and these factors will affect the accuracy of positioning methods based on delay measurement. Therefore, how to reduce the influence of the above situation on the positioning result, and how to accurately describe the average delay in a certain area is one of the keys to improve the positioning accuracy of network entities based on measurement.

Contents of the invention

The purpose of the present invention is to provide a network entity city-level positioning method based on landmark clustering, which can use the average time delay in the area calculated by the clustering algorithm to realize high-precision network entity positioning.

The present invention adopts following technical scheme:

A network entity city-level positioning method based on landmark clustering, characterized in that: sequentially comprising the following steps:

A: According to the positioning requirements, deploy detection sources in multiple different geographic locations; then enter step B and step D respectively;

B: Measure the round-trip delay between each detection source and all physical landmarks; then establish a delay vector for each physical landmark according to the obtained round-trip delay; then enter step C;

C: Divide all physical landmarks into different groups according to the area, and use the clustering algorithm to cluster the time delay vectors of the physical landmarks in the same area into multiple clusters, then select the cluster with the largest number of clustering results and Calculate the centroid of the cluster, use the calculated centroid as the average delay vector of the region, and finally obtain the average delay vector of each region; then enter step E;

D: Measure the round-trip delay between each detection source and the network entity to be located; then establish a delay vector for the network entity to be located according to the obtained round-trip delay; then enter step E;

E: According to the average delay vector of each area obtained in step C and the delay vector of the network entity to be located obtained in step D, calculate the relative delay vector of the network entity to be located to each area; then enter step F;

F: From the calculated relative delay vectors from the network entity to be located to each area, select the minimum relative delay vector, and the area corresponding to the minimum relative delay vector is the location of the network entity to be located.

In the step B, the detection sources deployed in different geographical locations are used to send ICMP detection packets to all physical landmarks in the network respectively, and the round-trip time delay between each detection source and all physical landmarks is measured, and all detection sources are The round-trip delay with a certain network entity landmark is denoted as d _i1 , d _i2 , d _i3 ,…,d _im ,i=1,2,…,m, where _i represents the _i -th detection source, and are respectively Each landmark establishes a delay vector DV, DV=(d _i1 , d _i2 , d _i3 , L, d _im ), i=1, 2, . . . , m.

In the step C, all the physical landmarks are divided into different groups in units of cities, and the K-means algorithm is used to cluster the time delay vectors of the physical landmarks in the same area into multiple clusters, and then select the cluster The cluster with the largest number in the result and calculate the centroid of the cluster, and the calculated centroid will be used as the average delay vector ADV=(delay ₁ ,delay ₂ ,...,delay _m ) of the area, where K in the K-means algorithm is The empirical threshold value is used to finally obtain the average delay vector of each area.

In the step D, use the detection sources deployed in different geographic locations to send ICMP detection packets to the network entity to be located respectively, and measure the round-trip delay between each detection source and the network entity to be located; then according to the obtained round-trip time Delay establishes a delay vector DV_target for the network entity to be located,

DV_target=(d' _i1 , d' _i2 ,...,d' _im ), i=1, 2,...m; where _i represents the _i -th detection source.

In the step E, according to the average delay vector of each area obtained in step C and the delay vector of the network entity to be located obtained in step D, the relative delay calculation method is used to calculate the distance between the network entity to be located and each The relative delay vector RDV of the region,

The relative delay calculation formula is as follows:

RDV＝(|delay ₁ -d' _i1 |,|delay ₂ -d' _i2 |,...|delay _m -d' _im |), i=1, 2,..., m, i≤m, where _i Indicates the _i -th probe source.

In the step F, the minimum relative delay vector is selected from the calculated relative delay vectors from the network entity to be located to each area, and the city corresponding to the minimum relative delay vector is the city where the network entity to be located is located. That is, the final city-level positioning result of the network entity to be located.

In the present invention, the round-trip time delay RTT between each detection source and all physical landmarks is firstly obtained by using detection sources in different geographic locations, and then a delay vector DV is established for each physical landmark according to the obtained round-trip time delay RTT, and then the entity After the landmarks are divided into regions, clustering algorithm is used to obtain the average delay vector ADV of each region, which greatly improves the accuracy of the average delay of each region. Subsequently, the present invention uses detection sources in different geographical locations to obtain the round-trip delay RTT between each detection source and the network entity to be located, and establishes the delay vector DV_target of the network entity to be located, and then according to the average delay vector ADV and The delay vector DV_target of the network entity to be located is calculated separately to obtain the relative delay vector RDV from the network entity to be located to each area, and finally, the present invention calculates the relative delay vector RDV from the network entity to be located to each area The minimum relative delay vector RDV is selected in , and the area corresponding to the minimum relative delay vector RDV is the location of the network entity to be located. Compared with the network entity positioning technology based on network measurement, the present invention can effectively avoid network congestion, load balancing, heterogeneous network and poor performance of network equipment from affecting network delay expansion and delay jitter, and significantly improve the physical landmark location. The number of excavations, while improving the positioning accuracy of the network entity city level, can provide reliable landmarks for the network city level positioning.

Description of drawings

Fig. 1 is a schematic flow sheet of the present invention;

Fig. 2 is a schematic diagram of the principle of the relative time delay calculation method.

Detailed ways

Below in conjunction with accompanying drawing and embodiment the present invention is described in detail:

As shown in FIG. 1 , the city-level positioning method for network entities based on landmark clustering according to the present invention mainly includes a clustering part and a positioning part. The clustering part includes steps A to C; the positioning part includes steps D to F. The present invention selects city-level reference nodes, and selects multiple regional city-level network entity landmarks under the same ISP (Internet Service Provider) as the reference nodes of the positioning algorithm.

The network entity city-level positioning method based on landmark clustering of the present invention comprises the following steps in turn:

A: According to positioning requirements, the detection sources are deployed in multiple different geographical locations; in this embodiment, m detection sources can be deployed in different geographical locations according to the positioning accuracy requirements.

B: Use detection sources deployed in different geographical locations to send detection messages to all physical landmarks in the network, and measure the round-trip time delay RTT (Round-Trip Time) between each detection source and all physical landmarks; then according to the obtained The round-trip delay RTT establishes a delay vector DV (Delay Vector) for each entity landmark.

In step B, the detection sources deployed in different geographical locations can be used to send ICMP detection packets to all physical landmarks in the network respectively, and the round-trip time delay RTT between each detection source and all physical landmarks can be measured, and all detection sources and The round-trip time delay RTT between certain physical landmarks is d _i1 , d _i2 , d _i3 ,...,d _im , i=1,2,...,m, where i represents the i-th detection source, and each An entity landmark establishes a delay vector DV, DV=(d _i1 ,d _i2 ,d _i3 ,...,d _im ), i=1,2,...m;

C: Divide all physical landmarks into different groups according to the area, and use the clustering algorithm to cluster the delay vector DV of the physical landmarks in the same area into multiple clusters, and then select the cluster with the largest number of clustering results And calculate the centroid of the cluster, use the calculated centroid as the average delay vector ADV (Average Delay Vector) of the region, and obtain the average delay vector ADV of each region.

In the present invention, all physical landmarks are divided into different groups in units of cities, and the K-means algorithm is used to cluster the time-delay vectors DV of physical landmarks in the same city into multiple clusters, and then select clustering results The cluster with the largest number and calculate the centroid of the cluster, and calculate the centroid as the average delay vector ADV=(delay ₁ ,delay ₂ ,...,delay _m ) of the area;

ADV＝Centroid(MaxCluster(cluster ₁ ,...,cluster _k ))

=(delay ₁ ,delay ₂ ,...,delay _m );

Among them, Centroid() is the centroid calculation function, MaxCluster() is the maximum cluster acquisition function, cluster ₁ , ..., cluster _k are the K clusters generated by clustering, delay ₁ , delay ₂ , ..., delay _m are m The time delay vectors measured by the probing sources respectively.

The K-means algorithm is a mature existing algorithm and will not be repeated here. K in the K-means algorithm is an empirical threshold, which can be determined through a large number of experiments and combined with the user's demand for positioning accuracy. The clustering algorithm and the calculation of the centroid also belong to the prior art.

D: Use the detection sources deployed in different geographic locations to send ICMP detection packets to the network entity to be located respectively, and measure the round-trip time delay RTT between each detection source and the network entity to be located; then according to the obtained round-trip time delay RTT is to be determined The bit network entity establishes the delay vector DV_target;

DV_target=GeTargetRTT(probes,target)=(d' _i1 ,d' _i2 ,...,d' _im ), i=1,2,...m;

Among them, GeTargetRTT() is the round-trip time delay function of the target, probes is the detection source, target is the network entity to be located, d' _i1 , d' _i2 ,..., d' _im are the measured and undetermined values of m detection sources respectively is the round-trip delay between bit network entities, _{and i} represents the _i- th probe source.

E: Calculate the relative delay vector RDV (relative Delay Vector);

In the present invention, the relative delay vector RDV from the network entity to be positioned to each area is calculated respectively by using the relative delay calculation method,

The relative delay calculation formula is as follows:

RDV＝(|delay ₁ -d' _i1 |,|delay ₂ -d' _i2 |,...|delay _m -d' _im |), i=1, 2,..., m, i≤m, where _i Indicates the _i -th detection source;

F: From the calculated relative delay vectors from the network entity to be located to each area, select the minimum relative delay vector, and the area corresponding to the minimum relative delay vector is the city where the network entity to be located is located, that is, the location to be located Final city-level localization results for network entities.

The selection method of the minimum relative delay vector belongs to the prior art, and the average number of the relative delay vectors from the network entity to be located to each area can be calculated, and the selection is performed according to the size of the average number.

Claims (6)

1. a kind of network entity City-level localization method based on landmark clustering, it is characterised in that：Include the following steps：

A：According to location requirement, detection source is disposed respectively in multiple and different geographical locations；Then step B and step D are respectively enterd；

B：Measure the round-trip delay between each detection source and all entity terrestrial references；Then it is according to obtained round-trip delay Each entity terrestrial reference setup delay vector；Subsequently into step C；

C：By all entity terrestrial references according to region division be different groups, and using clustering algorithm will be in the same area Physically target time delay vector clusters are multiple clusters, then choose the cluster that number is most in cluster result and the matter for calculating the cluster The heart will be calculated barycenter as the average delay in region vector, finally obtain the average delay vector of each region；Then Enter step E；

D：Measure the round-trip delay between each detection source and network entity to be positioned；Then it is according to obtained round-trip delay Network entity setup delay vector to be positioned；Subsequently into step E；

E：According to the network entity to be positioned obtained in the average delay vector sum step D of each region obtained in step C Time delay vector, the relative time delay for calculating network entity to be positioned to each region are vectorial；Subsequently into step F；

F：In the relative time delay vector of the network entity to be positioned being calculated to each region, choose minimum relative time delay to It measures, the region corresponding to minimum relative time delay vector is network entity position to be positioned.

2. the network entity City-level localization method according to claim 1 based on landmark clustering, it is characterised in that：It is described Step B in, using the detection source of diverse geographic location deployment, into network, all entity terrestrial reference sends icmp probe respectively Data packet measures the round-trip delay between each detection source and all entity terrestrial references, by all detection sources and each net Round-trip delay between network entity terrestrial reference is denoted as d_i1,d_i2,d_i3,…,d_im, i=1,2 ..., m, wherein i i-th of detection source of expression, And respectively each terrestrial reference setup delay vector DV, DV=(d_i1,d_i2,d_i3,L,d_im), i=1,2 ..., m.

3. the network entity City-level localization method according to claim 2 based on landmark clustering, it is characterised in that：It is described Step C in, be that unit is divided into different groups by all cities that are physically marked with, will be in same using K-means algorithms Physically target time delay vector clusters in one region are multiple clusters, then choose number is most in cluster result cluster and calculating Average delay vector ADV=(delay of the barycenter as the region will be calculated in the barycenter of the cluster₁,delay₂,…, delay_m), wherein the K in K-means algorithms is empirical thresholds value, delay₁、delay₂、……、delay_mFor m detection source The time delay vector measured respectively finally obtains the average delay vector of each region.

4. the network entity City-level localization method according to claim 3 based on landmark clustering, it is characterised in that：It is described Step D in, using diverse geographic location deployment detection source respectively to network entity to be positioned send icmp probe data packet, Measure the round-trip delay between each detection source and network entity to be positioned；Then it is to be positioned according to obtained round-trip delay Network entity setup delay vector DV_target,

DV_target=(d'_i1,d'_i2,…,d'_im), i=1,2 ... m；Wherein i indicates i-th of detection source.

5. the network entity City-level localization method according to claim 4 based on landmark clustering, it is characterised in that：It is described Step E in, it is real according to the network to be positioned that is obtained in the average delay vector sum step D of each region obtained in step C Body time delay vector, using relative time delay computational methods calculate separately network entity to be positioned to each region relative time delay to RDV is measured,

Relative time delay calculation formula is as follows：

RDV=(| delay₁-d'_i1|,|delay₂-d'_i2|,……|delay_m-d'_im|), i=1,2 ... ..., m, i≤m, wherein I indicates i-th of detection source.

6. the network entity City-level localization method according to claim 5 based on landmark clustering, it is characterised in that：It is described Step F in, when choosing minimum opposite in from the network entity to be positioned being calculated to the relative time delay vector in each region Prolong vector, the city corresponding to minimum relative time delay vector is city where network entity to be positioned, i.e., network to be positioned is real The final City-level positioning result of body.