JP4387296B2 - Network design support apparatus and program - Google Patents

Description

  The present invention relates to a method for connecting a plurality of communication devices in a communication network. As a network targeted by the present invention, for example, a mobile wireless communication device that does not have a fixed network such as a sensor network or a base station that arranges a large number of communication devices within a certain range and connects them wirelessly or by wire An ad hoc network that constructs a network by mutual relaying between them, or a network that connects ordinary fixed communication devices wirelessly or by wire.

  In designing a communication network, a network model in which communication devices are nodes and communication devices are links is generally used.

  As a technique for designing a route of a node using a network model, there is a technique described in Japanese Patent Laid-Open No. 2002-118597. In Japanese Patent Laid-Open No. 2002-118597, node path design is performed in consideration of a plurality of communication characteristics of a link (cost, delay code, etc. based on a level value effective band).

  As a method for evaluating the connectivity of nodes in a network, B.I. Krishnamachari, D.H. Estrin, S.M. There is Wicker "Modeling Data-Centric Routing in Wireless Sensor Networks" (IEEE INFOCOM 2002). Further, “Design of Survivable Networks” (Springer-Verlag, Inc., Nature Notes in Materials 1531), which is a method for explaining a general method as a background, is described. However, there was no network design method based on a simple model that simulated a network with a single key parameter. On the other hand, Yasuari Higuchi published “Percolation” Yuseisha as an explanation of a mathematical model that expresses network properties using link connection probabilities. The present invention proposes a method for securing the connectivity of a communication network by applying such a mathematical model.

  FIG. 1 is a diagram illustrating an example of a network topology model. In the figure, 10 is a network model, 1 is a node indicating a communication apparatus, 1S is a node S, and 1T is a node T. 2 indicates a link (displayed by a solid line) indicating a wireless or wired communication path, and a link candidate 2C (displayed by a dotted line) indicates a location where the link 2 can be set.

FIG. 22 is a diagram showing an operation flow of the conventional method. In the figure, KB01 indicates a topology model setting, KB02 indicates a random model trial, and KB05 indicates a high connection condition output. In the topology model setting of KB01, node 1, link candidate 2C, and source node 1S are assigned (FIG. 1). In the random model trial of KB02, an appropriate link is randomly selected from the link candidates 2S shown in FIG. FIG. 4 shows the procedure of the random model trial. In the random model trial, since a large number of random models are set and the trial is performed, the amount of computer processing increases. Based on this result, KB05 outputs which model is a high connection condition, that is, a random model with high connectivity between nodes among a plurality of random models tried by a random model trial.
JP 2002-118597 A B. Krishnamachari, D.H. Estrin, S.M. "Modelling Data-Centric Routing in Wireless Sensor Networks" by Wicker (IEEE INFOCOM 2002) "Design of Survivable Networks" by Mechtil Stoer (Springer-Verlag, Inc., Texture Notes in Mathematicas 1531) Published by Yasunari Higuchi, “Percolation”, Yuseisha, June 25, 1992, p. 8-17

  However, in the above method, it is necessary to repeat a random model trial (FIG. 22-KB02, FIG. 4) having a large processing amount for each case of each network, and thus there is a problem that the entire processing amount becomes large. It was. In particular, when the number of nodes 1 and the number of link candidates 2C in the network model 10 are large, the amount of processing becomes very large.

  The main object of the present invention is to solve the above problems, and to output high connection conditions by a simple process.

The network design support apparatus according to the present invention is:
A topology model setting unit for setting a topology model composed of a plurality of nodes and a plurality of link candidates;
It is a network model when it is assumed that each of a plurality of nodes included in the topology model is connected to another node that may be connected with a predetermined connection probability, and at least one of the plurality of link candidates is A network model generation unit that generates a network model in which a link is set between at least two nodes and is enabled for a plurality of connection probabilities;
For each network model generated for a plurality of connection probabilities by the network model generation unit, a connection determination unit that analyzes the network model and determines the value of the number of connection nodes connected via a link in the network model When,
Corresponding to the order of the magnitude relationship of the plurality of connection probabilities, the change state of the value of the plurality of connection nodes determined by the connection determination unit is analyzed, and based on the analysis result of the change state, the network design And a threshold connection probability setting unit that sets a threshold connection probability that serves as a threshold when the design condition is evaluated.

  According to the present invention, since the network design condition can be evaluated based on the threshold connection probability by setting the threshold connection probability, the amount of computer processing for the design condition evaluation can be suppressed. .

Embodiment 1 FIG.
First, the outline of the present embodiment will be described in comparison with the prior art. FIG. 1 is a network topology model diagram for illustrating the goals of the present embodiment.

  In the figure, 10 is a network model, 1 is a node indicating a communication device, and 2 is a link indicating a wireless or wired communication path. In the node 1, a subscript may be used to indicate a specific node, and 1S indicates the node S and 1T indicates the node T. A link candidate 2C shown by a dotted line indicates a place where the link 2 can be set.

  The goal of this embodiment is to determine the ratio of the node 1 connected to a certain node 1S and the link 2 with respect to the total number of nodes when the link candidate 2C connecting the node 1 and the node is given, This is to be a certain value or more.

  In FIG. 1, there are 10 nodes 1 and 23 link candidates 2C connecting the nodes 1. (Including node 1S and link 2). In this case, the number of nodes connected to the node 1S is three represented by 1T, and the ratio to the total number of nodes is 3/10 = 0.3. Here, if the node 1S itself is included, the ratio of the number of connected nodes is 4/10 = 0.4. Since the present invention is generally intended for a case where the number of nodes is large, the ratio when the node is included is substantially equal to the ratio when the node is not included.

  In order to widely inform other nodes 1 of the information transmitted from the node 1S, an appropriate link is selected from the link candidates 2C to make it an effective link 2. In this embodiment, it is possible to efficiently discover how many nodes 1 and nodes 1S can be connected by selecting the link 2 in a limited communication band, communication device, and the like. Is the goal.

  FIG. 2 is a diagram showing an operation flow of the present embodiment. In the present embodiment, the operation flow is divided into a P0 determination stage (KB01 to KB03) and a condition evaluation stage (KB04, KB05).

  KB01 is a topology model setting, KB02 is a random model trial, KB03 is critical probability P0 determination, KB04 is connectivity determination based on critical probability P0, and KB05 is a high connection condition output.

  In the P0 determination stage (KB01 to KB03), in setting the topology model of KB01, the node 1, the link candidate 2C, and the transmission node 1S are assigned, and for example, the topology model shown in FIG. 1 is set (topology model setting step).

  In the KB02 random model trial, an appropriate link is randomly selected from the link candidates 2S in FIG. 1 to set a valid network 2 and try multiple times (network model generation step). FIG. 4 shows the procedure of the random model trial. In the random model trial, since a large number of random models are set and the trial is performed, the amount of computer processing increases.

  In determining the critical probability P0 of KB03, the critical probability P0 is determined based on a random model trial (threshold connection probability setting step). Details of the determination of the critical probability P0 will be described later. The critical probability P0 is an example of a threshold connection probability.

  Next, in the condition evaluation stage (KB04, KB05), connectivity determination based on the critical probability P0 of KB04 is performed (design condition input step, target network connection probability derivation step, design condition evaluation step). FIG. 5 shows the procedure for determining connectivity based on the critical probability P0 of KB04. In step ST01, the probability P of each case is compared with the critical probability P0. If P is greater than P0, it is determined that the connectivity is high (step ST02), and if P is less than P0, the connectivity is determined to be low. (Step ST03). Based on this result, KB05 outputs a high connection condition.

  The conventional method shown in FIG. 22 has fewer processing steps than the operation flow of the present embodiment shown in FIG. However, the random model trial KB02 has a very large processing amount as shown in FIG. In the conventional method, it is necessary to perform a random model trial for each individual case, which increases the processing amount. On the other hand, in the method of the present embodiment shown in FIG. 2, once the random model trial KB02 is performed after the topology model setting KB01, the result is represented by the value of the critical probability P0 which is the threshold value of the key parameter ( (KB03), in each case, the connectivity can be determined only by comparing the magnitude with the threshold value P0 of the key parameter P (KB04, FIG. 5). By representing the network model connectivity, that is, the characteristic obtained as a result of trial and error, that is, the ratio of the node 1 connected to the node 1S, by a key parameter called probability P, trial and error. Is a feature of the method of the present embodiment that connectivity can be determined only by a simple size comparison with the threshold value P0 at the time of setting a topology model and at the time of evaluating individual network cases.

  Next, FIG. 3 shows a configuration example of a network design support apparatus that executes each step shown in FIG.

  The topology model setting unit 101 is an element that executes the topology model setting KB01 of FIG. 2, and sets, for example, the topology model shown in FIG.

  The random model trial unit 102 is an element that executes the random model trial KB02 in FIG. 2, and it is assumed that each of a plurality of nodes included in the topology model is connected to other nodes that may be connected with a predetermined connection probability. A network model in which at least one of a plurality of link candidates is valid and a link is set between at least two nodes is generated for a plurality of connection probabilities. Specific contents of the random model trial will be described later. The random model trial unit 102 is an example of a network model generation unit.

  The P0 determination unit 103 is an element that executes the critical probability P0 determination KB03 of FIG. The P0 determination unit 103 includes a connection determination unit 1031 and a P0 extraction unit (threshold connection probability setting unit) 1032. The connection determination unit 1031 analyzes the network model for each network model generated for a plurality of connection probabilities by the random model trial unit 102, and the value of the number of connection nodes connected via a link in the network model Determine. The connection determination unit 1031 may determine the number of nodes connected to the node 1S via a link, or a ratio value relative to the total number of nodes connected to the node 1S via a link. Also good. The P0 extraction unit 1032 analyzes the change state of the values of the plurality of connection nodes determined by the connection determination unit 1031 in correspondence with the order of the relationship of the plurality of connection probabilities, and based on the analysis result of the change state Thus, P0 is extracted as a threshold for evaluating the design conditions of the network design. Details of the processes of the connection determination unit 1031 and the P0 extraction unit 1032 will be described later.

  The P0 storage unit 104 stores P0 determined by the P0 determination unit 103.

  The input unit 105 inputs the design conditions of the target network that is the target of the connectivity determination KB04 by P0 in FIG. The input unit 105 is an example of a design condition input unit.

  The target network P deriving unit 106 derives the connection probability P of the target network based on the design conditions of the target network input by the input unit 105. The target network P deriving unit 106 is an example of a target network connection probability deriving unit.

  The design condition evaluation unit 107 is an element that executes the connectivity determination KB04 based on P0 in FIG. 2, and the connection probability between P0 stored in the P0 storage unit 104 and the target network P derived by the target network P deriving unit 106 P is compared, and the design conditions of the target network are evaluated based on the comparison result.

  The output unit 108 is an element that executes the high connection condition output KB05 of FIG. 2, and outputs the evaluation result of the design condition evaluation unit 107.

  Next, a specific method of the present embodiment will be described. 6 and 7 show the topology model, which corresponds to FIG. 6 and 7, elements having the same numbers as those in FIG. 1 have the same functions. However, in the models of FIGS. 6 and 7, the nodes 1 are regularly arranged in a grid pattern. A lattice 11 is a frame for arranging nodes 1. It is assumed that the node 1 is arranged at the intersection of the lattice 11 and the illustration of the node 1 is omitted when there is no link connection or the like as shown in FIG. Further, unlike the case of FIG. 1, each node 1 can be connected to only four nodes 1 on the top, bottom, left and right. FIG. 7 shows a node 1S, a node candidate 1SC that can be connected to the node 1S, and a connection link candidate 2SC at that time. The topology models in FIGS. 6 and 7 simulate an ad hoc network or a sensor network that is wirelessly connected. In wireless connection, since the reachable range of radio from a certain node 1S is limited, the link candidate 2C is effective only with nodes around the node 1S. The nodes 1 may be randomly arranged, but even if they are quantized and regularly arranged, the generality is not greatly impaired, so the model of FIGS. 6-7 is used.

  FIG. 8 shows an example of the state of the nodes connected to the node 1S in the network topology models of FIGS. In the figure, a node connected to the node 1S (black circle) is indicated by a node 1T (white circle), and a connection link is indicated by a link 2S (solid line).

  Examples of the results of random model trials (KB02 of FIG. 2, FIG. 4) in the network topology model of FIGS. 6 and 7 are shown in FIGS. 9 to 11, the description of the node 1 is omitted. 9 shows a case where the connection probability P = 0.1 which is a key parameter, FIG. 10 shows a case where the connection probability P = 0.5 which is a key parameter, and FIG. 11 shows a case where the connection probability P = 0.9 which is a key parameter. Indicates. Here, the connection probability refers to the probability that a certain node can be connected when trying to connect to a node that may be connected. For example, when the connection probability P = 0.1, a certain node can be connected. This is a case where a connection can be made only once when 10 attempts are made to connect with a secure node. FIG. 9 shows a network when it is assumed that each of a plurality of nodes included in the topology model of FIG. 6 is connected to other nodes that can be connected (up / down / left / right nodes) with a connection probability P = 0.1. FIG. 10 shows a case where it is assumed that each of a plurality of nodes included in the topology model of FIG. 6 is connected to other nodes that can be connected (upper and lower left and right nodes) with a connection probability P = 0.5. FIG. 11 shows that each of a plurality of nodes included in the topology model of FIG. 6 is connected to other nodes (upper and lower left and right nodes) that may be connected with a connection probability P = 0.9. The network model is shown. 9 to 11, each side of the lattice 11 that is the link candidate 2 </ b> C is validated with a probability P. It can be seen that as the connection probability P increases, the proportion of nodes connected to the node 1S increases. In this way, the random model trial unit 102 tries to generate a network model for a plurality of connection probabilities.

  Next, how to obtain the critical probability P0 will be described. In the above description, the random model trial KB02 in FIG. 2 performs the random model trial shown in FIG. 4, and the critical probability P0 is determined by the critical probability P0 determination KB03 in FIG. Details of these procedures are shown in FIGS.

  The details of the procedure for determining the connection between the node S and other nodes in step ST71 in FIG. 12 are the creation of information on the nodes connected to the nodes S in steps ST81, ST83, ST85, and ST87 in FIG. FIG. 15 shows in detail the procedure for determining the connection between node i and node j in step ST91 of FIGS.

  When determining the critical probability P0, first, in step ST71 of FIG. 12, the connection determination unit 1031 determines the connection between the node S and another node. This connection determination between the node S and another node is the value of the number of connected nodes connected via a link in the network model (the number of connected nodes or the total number of all nodes) for each network model generated by the random model trial. The ratio value of the connection node with respect to (). When the value of the number of connected nodes is determined for a certain network model, the result is written in the connection status between the node S of the data memory DM72 and another node.

  Next, in step ST73, it is determined whether or not the trial has been performed for several values of the connection probability P. If yes, the process proceeds to step ST75, and if no, the process proceeds to step ST74. In step ST74, the next candidate for the connection probability P is given, and step ST71 is repeated. In the example of FIGS. 9-11, the number of connected nodes is determined for three types of network models, P = 0.1 in FIG. 9, P = 0.5 in FIG. 10, and P = 0.9 in FIG. Thus, in this example, the process of step ST711 is performed three times.

  Next, proceeding to step ST75, the P0 extraction unit 1032 refers to the connection status between the node S of the data memory DM72 and another node, and sets the value of P at which the connection status changes greatly before and after to P0. A curve 6 in FIG. 16 schematically represents the relationship between the connection probability P and the connection status (value of the number of connected nodes). In the figure, P0 is set around P where the connection status changes greatly between before and after. That is, the P0 extraction unit 1032 analyzes the change state of the value of the plurality of connection nodes determined by the connection determination unit 1031 in correspondence with the order of the relationship of the plurality of connection probabilities, and the value of the number of connection nodes Is extracted, and a threshold connection probability P0 is set based on the extracted connection probability.

  Next, a connection determination procedure between the node S and another node in FIG. 13 will be described. First, in step ST81, information on a node directly connected to the node S is created and written in the data memory DM82.

  Next, in step ST83, information on the node connected to the node S in one relay is created and written to the data memory DM84. This is sequentially repeated in steps ST85 to ST89, and when all the nodes are covered (step ST89), the process ends.

  Next, a procedure for creating information of a node connected to the node S in the relay R times in FIG. 14 will be described. First, in step ST91, connection determination between node i and node j is performed (whether or not they are connected by a link), and the result is written in the data memory DM92. In step ST93, it is determined whether or not all nodes in the network have been determined as node j. If yes, the process proceeds to step ST95. If no, the next candidate for node j is assigned in step ST94 and step ST91 is repeated. In step ST95, it is determined whether all nodes connected to the node S by relay R-1 times have been determined as the node i. If yes, the process ends. If no, the next candidate of the node i is assigned in step ST96, and step ST91. repeat.

  Next, the connection determination procedure between node i and node j in FIG. 15 will be described. In step ST101, the data memory DM102 is referred to determine the connection status between the node i and the node j (whether or not they are connected by a link), and the result is written in the data memory DM103. A data memory DM102 that holds connection information is the link data DM10 when the random model is tried in FIG.

  In this way, the connection determination unit 1031 includes, for each network model generated by the random model trial unit 102 for a plurality of connection probabilities P (= 0.1, 0.5, 0.9), in the network model. Designate a reference node 1S as a reference, sequentially increase the number of hops from the reference node 1S, sequentially detect nodes connected by links, and thereby connect to the reference node 1S via at least one or more links The detected node is detected, and the value of the number of connected nodes in the network model is determined.

  Through the processes shown in FIGS. 12 to 16, the critical probability P <b> 0 that is a threshold is set, and this critical probability P <b> 0 is stored in the P <b> 0 storage unit 104.

  Next, the condition evaluation stage (KB04 and KB05 in FIG. 2), which is a process for evaluating the design conditions of the network design, will be described.

  First, in order to perform the connectivity determination KB04 based on P0, it is necessary to obtain the connection probability P of the target network to be evaluated (hereinafter referred to as the target network connection probability P). First, how to determine the target network connection probability P will be described. Here, a case where the probability P is lowered based on the distance D between nodes will be described. FIG. 17 is a diagram schematically showing the periphery of the node 1S, and the range of the distance D from the node S is a range that can be connected to the node S with the connection probability P. The connection probability P decreases as the distance D increases and the distance from the node S decreases. P = 0.5 in the range 3A, P = 0.2 in the range 3B, and P = 0.1 in the range 3C. FIG. 18 is a graph schematically showing the relationship 4 between the distance D and the probability P. When the distance D from the node S is 0, the probability P is 1 and the connection is always made. However, as the distance D increases, the probability P decreases, and at D0, P becomes almost zero and hardly connected.

Next, how to obtain the relationship of FIG. 18 will be described. FIG. 19 shows the relation 5 in which the relative electric field strength E (dB) decreases as the distance D increases, and is drawn based on the following relational expression that is widely used in general. (For example, Yoshihisa Okumura and Masaaki Shinji “Basics of Mobile Communications” edited by the Institute of Electronics, Information and Communication Engineers)
E = −20 × log (D) (Formula 1)
However, since the logarithm (log) when the distance D = 0 m cannot be taken, the distance D = 0 indicates a case where the distance is very small. In FIG. 19, when the connection probability P is 1 when the distance D = 0 m and the relative electric field strength is 0 dB, and the connection probability P is zero when the distance D = 100 m and the relative electric field strength is −40 dB, in FIG. Relationship 4 with 100m can be obtained. This is expressed as follows.

P = (| E (D0) | + E) / | E (D0) | (Formula 2)
= (40-20 * log (D)) / 40
= 1- (log (D)) / 2
As described above, in order to obtain the target network connection probability P, the input unit 105 inputs conditions such as the distance D and the relative electric field strength, which are design conditions of the target network, and based on the input design conditions, the target network P derivation unit 106 derives the target network connection probability P based on Equation 2 above. Then, as shown in FIG. 5, the design condition evaluation unit 107 compares the derived target network connection probability P with the threshold value P0 stored in the P0 storage unit 104, and the target network connection probability P is greater than the threshold value P0. Is also large, it is evaluated that the design condition of the target network is a design condition with a high connection probability. Thereby, the network designer can determine whether design conditions, such as distance, are appropriate.

  In the above description, the case where the node S serving as a node design reference is fixed has been described, but the same method can be applied even if the node S is not fixed and generalized.

  In the above description, when the probability P is obtained from the distance D, the expression 1 of the relative electric field strength E is used. However, the probability P is calculated based on another relational expression of the electric field strength, loss, or another attribute. It may be set.

  Thus, in this embodiment, in an ad hoc network or a sensor network, a connection probability between a certain node and another node that may be connected to the node is set to a constant value P, and this connection probability P is a key. A network model is created as a parameter, and the connection probability of nodes in the network becomes dense when this connection probability P exceeds a certain value, and the network becomes sparse when it is less than a certain value (assuming) Do the design. In a topology in which node candidates are arranged in a grid pattern and a certain node may be connected to the upper, lower, left, and right nodes, and P is a key parameter, and P exceeds a certain value The network is designed by using (assuming) the property that the entire network is closely connected and becomes sparse when it is below a certain value. A connection probability P between a certain node and another node is set, and the probability P is set so as to decrease as the distance D between the nodes increases. At this time, the relationship between the distance D and the connection probability P is obtained by using a known relationship such as an electrolytic strength and a radio wave loss indicating that the strength of the radio wave that arrives decreases as the distance D increases. That is, based on an existing relationship such as distance D and electric field strength, a relationship is derived in which probability P is 1 when distance D is zero and probability P is zero when distance D is a certain value D0.

  According to the present embodiment, by characterizing the network model using the connection probability P between nodes as a key parameter, it is possible to output a high connection condition by a simple process.

  That is, in the past, each time the design conditions of the network design were evaluated, a plurality of random model trials were performed and high connection conditions were output, so the computer processing amount increased. If the critical probability P0 is set by performing a model trial, the design condition can be evaluated simply by comparing the target network connection probability P and the critical probability P0. Can be suppressed.

  The network design support apparatus according to the present embodiment can be used when estimating connectivity between communication apparatuses in planning and design of a network connecting many communication apparatuses such as a sensor network and an ad hoc network. Is possible.

Embodiment 2. FIG.
In the first embodiment, the model shown in FIGS. 6 and 7, that is, the model in which the nodes 1 are regularly arranged according to the lattice 11 is used as a diagram corresponding to the topology model FIG.

  As shown in FIG. 20, the same method can be used in a model in which nodes 1 are randomly arranged and connected to all other nodes with a probability P. The connectivity in this case is shown in FIG. This model is suitable for modeling a wired connection network, not a wireless connection, because the connection is made with a certain probability P regardless of distance.

  Thus, in this embodiment, node candidates are randomly arranged, and a certain node may be connected to all other nodes. Using these connection probabilities P as key parameters, the network design is utilized (assuming) that the entire network is densely connected when P exceeds a certain value, and sparse when it is less than a certain value. It is carried out. Thus, by characterizing the network model using the connection probability P between nodes as a key parameter, it is possible to output high connection conditions by a simple process.

  In each of the embodiments described above, the network design support apparatus 100 can be realized by a computer.

  Although not shown, the network design support apparatus 100 includes a CPU (Central Processing Unit) that executes a program.

  For example, the CPU is connected to a ROM (Read Only Memory), a RAM (Random Access Memory), a communication board, a display device, a K / B (keyboard), a mouse, an FDD (Flexible Disk Drive), and a CDD (Compact Disc) via a bus. Drive), magnetic disk device, optical disk device, printer device, scanner device, and the like.

  The RAM is an example of a volatile memory. ROM, FDD, CDD, magnetic disk device, and optical disk device are examples of nonvolatile memory. These are examples of a storage device or a storage unit.

  The data and information handled by the network design support apparatus 100 of each embodiment described above are stored in a storage device or a storage unit, and are recorded and read out by each unit of the network design support apparatus 100.

  The communication board is connected to a WAN (Wide Area Network) such as a LAN, the Internet, or ISDN.

  The magnetic disk device stores an operating system (OS), a window system, a program group, and a file group (database).

  The program group is executed by a CPU, OS, and window system.

  Each part of the network design support apparatus 100 may be configured by a program that can be operated partly or entirely by a computer. Alternatively, it may be realized by firmware stored in the ROM. Alternatively, it may be implemented by software, hardware, or a combination of software, hardware, and firmware.

  The program group stores a program that causes the CPU to execute the processing described as “˜unit” in the description of the embodiment. These programs are created by computer languages, such as C language, HTML, SGML, and XML, for example.

  The program is stored in another recording medium such as a magnetic disk device, FD (Flexible Disk), optical disk, CD (compact disk), MD (mini disk), DVD (Digital Versatile Disk), and read by the CPU. And executed.

3 is a network topology model diagram according to Embodiments 1 and 2. FIG. 6 is a diagram showing an example of an operation flow according to Embodiments 1 and 2. FIG. 3 is a diagram illustrating a configuration example of a network design support apparatus according to Embodiments 1 and 2. FIG. It is a figure which shows the procedure of a random model trial. It is a figure which shows the procedure of connectivity judgment by the critical probability P0 which concerns on Embodiment 1 and 2. FIG. 2 is a diagram showing a network topology model according to Embodiment 1. FIG. 2 is a diagram showing a network topology model according to Embodiment 1. FIG. FIG. 8 is a diagram illustrating an example of a state of a node connected to a node 1S in the network topology model of FIGS. 6 and 7; FIG. 8 is a diagram illustrating an example of a result of a random model trial performed with a connection probability P = 0.1 in the network topology model of FIGS. 6 and 7. FIG. 8 is a diagram illustrating an example of a result of performing a random model trial with a connection probability P = 0.5 in the network topology model of FIGS. 6 and 7. FIG. 8 is a diagram illustrating an example of a result of a random model trial with a connection probability P = 0.9 in the network topology model of FIGS. 6 and 7. It is a figure which shows the procedure which derives | leads-out the critical probability P0 which concerns on Embodiment 1 and 2. FIG. FIG. 13 is a diagram detailing a connection determination procedure between the node S of FIG. 12 and another node. It is the figure which detailed the procedure which produces the information of the node connected with the node S of FIG. 13 by the relay R times. It is the figure which explained in detail the connection determination procedure of the node i of FIG. 14, and the node j. It is the figure which represented typically the relationship between the connection probability P and a connection condition. It is the figure which represented the periphery of the node 1S typically, and is a figure which shows the range which can be connected with the distance D from the node 1S, and the connection probability P. It is the graph which showed typically the relation between distance D and probability P. 5 is a graph showing the relationship between distance D and electric field strength E. FIG. 10 is a diagram illustrating a random arrangement of nodes according to the second embodiment. 6 is a diagram illustrating an example of connectivity according to Embodiment 2. FIG. It is a figure which shows the operation | movement flow of the conventional method.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 100 Network design support apparatus, 101 Topology model setting part, 102 Random model trial part, 103 P0 determination part, 104 P0 memory | storage part, 105 Input part, 106 Target network P derivation part, 107 Design condition evaluation part, 108 Output part, 1031 Connection determination unit, 1032 P0 extraction unit.

Claims (7)

A topology model setting unit for setting a topology model composed of a plurality of nodes and a plurality of link candidates;
It is a network model when it is assumed that each of a plurality of nodes included in the topology model is connected to another node that may be connected with a predetermined connection probability, and at least one of the plurality of link candidates is A network model generation unit that generates a network model in which a link is set between at least two nodes and is enabled for a plurality of connection probabilities;
For each network model generated for a plurality of connection probabilities by the network model generation unit, a connection determination unit that analyzes the network model and determines the value of the number of connection nodes connected via a link in the network model When,
Corresponding to the order of the magnitude relationship of the plurality of connection probabilities, the change state of the value of the plurality of connection nodes determined by the connection determination unit is analyzed, and based on the analysis result of the change state, the network design A network design support apparatus, comprising: a threshold connection probability setting unit configured to set a threshold connection probability that serves as a threshold when a design condition is evaluated. The network design support device further includes:
A design condition input unit for inputting design conditions of a target network to be evaluated for design conditions;
A target network connection probability deriving unit for deriving a connection probability of the target network based on the design conditions input by the design condition input unit;
A design that compares the connection probability of the target network derived by the target network connection probability deriving unit with the threshold connection probability set by the threshold connection probability setting unit, and evaluates the design conditions of the target network based on the comparison result The network design support apparatus according to claim 1, further comprising a condition evaluation unit. The design condition evaluation unit
When the connection probability of the target network derived by the target network connection probability deriving unit is higher than the threshold connection probability set by the threshold connection probability setting unit, the design condition of the target network is a design condition of high connection probability The network design support apparatus according to claim 2, wherein: The network model generation unit
As the connection probability increases, the value of the number of connected nodes increases, and when a specific connection probability is exceeded, a network model having a characteristic that the value of the number of connected nodes greatly increases is generated.
The threshold connection probability setting unit includes:
Corresponding to the order of the magnitude relationship of the plurality of connection probabilities, the change status of the value of the plurality of connection nodes determined by the connection determination unit is analyzed, and based on the analysis result of the change status, the number of connection nodes The network design support apparatus according to claim 1, wherein a connection probability that greatly increases the value of is extracted, and a threshold connection probability is set based on the extracted connection probability. The connection determination unit
For each network model generated for a plurality of connection probabilities by the network model generation unit, a reference node serving as a reference is designated in the network model, and the number of hops from the reference node is sequentially increased to at least one of the reference node. The network design support apparatus according to claim 1, wherein a node connected via two or more links is detected and a value of the number of connected nodes is determined. Topology model setting processing for setting a topology model composed of a plurality of nodes and a plurality of link candidates;
It is a network model when it is assumed that each of a plurality of nodes included in the topology model is connected to another node that may be connected with a predetermined connection probability, and at least one of the plurality of link candidates is A network model generation process for generating a network model in which a link is set between at least two nodes that is enabled and for a plurality of connection probabilities;
For each network model generated for a plurality of connection probabilities by the network model generation process, the network model is analyzed, and a connection determination process for determining the value of the number of connection nodes connected via a link in the network model When,
Corresponding to the order of magnitude relationship of the plurality of connection probabilities, the change status of the value of the plurality of connection nodes determined by the connection determination processing is analyzed, and based on the analysis result of the change status, the network design A program that causes a computer to execute threshold connection probability setting processing for setting a threshold connection probability that becomes a threshold value when evaluating design conditions. The program further includes:
Design condition input processing for inputting design conditions of a target network to be evaluated for design conditions;
A target network connection probability derivation process for deriving a connection probability of the target network based on the design conditions input by the design condition input process;
A design for comparing the connection probability of the target network derived by the target network connection probability deriving process with the threshold connection probability set by the threshold connection probability setting process and evaluating the design conditions of the target network based on the comparison result The program according to claim 6 , which causes a computer to execute condition evaluation processing.

Images