JP4877989B2 - Network design method, network design support apparatus, and network design support program - Google Patents

Description

  The present invention relates to a method for designing a communication network in which a plurality of communication devices are arranged and wirelessly or wiredly connected to each other, and particularly includes a communication device that interferes with desired communication in the communication network. In particular, the present invention relates to a network design method, a network design support apparatus and a program for realizing the network design method.

  In designing a communication network, a network model in which communication devices are nodes and communication devices are links is generally used. At this time, as a method for evaluating the connectivity of the nodes in the network, for example, there is the following Non-Patent Document 1. Further, there is the following Non-Patent Document 2 as an explanation of a general method as a background of communication network design. Non-patent document 3 below describes a mathematical model that expresses network properties using link connection probabilities.

  Moreover, in the sensor network or ad hoc network by many communication apparatuses, there exist the following patent document 1 and the following patent document 2 as a network design method which considered interference or interference. Note that these Patent Documents 1 and 2 do not specify a network design based on a simple model that simulates a network in which interference exists with a small number of key parameters. On the other hand, Non-Patent Document 4 below describes a mathematical model that expresses the nature of a network in consideration of interference from multiple nodes. Here, the disturbing node is not considered.

  Here, an example of a conventional network design method will be described. Conventional network design is performed, for example, in three steps: “topology model setting”, “random model trial”, and “high connection condition output”. In “topology model setting”, a plurality of nodes indicating communication devices, link candidates indicating communication paths, and a transmission node among the nodes are set. In the “random model trial”, an appropriate link is randomly selected from link candidates and a model in which the link is used as an effective link is set, and a trial is performed a plurality of times in a predetermined procedure. In the “random model trial”, trials are performed by setting a large number of random models. “High connection condition output” outputs a high connection condition based on the trial result.

JP 2000-315974 A JP 2001-156787 A B.Krishnamachari, D.Estrin, S.Wicker “Modeling Data-Centric Routing in Wireless Sensor Networks” (IEEE INFOCOM 2002) “Design of Survivable Networks” by Mechthild Stoer (Springer-Verlag Lecture Notes in Mathematics 1531) Published by Yasunari Higuchi "Percolation" O.Dousse, F.Baccelli, P.Thiran, “Impact of interferences on connectivity in ad hoc networks,” IEEE / ACM Transactions on networking, vol.13, no.2, April 2005, pp. 425-436

  However, in the above conventional network design method, it is necessary to repeatedly execute “topology model setting” and “random model trial” with a large processing amount for each case of each network, so that the entire processing amount increases. There was a problem. In particular, in the network model, when the number of nodes and the number of link candidates tend to increase, the processing amount increases with the increase.

  The present invention has been made in view of the above, and in a communication network such as a sensor network or an ad hoc network by a large number of communication devices, a network design method and a network design capable of realizing output of high connection conditions by simple processing An object is to obtain a support device and a program.

  In order to solve the above-described problems and achieve the object, a network design method according to the present invention sets a topology model configured from a plurality of nodes indicating communication devices and a plurality of link candidates indicating communication paths. And a random model trial step in which an appropriate link is randomly selected from link candidates to generate a network model using the link as a valid link, and a plurality of trials are performed in a predetermined procedure. A network setting method for outputting a high connection condition based on an execution result, the network connection based on the trial result in a network model including a disturbing node that adversely affects communication by a necessary node for performing desired communication Criticality of the required node density M to determine performance (low connection and high connection) A critical value determining step for determining a critical value of the interference load factor Kk, a critical value of the disturbing node density Mb (function of M), and a critical value of the disturbing load factor Kb; A connectivity determination step of determining network connectivity using each of the critical values, with the load factor Kk of the node, the density Mb of the disturbing node, and the disturbing load factor Kb as key parameters, and the random model trial The step and the critical value determining step are performed only at the time of executing the topology model setting step, and the connectivity determination in each network case is performed by comparing the respective parameters with the respective critical values.

  According to the present invention, in a communication network such as a sensor network or an ad hoc network using a large number of communication devices, an effect is achieved that an output of a high connection condition can be realized by a simple process.

  Embodiments of a network design method and a network design support apparatus according to the present invention will be described below in detail with reference to the drawings. Note that the present invention is not limited to the embodiments.

  The network design method in the present embodiment is, for example, a sensor network in which a large number of communication devices are arranged in a specific range, an ad hoc network that does not have a fixed facility such as a base station, and constructs a network by mutual relay between mobile radio communication devices The present invention is applicable to all communication networks in which communication devices are connected wirelessly or by wire.

  FIG. 1 is a diagram illustrating an example of a network topology model. In FIG. 1, a network model 10 includes, for example, 10 nodes 1 (including a node 1S and a node 1T) indicating communication devices, and each node 1 is a link (shown by a solid line and a wired line) indicating a wireless or wired communication path. (Corresponding to a dotted line). 2 indicated by a solid line is a link, and 2C indicated by a dotted line is a link candidate representing a link that can be set.

  FIG. 2 is a diagram illustrating an example of a network topology model when a disturbing node is included in the network. The network model 10 includes a node 1S, a node 1T, a node 1U, a node 1V, and a node 1W as nodes 1 that perform desired communication, and further includes a disturbing node 3A as a disturbing node 3 that adversely affects the desired communication. , The disturbing node 3B is included. Here, in the present embodiment, the node 1 is expressed as a necessary node 1 in order to distinguish it from the disturbing node 3.

  For example, when the node 1S communicates with the node 1U using the node 1T as a relay point (assuming that the node 1V and the node 1W are not involved in the communication of the nodes 1S, 1T, and 1U), the disturbing node 3A and the disturbing node 3B Emits radio waves and adversely affects the communication of the nodes 1S, 1T, and 1U. On the other hand, radio waves emitted from the node 1V and the node 1W may adversely affect the communication of the nodes 1S, 1T, and 1U, but this is interference and is distinguished from the above-described interference. In this embodiment, as an example, a network design method that considers interference as well as interference will be described.

  In FIG. 2, when the network model 10 is a unit area, the density M of the necessary node 1 is 5 and the density Mb of the disturbing node 3 is 2. Further, the density Mb of the disturbing node 3 is a function that increases as the density M of the necessary node 1 increases. In the present embodiment, for example, it is assumed that there is a proportional relationship. Therefore, in the present embodiment, the density Mb can be expressed as “Mb = M × 0.4”.

  In the network design method of the present embodiment, when a link candidate 2C for connecting nodes is given, the ratio of the other necessary nodes 1 connected by the node 1S and the link 2 to the total number of nodes is Judgment is made, and a communication network is constructed so that this is a certain value or more.

  For example, in FIG. 1, there are 10 necessary nodes 1 (including nodes 1S and 1T), 23 link candidates 2C connecting between nodes (including link 2), and the node 1S includes Three nodes 1T are connected. Accordingly, the ratio of the other necessary nodes 1 connected to the node 1S to the total number of nodes is “3/10 = 0.3”. When the node 1S itself is included, the ratio is “4/10 = 0.4”. Since the present embodiment is intended for a case where the number of nodes is large, the ratio when the node 1S is included and the ratio when the node 1S is not included can be considered to be substantially equal. That is, in the present embodiment, the node 1S may or may not be included in the calculation of the ratio.

  In the present embodiment, in order to widely transmit information transmitted from the node 1S to other necessary nodes 1, an appropriate link is selected from the link candidates 2C to make it an effective link 2, and the above ratio is equal to or greater than a certain value. And That is, in this embodiment, the link 2 is efficiently selected from the link candidates 2C so that more necessary nodes 1 and nodes 1S can be connected in a limited communication band, communication device, and the like. To do.

  Next, parameters necessary for realizing the network setting method of the present embodiment will be described.

  In this embodiment, the signal-to-noise ratio is calculated using the density M of the required node 1, the density Mb of the disturbing node 3 (a function of M), the disturbing load coefficient Kb in noise, and the interference load coefficient Kk as key parameters. To do. Then, network design is performed using the property that when this ratio exceeds a specific value, the connection status of the nodes in the network becomes dense, and when the ratio is less than the specific value, it becomes sparse. Further, when a certain reception node (necessary node 1) receives a transmission signal from another transmission node (necessary node 1), the attenuation L of the transmission signal increases as the distance D between the transmission and reception nodes increases. In the present embodiment, a predetermined threshold value is obtained using a known relationship between the distance D and the attenuation L, and the key parameter is adjusted based on the threshold value.

For example, when the reception node 1 receives a transmission signal from another transmission node 1, the reception signal of the reception node 1 is a signal in which the transmission power of the transmission node 1 is attenuated. Therefore, the received signal can be expressed by the following equation (1).
Received signal = Transmission power P of transmission node × Attenuation L (1)

An adverse effect on communication between the two necessary nodes 1 is referred to as noise. Noise is weighted addition of interference, interference, and background noise. When the interference load coefficient is Kb and the interference load coefficient is Kk, the noise can be expressed as the following equation (2).
Noise = interference + interference + background noise
= Kb × Σ (transmission power P × attenuation L) + Kk × Σ (transmission power P × attenuation L)
+ Background noise (2)

  The jamming is the sum of the signals P transmitted by the individual jamming nodes 3 that have attenuated by L and arrived at the receiving node (sum of Mb numbers). Similarly, the interference is the sum of the transmission powers P of the necessary nodes 1 other than the receiving node 1 attenuated by L (sum of M numbers). The transmission power P and the attenuation L for interference and interference may be different from each other, but are the same here for convenience of explanation.

Therefore, the reception node 1 can receive the transmission signal from the transmission node 1 when the ratio of the reception signal and noise exceeds the threshold value. This can be expressed by the following equation (3).
(Transmission node transmission power P × attenuation L) / noise> threshold value (3)

  FIG. 3 is a flowchart showing the network design method of the present embodiment. In the network design of the present embodiment, topology model setting (step S1), random model trial (step S2), critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0) are determined (step S3), critical values The steps of connectivity determination (step S4) and high connection condition output (step S5) based on (Mb1, Mb2, Kb0) and (M1, M2, Kk0) are sequentially executed.

  In “topology model setting” in step S1, for example, as shown in FIG. 1, node 1 and link candidate 2C are set, and further, originating node 1S is set. In “Random Model Trial” in step S2, a network model in which an appropriate link is randomly selected from the link candidates 2C in FIG. In the random model trial, since a large number of network models are set and the trial is performed, the amount of computer processing increases. FIG. 4 is a flowchart showing the “random model trial” procedure in step S2.

  Here, the “random model trial” procedure shown in FIG. 4 will be described with reference to the drawings. First, in step S101, an appropriate link is selected from the link candidates, and the result is stored in the “random model connection information” area of the data memory. Next, in step S102, the ratio of other nodes connected to the node S is obtained. Next, in step S103, it is determined whether or not the ratio is equal to or greater than a certain value. For example, if the ratio is equal to or greater than a certain value (Yes in step S103), the process proceeds to step S104. On the other hand, when it does not reach a certain value (step S, No), the process proceeds to step S105, the condition is changed and an attempt is made, and then the process returns to step S101. Further, in step S104, it is confirmed whether or not the trial has been completed over a plurality of cases, and when the plurality of cases have been tried (step S104, Yes), the processing related to the “random model trial” is terminated. On the other hand, when another example is tried under the same conditions (step S104, No), the process proceeds to step S106, another example is tried, and then the process returns to step S101.

  Next, in the “determination of critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0)” in step S3, critical values (Mb1, Mb2, Kb0) and (M1, M2) are determined based on the results of random model trials. , Kk0).

  Next, the processing of “connectivity determination based on critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0)” in step S4 will be described.

  FIG. 5 is a flowchart showing the processing of “connectivity determination based on critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0)” in step S4. Here, four parameters Mb, Kb, M, Kk and six critical values Mb1, Mb2, Kb0, M1, M2, Kk0 are used. These parameters do not change all at the same time, only one is changed at a time and the others are fixed. In this state, it is determined how the relationship between each parameter and the critical value is. Specifically, the density Mb of the disturbing node 3 is (Mb1 ≦ Mb ≦ Mb2), the disturbing load coefficient Kb is (Kb ≦ Kb0), or the density M of the required node 1 is (M1 ≦ Mb2). It is determined whether M ≦ M2) or the interference load coefficient Kk is (Kk ≦ Kk0).

  Here, the meaning of the determination of the disturbance load coefficient Kb (Kb ≦ Kb0) will be described with reference to FIGS. FIG. 6 is a diagram schematically showing the relationship between the density Mb of the disturbing node 3 and the disturbing load coefficient Kb, and FIG. 7 is a diagram schematically showing the relationship between the disturbing load coefficient Kb and the connection state (connectivity) of the node S1. FIG. In FIG. 6, the lower part is a state in which a large number of nodes 1 are connected as a whole of the network model 10 (high connection state), and the upper part is a state in which the nodes 1 are not so connected (low connection state). Is shown. For example, when the density Mb of the disturbing node 3 on the horizontal axis in FIG. 6 is fixed and only the disturbing load factor Kb on the vertical axis is increased, the lower part becomes high connection, but the upper part becomes low connection. These states represent a decrease in connection between nodes due to an increase in weight (load) that considers interference. This corresponds to the fact that, in FIG. 7, when the load factor Kb for disturbance on the horizontal axis is increased, the connection becomes high when Kb is smaller than the critical value Kb0, but the connection becomes low when Kb0 is exceeded. .

  Next, the meaning of the density Mb of the disturbing node 3 (Mb1 ≦ Mb ≦ Mb2) and the meaning of the disturbing load coefficient Kb (Kb ≦ Kb0) will be described with reference to FIGS. FIG. 8 is a diagram schematically showing the relationship between the density Mb of the disturbing node 3 and the connection status (connectivity) of the node S1. In FIG. 6, when the disturbance load factor Kb on the vertical axis is fixed and only the density Mb of the disturbance node 3 on the horizontal axis is increased, the low connection is temporarily changed to the high connection, and then the density Mb of the disturbance node 3 is further increased. If it increases, it shifts to a low connection again. This means that when the density Mb of the disturbing node 3 is small, the density M of the necessary node 1 is also small, so that the node 1 in the network model 10 has low connectivity. Further, when the density Mb of the disturbing node 3 and the density M of the necessary node 1 are increased thereafter, the connectivity between the necessary nodes is ensured and the connectivity is improved. Further, when the density Mb of the disturbing node 3 and the density M of the necessary node 1 are further increased, the influence of the disturbing becomes stronger and the connectivity is reduced. Such a tendency occurs because the density Mb of the disturbing node 3 increases as the density M of the necessary node 1 increases (“Mb = M × 0.4” in FIG. 2). In FIG. 8, when the density Mb of the disturbing node 3 on the horizontal axis is increased, the connection is low when Mb is smaller than the critical value Mb1, but once the critical value Mb1 is exceeded, the connection is once high. When the critical value Mb2 is exceeded, this corresponds to a low connection.

  Thus, in the above description, the meaning of judgment of the disturbance load coefficient Kb and the density Mb of the disturbance node 3 which are parameters relating to disturbance has been described. However, the determination of the interference load coefficient Kk (Kk ≦ Kk0) and the necessary node 1 The determination of the density M (M1 ≦ M ≦ M2) can be similarly explained.

  Next, the processing of FIG. 5 will be described on the premise of the connectivity determination. First, in step S11, parameters (M, Kk) representing the influence of interference are fixed, and the processing proceeds to two systems (step S13, step S14) in consideration of the influence of interference. On the other hand, in step S12, parameters (Mb, Kb) representing the influence of interference are fixed, and the process proceeds to processing of two systems (step S15, step S16) in consideration of the influence of interference.

  In step S13, the density Mb of the disturbing node 3 is fixed, and the disturbing load coefficient Kb is changed. Then, in step S17, the disturbance load coefficient Kb in each case is compared with the critical value (critical load coefficient) Kb0 of the load coefficient, and when “Kb ≦ Kb0”, it is determined that the connectivity is high (step S22). When “Kb> Kb0”, it is determined that the connectivity is low (step S21).

  In step S14, the disturbance load coefficient Kb is fixed, and the density Mb of the disturbance node 3 is changed. In step S18, the density Mb of the disturbing node 3 in each case is compared with the critical density values (critical density) Mb1 and Mb2, and if “Mb1 ≦ Mb ≦ Mb2”, it is determined that the connectivity is high. (Step S22) When Mb is other than that, it is determined that the connectivity is low (Step S21).

  In step S15, the density M of the interference node 1 is fixed, and the interference load coefficient Kk is changed. In step S19, the interference load coefficient Kk and the critical load coefficient Kk0 in each case are compared, and if “Kk ≦ Kk0”, it is determined that the connectivity is high (step S22), and “Kk> Kk0” is satisfied. In this case, it is determined that the connectivity is low (step S21).

  In step S16, the interference load coefficient Kk is fixed, and the density M of the interference node 1 is changed. In step S20, the density M of the interference node 1 in each case is compared with the critical densities M1 and M2. If “M1 ≦ M ≦ M2”, it is determined that the connectivity is high (step S22). Otherwise, it is determined that the connectivity is low (step S21).

  Therefore, in the “high connection condition output” of step S5 shown in FIG. 3, the high connection condition is output based on the determination result.

  As described above, in the network design method of the present embodiment, after the topology model setting (step S1), the random model trial (step S2) is performed once, and the threshold value that is the threshold value of each parameter based on the result. (Mb1, Mb2, Kb0) and (M1, M2, Kk0) are determined (step S3). In the case of individual networks, parameters (Mb, Kb), (M, Kk) and critical values (Mb1, Mb2, The connectivity is determined by comparing the size with (Kb0), (M1, M2, Kk0) (step S4). As described above, in this embodiment, the network model connectivity, that is, the “topological model” and “random model trial”, which are usually equivalent to the height of the ratio of the node 1 connected to the node 1S, is repeatedly executed. The resulting characteristics are expressed by parameters (Mb, Kb) and (M, Kk). Thereby, “random model trial” and “critical value determination” are performed only at the time of “topology model setting”, and threshold values (Mb1, Mb2, Kb0), (M1, M2, Kk0) are used for individual network case evaluation. We decided to make connectivity judgment by simple comparison with

  Next, the network design support apparatus 100 that realizes the network design method shown in FIG. 3 will be described. FIG. 9 is a diagram illustrating a configuration example of the network design support apparatus 100. The network design support apparatus 100 includes a topology model setting unit 101, a random model trial unit 102, a critical value determination unit 103, a critical value storage unit 104, A design condition input unit 105, a target network connection coefficient derivation unit 106, a design condition evaluation unit 107, and an output unit 108 are provided.

  The topology model setting unit 101 executes “topology model setting (step S1)” in FIG. 3, and sets, for example, the network model shown in FIG.

  The random model trial unit 102 executes “random model trial (step S2)” in FIG. For example, when it is assumed that a plurality of nodes included in the network model are randomly connected to other connectable nodes, at least one of the link candidates becomes valid, and a link exists between at least two nodes. Generate a set network model for multiple connection parameters.

  The critical value determination unit 103 executes “critical value (Mb1, Mb2, Kb0) and (M1, M2, Kk0) determination (step S3)” of FIG. The critical value determination unit 103 includes a connection determination unit 111, an (Mb1, Mb2, Kb0) extraction unit 112, and an (M1, M2, Kk0) extraction unit 113. The connection determination unit 111 analyzes the network model for each network model generated by the random model trial unit 102 for a plurality of connection parameters, and determines the number of nodes connected via links in the network model. To do. The determination by the connection determination unit 111 may be the number of nodes connected to the node 1S via a link, or the ratio of the nodes connected to the node 1S via a link to the total number of nodes. The (Mb1, Mb2, Kb0) extraction unit 112 analyzes the change state of the number of nodes determined by the connection determination unit 111 in association with the order of the magnitude relation of the plurality of connection parameters, and based on the analysis result of the change state Thus, the critical values (Mb1, Mb2, Kb0) that serve as thresholds when evaluating the design conditions of the network design are extracted. The (M1, M2, Kk0) extraction unit 113 analyzes the change state of the number of nodes determined by the connection determination unit 111 in association with the order of the magnitude relation of the plurality of connection parameters, and based on the analysis result of the change state Thus, (M1, M2, Kk0), which are threshold values for evaluating the design conditions of the network design, are extracted. Details of the processes of the connection determination unit 111, the (Mb1, Mb2, Kb0) extraction unit 112, and the (M1, M2, Kk0) extraction unit 113 will be described later. The critical value storage unit 104 stores the parameters determined by the critical value determination unit 103.

  The design condition input unit 105 inputs a design condition of a network that is a target of “connectivity determination by (Mb1, Mb2, Kb0) and (M1, M2, Kk0)” in FIG. 3 (step S4).

  The target network connection coefficient deriving unit 106 derives connection parameters Mb, Kb, M, and Kk of the target network based on the network design conditions input by the design condition input unit 105.

  The design condition evaluation unit 107 performs “connectivity determination based on (Mb1, Mb2, Kb0) and (M1, M2, Kk0)” (step S4) in FIG. 3, and Mb1 stored in the critical value storage unit 104 , Mb2, Kb0, M1, M2, Kk0 are compared with the parameters Mb, Kb, M, Kk of the target network derived by the target network connection coefficient deriving unit 106, and the target network is designed based on the comparison result. Evaluate the conditions.

  The output unit 108 executes “high connection condition output (step S5)” in FIG. 3 and outputs the evaluation result.

  Next, how to obtain the critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0) in the present embodiment will be described. In the present embodiment, the processing of each step shown in FIG. 4 is performed in the “random model trial (step S2)” shown in FIG. 3, and further, “critical values (Mb1, Mb2, Kb0) and (M1) shown in FIG. , M2, Kk0) determination (step S3) ", the critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0) are determined. These procedures are described in detail in FIGS. 10 to 14 and FIGS. FIG. 12 details the procedure of “determination of connection between node S and another node” in step S31 of FIGS. FIG. 13 details the procedure of “create node information” in steps S41, S42, S43, and S44 of FIG. FIG. 14 details the procedure of “determination of connection between node i and node j” in step S51 of FIG.

  Of the critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0), FIG. 10 shows how to obtain the critical load Kb0. When determining the critical load Kb0, first, in step S31, the connection determination between the node S and another node is performed. This result is written in the “connection state between node S and other nodes” area of the data memory. In step S32, it is determined whether or not several kinds of values of the critical load Kb0 have been tried. If the trial has been done (Yes), the “connection status between node S and other nodes” area of the data memory is set in step S34. Referring to FIG. 7, the value of Kb at which the connection state greatly decreases before and after is defined as Kb0 (see FIG. 7). On the other hand, if it has not been tried (No), in step S33, the next candidate for the disturbance load coefficient Kb is set, and steps S31 to S33 are repeatedly executed until it is determined that the trial has been completed (Yes). In step S34, for example, as shown in FIG. 7, a critical value Kb0 is set around the disturbance load coefficient in which the connection state largely changes before and after.

  Of the critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0), FIG. 11 shows how to obtain the critical densities Mb1, Mb2. When determining the critical densities Mb1 and Mb2, first, in step S31 of FIG. 11, the connection determination between the node S and another node is performed. This determination result is written in the “connection status between node S and other nodes” area of the data memory. In step S35, it is determined whether or not the critical densities Mb1 and Mb2 have been tried. If they have been tried (Yes), refer to the “connection status between the node S and other nodes” area of the data memory and check the connection status before and after. The value of Mb that greatly increases is Mb1, and the value of Mb that greatly decreases is Mb2. On the other hand, if it has not been tried (No), in step S36, the next candidate of the density Mb of the disturbing node 3 is set, and steps S31, S35, and S36 are repeatedly executed until it is determined that the trial has been completed (Yes). In step S37, as shown in FIG. 8, the value of Mb that greatly increases the connection status before and after is set as Mb1, and the value of Mb that greatly decreases is set as Mb2.

  Of the critical values (Mb1, Mb2, Kb0) and (M1, M2, Kk0), the critical load coefficient Kk0 can be obtained in the same manner as the critical load coefficient Kb0 according to FIG. 10 and FIG. The critical densities M1 and M2 can be obtained in the same manner as the critical densities Mb1 and Mb2 according to FIGS.

  Next, the procedure of “determination of connection between node S and other nodes (step S31)” in FIGS. 10 and 11 will be described. FIG. 12 is a flowchart showing the procedure of “determination of connection between node S and other node (step S31)” in FIGS.

  First, in step S41, information on a node directly connected to the node S is created and written in the “direct connection information” area of the data memory. In step S42, information on the node connected to node S in one relay is created and written in the “1-hop connection information” area of the data memory. In steps S43 to S44, information on a node connected to node S in two relays to information on a node connected to node S in N relays is created. Then, when all the nodes are covered (step S45), the “connection determination between the node S and another node” procedure is terminated.

  Next, a procedure for “creating node information” in FIG. 12 will be described with reference to FIG. First, in step S51, the connection determination between the node i and the node j is performed, and the determination result is written in the “R-hop connection information addition” area of the data memory. In step S52, it is determined whether or not all the nodes in the network have been determined as nodes j. If Yes, the process proceeds to step S54. On the other hand, if it is No, it will transfer to step S53, the next candidate of the node j will be allocated, and step S51-S53 will be repeatedly performed until it becomes Yes in step S52. In step S54, it is determined whether or not all nodes connected to the node S in the relay R-1 times are determined as the node i. If Yes, the process ends. On the other hand, if it is No, it will transfer to step S55, the next candidate of the node i will be allocated, and step S51-S55 will be repeatedly performed until it becomes Yes in step S54.

  Next, the “connection determination between node i and node j” procedure in FIG. 13 will be described with reference to FIG. In step S61, the “topology model inter-node connection information” area of the data memory is referred to, the connection status between the node i and the node j is determined, and the determination result is stored in the “add R hop connection information” area of the data memory. Write. The “topology model node connection information” area of the data memory is the “random model connection information” area of FIG.

  Next, how to determine the parameters (Mb, Kb) and (M, Kk) will be described. First, the relationship between the distance D between nodes and the attenuation L will be described. FIG. 15 is a diagram schematically illustrating the periphery of the node 1S. A range where the attenuation of the transmission signal emitted from the node 1S becomes L at a distance D from the node 1S is shown. As the distance D increases and the distance from the node 1S increases, the attenuation L progresses. L = 1 in the range 30A, L = 0.1 in the range 30B, and L = 0.01 in the range 30C.

  FIG. 16 is a diagram schematically showing the relationship between the distance D and the attenuation L. When the attenuation L is expressed as a function of the distance D, in many cases, the attenuation L becomes infinite when the distance D is 0, and the attenuation L progresses as the distance D increases. Note that the attenuation L progresses as the distance D increases, but does not become zero. However, for convenience of algorithm execution, the minimum value Dn and the maximum value Dx of the distance D are determined. When the distance D is D <Dn, D is Dn, the attenuation L is Ln, and the distance D is the maximum value Dx. The attenuation L is set to zero. FIG. 17 is a diagram illustrating a specific example of the case where the attenuation L progresses as the distance D increases. The attenuation L is depicted as being inversely proportional to the cube of D. The relationship that the attenuation L is inversely proportional to the power of the distance D is generally used widely (for example, edited by Yoshihisa Okumura and Masaaki Shinji, “Basics of Mobile Communication” edited by the Institute of Electronics, Information and Communication Engineers).

  As described above, in this embodiment, the network model is designed using Mb, Kb, M, and Kk, which are connection coefficients (parameters) between nodes, as key parameters. Thereby, the output of a high connection condition can be realized by a simple process.

  In the present embodiment, the case where the node S as a node design reference is fixed has been described. However, the same network design method may be applied even when the node S is not fixed and generalized. it can. In this embodiment, when the attenuation L is obtained from the distance D, the attenuation L is proportional to the cube of the distance D. However, the attenuation L may be set based on another relational expression. Further, in the present embodiment, the network design considering the interference caused by the necessary node 1 has been described. However, the network design may be performed considering only the interference without considering the interference.

  As described above, the network design method according to the present invention is useful as a design method for a communication network in which a plurality of communication devices are arranged and the communication devices are connected wirelessly or by wire. Suitable for network design when communication devices that interfere with communication are included.

It is a figure which shows an example of a network topology model. It is a figure which shows an example of a network topology model in case a disturbance node is contained in a network. It is a flowchart which shows the network design method concerning this invention. It is a flowchart which shows the "random model trial" procedure of step S2. It is a flowchart which shows the process of "connectivity judgment by critical value (Mb1, Mb2, Kb0) and (M1, M2, Kk0)" of step S4. It is a figure which shows typically the relationship between the density Mb of an obstruction node, and the load factor Kb of obstruction. It is a figure which shows typically the relationship between the load factor Kb of disturbance, and the connection condition (connectivity) of the node S. FIG. It is a figure which shows typically the relationship between the density Mb of a disturbance node, and the connection condition (connectivity) of the node S. FIG. It is a figure which shows the structural example of a network design assistance apparatus. It is a figure which shows how to obtain | require critical load Kb0. It is a figure which shows how to obtain | require critical density Mb1, Mb2. FIG. 12 is a diagram illustrating a procedure of “determination of connection between node S and another node” in step S31 in FIGS. 10 and 11; It is a figure which shows the procedure of "creating the information of a node" of step S41, S42, S43, S44 of FIG. FIG. 14 is a diagram illustrating a procedure of “determination of connection between node i and node j” in step S51 of FIG. FIG. 3 is a diagram schematically showing the periphery of a node S. It is a figure which shows typically the relationship between the distance D and the attenuation | damping L. FIG. It is a figure which shows the specific example in case attenuation | damping L advances with the increase in the distance D. FIG.

Explanation of symbols

1 node (required node)
1S, 1T, 1U, 1V, 1W Node 2 Link 2C Link candidate 3, 3A, 3B Interfering node 100 Network design support device 101 Topology model setting unit 102 Random model trial unit 103 Critical value determination unit 104 Critical value storage unit 105 Design condition Input unit 106 Target network connection coefficient derivation unit 107 Design condition evaluation unit 108 Output unit 111 Connection determination unit 112 (Mb1, Mb2, Kb0) extraction unit 113 (M1, M2, Kk0) extraction unit

Claims (6)

A topology setting step for setting a topology model composed of a plurality of nodes indicating communication devices and a plurality of link candidates indicating communication paths, and selecting an appropriate link from the link candidates at random and making it an effective link A network setting method for generating a network model, performing a random model trial step for performing a plurality of times in a predetermined procedure, and outputting a high connection condition based on the execution result,
In a network model including a disturbing node that adversely affects communication by a necessary node that performs desired communication, a necessary node for determining network connectivity (low connection and high connection) based on the trial result A critical value determining step for determining a critical value of density M, a critical value of interference load factor Kk, a critical value of disturbing node density Mb (a function of M), and a critical value of disturbing load factor Kb;
A connectivity determination step of determining network connectivity using each critical value, with the required node density M, the interference load factor Kk, the disturbing node density Mb, and the disturbing load factor Kb as key parameters;
Including
The random model trial step and the critical value determination step are performed only at the time of executing the topology model setting step, and the connectivity determination in each network case is performed by comparing the respective parameters with the respective critical values. A characteristic network design method.   A threshold value is obtained using a known relationship between the distance and attenuation, and the key parameter is obtained based on the threshold value. The network design method according to claim 1. In the critical value determining step,
Based on the regularity in which the connection state changes from the high connection state to the low connection state with the increase of the disturbance load coefficient Kb (fixed density Mb), the value of Kb when the connection state decreases most rapidly is expressed as Kb. The critical value Kb0 of
Based on the regularity that the connection state temporarily changes from the low connection state to the high connection state and then goes to the low connection state again as the density Mb of the disturbing node increases (load coefficient Kb is fixed), the connection state increases most rapidly. The value is the critical value Mb1 of the Mb, the value of Mb that decreases most rapidly is the critical value Mb2 of the Mb,
Based on the regularity that the connection state changes from the high connection state to the low connection state as the interference load factor Kk increases (fixed density M), the value of Kk at which the connection state decreases most rapidly is determined as the critical value of Kk. With value Kk0,
Based on the regularity that the connection state temporarily changes from the low connection state to the high connection state and becomes the low connection state again as the required node density M increases (load coefficient Kk is fixed), the connection state increases most rapidly. 3. The network design method according to claim 1, wherein a value is the critical value M1 of the M, and a value of M that decreases most rapidly is the critical value M2 of the M. In the connectivity determination step,
The parameters M and Kk representing the influence of interference and the density Mb of the disturbing node are fixed, the disturbing load coefficient Kb is changed, the changed disturbing load coefficient Kb is compared with the critical value Kb0, and “Kb ≦ In the case of “Kb0”, it is determined that the connectivity is high, and in the case of “Kb> Kb0”, it is determined that the connectivity is low,
The parameters M and Kk representing the influence of interference and the disturbance load coefficient Kb are fixed, the density Mb of the disturbance node is changed, and the changed density Mb of the disturbance node is compared with the critical values Mb1 and Mb2. When Mb1 ≦ Mb ≦ Mb2 ”, it is determined that the connectivity is high, and when Mb is other than that, the connectivity is determined to be low.
The parameters Mb and Kb representing the influence of interference and the density M of the interference node are fixed, the interference load coefficient Kk is changed, the changed interference load coefficient Kk is compared with the critical value Kk0, and “Kk ≦ In the case of “Kk0”, it is determined that the connectivity is high, and in the case of “Kk> Kk0”, it is determined that the connectivity is low,
The parameters Mb and Kb representing the influence of the interference and the interference load coefficient Kk are fixed, the density M of the interference node is changed, and the changed density M of the interference node is compared with the critical values M1 and M2. 4. The network design method according to claim 3, wherein if ≦ M ≦ M2, it is determined that the connectivity is high, and if M is otherwise, it is determined that the connectivity is low. A topology setting unit that sets a topology model configured by a plurality of nodes indicating communication devices and a plurality of link candidates indicating communication paths, and selecting an appropriate link from the link candidates at random and making it an effective link A network model support unit that generates a network model and outputs a high connection condition based on a result of the trial.
further,
In a network model including a disturbing node that adversely affects communication by a necessary node that performs desired communication, a necessary node for determining network connectivity (low connection and high connection) based on the trial result A critical value determination unit for determining a critical value of density M, a critical value of interference load coefficient Kk, a critical value of density Mb (function of M) of the disturbing node, and a critical value of disturbing load coefficient Kb;
A connectivity determination unit that performs network connectivity determination using each critical value, using the required node density M, the interference load factor Kk, the disturbing node density Mb, and the disturbing load factor Kb as key parameters;
With
The processing of the random model trial unit and the critical value determination unit is performed only at the time of setting the topology model, and the connectivity determination in each network case is performed by comparing each parameter with each critical value. A featured network design support device.   A network design support program causing a computer to execute the network design method according to claim 1.

Images