JP6161335B2 - Mesh point device and program - Google Patents

Description

  The present invention relates to a mesh point device and a program constituting a mesh network.

  A communication method in which each mesh point device transmits a packet to another mesh point device (adjacent node) capable of communication without using a centralized control device such as a base station, and sends the packet to a desired destination. (Mesh network) is considered. As such a mesh network, specifically, regulations such as 802.11s have been formulated.

  Also, in a wireless mesh network, an example of using a Viterbi routing algorithm to determine a route between a mesh point device (source node) as a source and a mesh point device (destination node) as a destination However, this is disclosed in Patent Document 1.

Special table 2009-520445

  However, the communication status between each mesh point device in the mesh network changes every moment. For this reason, a communication path determined by a certain method is not necessarily an optimal path, and a communication failure may occur during communication.

  The present invention has been made in view of the above circumstances, and an object thereof is to provide a mesh point device and a program that enable more stable communication.

  The present invention for solving the problems of the above-described conventional example is a mesh point device that is connected to each other and constitutes a mesh network, and each of the possible communication route candidates to the mesh point device as a communication destination is routed Calculating means for calculating a cost; path determining means for determining a communication path to be used for communication out of the possible communication path candidates based on the calculated path cost; and determining the determined communication path to another mesh Route notifying means for notifying the point device, wherein the calculating means calculates a plurality of path costs for each possible communication path candidate for each communication path candidate, and the path determining means is the communication path candidate. A plurality of communication paths are determined as communication paths to be used for communication from among the communication path candidates based on a plurality of calculated path costs for each. And, the route notification means is obtained by the notifying the plurality of communication routes the determined other mesh point device.

  Here, the route determination means determines a predetermined number of different communication routes from among the possible communication route candidates as communication routes to be used for communication based on a plurality of route costs calculated for each of the communication route candidates. It is good to do.

  And a means for obtaining a plurality of data fragments using an erasure code based on the data to be transmitted, and a means for generating a packet including each of the obtained data fragments. Each of the packets may be transmitted through the determined plurality of different communication paths.

  Furthermore, an aspect of the present invention is a program that calculates a path cost for each possible communication path candidate to a mesh point apparatus that is a communication destination of mesh point apparatuses that are connected to each other and constitute a mesh network. Based on the calculated route cost, route determining means for determining a communication route to be used for communication from the possible communication route candidates, and notifying the determined communication route to other mesh point devices When functioning as a route notifying unit and functioning as the calculating unit, when calculating a plurality of path costs for each possible communication route candidate for each communication route candidate and functioning as the route determining unit Based on the route cost calculated for each of the communication path candidates, a plurality of the communication path candidates A communication path, is determined as the communication path to be used for communication, when the function as the path notification means is obtained by the fact to notify a plurality of communication routes the determined other mesh point device.

  According to the present invention, more stable communication is possible.

It is a block diagram showing the structural example of the mesh point apparatus which concerns on embodiment of this invention. It is a functional block diagram showing the example of the mesh point apparatus which concerns on embodiment of this invention. It is explanatory drawing showing the example of the path | route metric value which the mesh point apparatus which concerns on embodiment of this invention hold | maintains. It is the schematic for demonstrating operation | movement of the mesh point apparatus which concerns on embodiment of this invention.

  Embodiments of the present invention will be described with reference to the drawings. The mesh network to which the mesh point device 1 according to the embodiment of the present invention includes a plurality of mesh point devices 1. The plurality of mesh point devices 1 are connected to each other to form a mesh network.

  As illustrated in FIG. 1, each mesh point device 1 includes a control unit 11, a storage unit 12, and a communication unit 13. Here, the control unit 11 is a program control unit such as a CPU, and operates according to a program stored in the storage unit 12. In the present embodiment, the control unit 11 uses another wireless mesh as a communication destination using, for example, an HWMP (Hybrid Wireless Mesh Protocol) based on an RM-AODV (Radio Metric Ad hoc On-Demand Distance Vector) routing method. A possible communication path candidate to the point device 1 is searched. Then, the route cost is calculated for each possible communication route candidate searched. Based on the route cost calculated in this way, the control unit 11 determines a communication route to be used for communication from among the communication route candidates, and notifies the other mesh point device 1 of the determined communication route.

  In the present embodiment, the control unit 11 calculates a plurality of path costs for each of the possible communication path candidates for each communication path candidate, and based on the path costs calculated for each communication path candidate, A plurality of communication paths are determined as possible communication paths from among possible communication path candidates. Then, the control unit 11 notifies the determined plurality of communication paths to the other mesh point device 1. Each mesh point device 1 transmits a packet to be transmitted via the determined communication path. Details of the operation of the control unit 11 will be described later.

  The storage unit 12 is a memory device or the like and holds a program executed by the control unit 11. The program may be provided by being stored in a computer-readable recording medium and stored in the storage unit 12. The storage unit 12 also operates as a work memory for the control unit 11. The communication unit 13 is, for example, a wireless LAN interface, and exchanges information with other mesh point devices 1 that are adjacent (within a communicable range). The communication unit 13 transmits and receives data to and from the terminal device 2 wirelessly.

  Specifically, as shown in FIG. 2, the control unit 11 according to the present embodiment functionally includes a neighboring node detection unit 21, a calculation unit 22, a route determination unit 23, a route notification unit 24, and a packet. The forming unit 25 and the communication control unit 26 are included.

  The neighboring node detection unit 21 transmits / receives test frames to / from each of the other mesh point devices 1 that can communicate with each other via the communication unit 13, and obtains information on the transmission rate r and the frame error rate ept. Every time, the path metric value between each mesh point device 1 that can communicate is calculated. Specifically, the path metric value Ca (i) (i = 1, 2,...) Between the i-th mesh point device 1-i that can be communicated, for example,

などと設定することとすればよい。ここでＯca，Ｏp，Ｂtはそれぞれチャネルアクセスオーバーヘッド（Channel Access Overhead）、プロトコルオーバーヘッド（Protocol Overhead）、テストフレームに含まれるデータのビット数であり、プロトコルごとに予め定められた定数となる。

And so on. Here, Oca, Op, and Bt are the channel access overhead, the protocol overhead, and the number of bits of data included in the test frame, and are constants predetermined for each protocol.

  The arithmetic unit 22 generates and stores random numbers Rj (j = 1, 2,... N) as many as the predetermined multiplexing number N (N> 1). Further, the calculation unit 22 obtains a path metric value Ca (i, j) (i = 1, 2,...; J = 1, 2,... N) with the i-th mesh point device 1-i capable of communication. For example

などとして設定する。

And so on.

  That is, at least one of the parameters included in the equation (1) (the transmission rate r in the above equation (2) is not limited to this but may be multiplied by a frame error rate, channel access overhead, etc.) by a random number. In other words, N different path metric values (path metric values between the communicable i-th mesh point apparatus 1-i) Ca (i, j) ( i = 1, 2,...; j = 1, 2,... N) and Ca (i) calculated by the equation (1).

  The range of variation of the random value Rj (the range of the random number to be generated) may be determined empirically depending on which parameter is multiplied. In the following, for the sake of explanation, Ca (i) calculated by the equation (1) is expressed as Ca (i, 0) for convenience. The calculation unit 22 stores the Ca (i, j) (i = 1, 2,...; J = 0, 1, 2,... N) obtained in this way in the storage unit 12 (FIG. 3). ).

  In the present embodiment, each mesh point device 1 virtually forms a plurality of virtual communication units 13-1, 13-2,..., 13-N by, for example, time division multiplexing of the communication units 13. Keep it. In each mesh point device 1, the same j-th virtual communication unit 13-j communicates with each other, and for different j and l, the virtual communication unit 13-j of one mesh point device 1 and It is set so that the virtual communication unit 13-l of the other mesh point device 1 does not communicate. This setting includes, for example, identification information (referred to as a slice ID) indicating which virtual communication unit 13-j performs communication in data (packet) to be transmitted / received, and each virtual communication unit 13- This can be realized by allowing j to receive a packet including its corresponding slice ID. That is, in the present embodiment, N independent networks identified by the slice ID are formed.

Then, the route determination unit 23, in each of these virtual communication units 13-j (j = 0, 1, 2,... N), a node (mesh point device 1) or an edge (a pair of nodes) on the communication route. A plurality of communication paths are obtained such that the overlap of the partial paths connecting them is relatively small.

  This route determination method uses a proactive routing protocol such as RA-OLSR (Radio Aware-Optimized Link State Routing) or FSR (Fish-eye State Routing) for each network identified by the slice ID. And a method using a reactive routing protocol such as AODV (Ad Hoc On-Demand Distance Vector Routing), and also in combination with these proactive routing protocols and reactive routing protocols as in 802.11s However, in the network where the slice ID is “s”, the route using the random value Rs among the random values stored in each mesh point device 1 is used. For each possible communication path, change at least one of the parameters in the decision Variation in route cost.

  As a result, communication paths are determined using different path costs in each of the networks identified by the slice ID, and the virtual communication unit 13-j (j = 0, 1, 2,... N) is determined. Each obtains a plurality of communication paths in which the overlap of nodes (mesh point device 1) and edges (partial paths connecting a pair of nodes) on the communication path is relatively small. The route determination unit 23 outputs route information representing the communication route acquired for each slice ID to the route notification unit 24.

  As a specific example, as illustrated in FIG. 4, the outline of the operation of the route determination unit 23 will be described using a mesh network including five mesh point devices 1 a to 1 e as an example. It is assumed that the mesh point devices 1a to 1e can be connected to each other as shown by the broken lines in FIG. That is, it is assumed that the mesh point devices 1a-1c, 1a-1b, 1b-1c, 1b-1e, 1c-1d, 1c-1e, 1d-1e can communicate with each other.

At this time, the path metric value Ca between the mesh point devices 1a to 1c is “10” for the slice ID “1”, “12” for the slice ID “2”, and “13” for the slice ID “3”. To do. This is
1a-1c: 10, 12, 13
It is assumed that the path metric value is set as follows.
1a-1c: 10, 12, 13
1a-1b: 9, 10, 12
1b-1c: 8, 10, 9
1b-1e: 17, 20, 18
1c-1d: 11, 6, 12
1c-1e: 7, 13, 19
1d-1e: 12, 5, 13

Then, the possible communication path of the data that the mesh point device 1a transmits with the mesh point device 1e as the destination is
1a-1b-1e
1a-1b-1c-1e
1a-1b-1c-1d-1e
1a-1c-1e
1a-1c-1b-1e
1a-1c-1d-1e
Can be enumerated.

At this time, when the accumulated result (path cost) of the path metric value in each possible communication path is expressed in the same manner as the previous case for each of the slice IDs “1”, “2”, and “3”,
1a-1b-1e: 26, 30, 30
1a-1b-1c-1e: 24, 33, 40
1a-1b-1c-1d-1e: 45, 46, 51
1a-1c-1e: 17, 25, 32
1a-1c-1b-1e: 35, 42, 40
1a-1c-1d-1e: 33, 23, 38
It becomes.

  That is, when the slice ID is “1”, the path cost is minimum when the communication path is 1a-1c-1e, and when the slice ID is “2”, the path cost is determined by the communication path 1a-1c-1d-1e. In the case of the slice ID “3”, the path cost is minimum on the communication paths 1a-1b-1e.

  Therefore, the route determination unit 23 outputs a list (an example of route information) representing the communication route for each of the slice IDs “1”, “2”, and “3” to the route notification unit 24.

  In an example of the present embodiment, the route notification unit 24 receives from the route determination unit 23 a list of mesh point devices in the communication route that minimizes the route cost for each slice ID. Then, the route notification unit 24 inputs the list and the list associated with the list to the mesh point device 1 specified by the information immediately before the information specifying the own mesh point device 1 in the received list. A response packet including the slice ID that has been sent is transmitted. The path notification unit 24 transmits a response packet including the slice ID “j” via the virtual communication unit 13-j corresponding to the slice ID. The response packet may further include route cost information associated with each list.

  When the route notification unit 24 receives a response packet from another mesh point device 1, the mesh point specified by the information immediately before the information specifying the own mesh point device 1 in the list included in the response packet. The received response packet is sent as it is to the device 1. Again, the path notification unit 24 receives the response packet including the slice ID “j” via the virtual communication unit 13-j corresponding to the slice ID, and receives the corresponding virtual communication unit 13-j. It shall be sent as it is.

  In addition, in the list included in the response packet, the route notification unit 24, when information specifying the own mesh point device 1 is at the head of the list (when the response packet is addressed to itself), The included list and the slice ID are extracted and stored in the storage unit 12 in association with each other. At this time, if the list to be stored is the same as the list already associated with another slice ID and already stored in the storage unit 12, the list to be stored may not be stored. . As a result, lists representing the same communication path are excluded. Here, the route notifying unit 24 transmits a response packet for notifying route information. However, the route notifying unit 24 is not limited to this, and the route notifying unit 24 adds the route information as a header or trailer of a packet to be exchanged by normal communication. May be transmitted.

  In consideration of the fact that it may be excluded in this way, when the number of communication paths remaining after the exclusion of the lists representing the same communication paths is below a predetermined threshold, a path notification unit 24 finds a slice ID that is not stored in the storage unit 12 in association with the list. The virtual communication corresponding to the found slice ID includes a packet including the found slice ID, a request to update the path metric value by changing the random number, and a request identifier unique to the request. It is sent to another mesh point device 1 that can communicate through the unit 13-j.

  Upon receiving this request, the mesh point device 1 side refers to the request identifier included in the packet, and determines whether or not a packet including the same request identifier as the request identifier has been received in the past. Here, if a packet including the same request identifier as the request identifier has not been received in the past, the mesh point device 1 updates the random value Rj corresponding to the virtual communication unit 13-j, and can communicate with the other. The received packet is sent as it is to the mesh point device 1 that is not the packet reception source via the virtual communication unit 13-j corresponding to the slice ID included in the packet. .

  Further, in each mesh point device 1, when the random value Rj is changed in this way, the route determination process in the network specified by the slice ID corresponding to the random value Rj is performed again. Thus, each mesh point device 1 may repeat the above process until a predetermined number of communication paths are obtained between the mesh point device 1 and the destination mesh point device 1.

  The packet forming unit 25 includes the data to be transmitted received from the terminal device 2 by dividing it into packets Px (x = 1, 2,...) Having a predetermined data size. The packet Px includes packet identification information unique to each packet. Further, the packet forming unit 25 obtains N ′ pieces of packets Px obtained by the division (N ′ is the number of pieces of route information representing different communication routes stored in the storage unit 12 and N ′ ≦ N ) And is output to the communication control unit 26. At this time, the N ′ packets obtained by duplication include different slice IDs stored in association with different path information.

  The communication control unit 26 controls N ′ packets Px (x = 1, 2,...) To be transmitted through communication paths represented by different path information. Specifically, the communication control unit 26 refers to the slice ID “s” included in each packet Px, and transmits the packet Px via the virtual communication unit 13-s corresponding to the slice ID. That is, the communication control unit 26 acquires the path information stored in association with the slice ID “s” as the operation of the virtual communication unit 13-s. Then, the packet Px is transmitted to the other mesh point device 1 (virtual communication unit 13-s) to be the next transmission destination in the route information together with the route information and the information specifying the destination.

  Further, when the communication control unit 26 receives a packet including the slice ID “s” from the virtual communication unit 13-s of another mesh point device 1, it determines whether or not the own mesh point device 1 is the destination. Investigate. If the own mesh point device 1 is not the destination, the communication control unit 26 reads information specifying the other mesh point device 1 to be transmitted next included in the route information received together with the packet. Then, the communication control unit 26 sends the route information, information for specifying the destination, and a packet to the virtual communication unit 13-s of the mesh point device 1 specified by the read information.

  Furthermore, when the own mesh point device 1 is the destination, the communication control unit 26 refers to the packet identification information of the received packet, and has already received a packet containing the same packet identification information as the packet identification information. If so, the received packet is discarded. If a packet containing the same packet identification information as the packet identification information has not been received, the received packet is stored or output, and the packet identification information is held in the storage unit 12.

  According to the present embodiment described above, N ′ different communication paths are obtained using path metric values including variations due to random numbers, and the same packet is transmitted through each of them. On the receiving side, the packet is received via a plurality of different communication paths determined to be optimal based on the path metric value given variation by the random value. As a result, more stable communication is possible.

[Use of erasure code]
Further, in the description so far, the packet forming unit 25 duplicates only N ′ packets Px obtained by dividing the data to be transmitted received from the terminal device 2. Is supposed to receive duplicate packets on the destination side.

  Therefore, in an example of the present embodiment, the packet forming unit 25 uses the erasure code (Erasure Coding) based on the packet Px obtained by dividing the data to be transmitted received from the terminal device 2, and N If there are q data fragments and q (q <N ′) data fragments, a data fragment capable of reproducing the original data (packet Px) is generated. As this erasure code, for example, various codes such as RaptorQ (RFC6330) and polynomial oversampling can be adopted.

  The packet forming unit 25 outputs N ′ packets Pxy (y = 1, 2,... N ′) each including the generated N ′ data fragments to the communication control unit 26. Each packet Pxy obtained from this packet Px includes a different slice ID (slice ID “y” representing the y-th packet).

  The communication control unit 26 refers to the list which is the path information stored in the storage unit 12 and sends N ′ packets Pxy (x = 1, 2,...; Y = 1, 2,... N ′) respectively. , Control to be transmitted via the communication path represented by each list. Specifically, the communication control unit 26 refers to the slice ID “y” included in each packet Pxy, and transmits the packet Pxy via the virtual communication unit 13-y corresponding to the slice ID “y”. That is, the communication control unit 26 acquires the path information stored in association with the slice ID “y” as the operation of the virtual communication unit 13-y. Then, the packet Pxy is transmitted to the other mesh point device 1 (virtual communication unit 13-y) to be the next transmission destination in the route information together with the route information and the information specifying the destination. Thereafter, the virtual communication unit 13-y of each mesh point device 1 performs the same processing as when a duplicate packet is transmitted.

  In this case, the destination mesh point device 1 reproduces the original packet Px when q of the packets Pxy that may arrive via N ′ different communication paths are received. Output. In this case, the rate of duplication can be reduced and communication efficiency can be further improved.

  When the slice ID is used as described above, for example, identification information indicating that the slice ID is not obtained by duplication or erasure coding may be set as the slice ID. In this case, each mesh point device 1 that has received a packet including the slice ID may treat the packet as an ordinary packet of 802.11s.

  Further, here, the virtual communication units 13-j form a logically virtualized network, but different networks may be formed using different physical communication devices.

DESCRIPTION OF SYMBOLS 1 Mesh point apparatus, 2 Terminal device, 11 Control part, 12 Storage part, 13 Communication part, 21 Neighboring node detection part, 22 Computation part, 23 Path determination part, 24 Path notification part, 25 Packet formation part, 26 Communication control part .

Claims (4)

A mesh point device that is connected to each other to form a mesh network,
For each possible communication path candidate to the mesh point device as the communication destination, a calculation means for calculating a path cost calculated including variation due to random numbers ;
Route determining means for determining a communication route to be used for communication from among the possible communication route candidates based on the calculated route cost;
Route notification means for notifying the determined communication route to other mesh point devices;
Including
The calculation means calculates a plurality of path costs for each of the possible communication path candidates for each communication path candidate using different random numbers , respectively .
The route determination means determines a plurality of communication routes from among the communication route candidates as communication routes to be used for communication based on a plurality of route costs calculated for each communication route candidate,
The route notification means is a mesh point device that notifies the determined plurality of communication routes to another mesh point device. The mesh point device according to claim 1,
The route determination means, based on the route cost calculated for each of the communication route candidates, out of the possible communication route candidates, the number of communication routes exceeding a predetermined number different from each other as communication routes to be used for communication Mesh point device to be determined. The mesh point device according to claim 1 or 2,
Means for obtaining a plurality of data fragments using an erasure code based on the data to be transmitted;
Means for generating a packet including each of the obtained data fragments;
A mesh point device that sends each of the generated packets through the determined plurality of different communication paths. Mesh point devices that are connected to each other to form a mesh network
For each possible communication path candidate to the mesh point device as the communication destination, a calculation means for calculating a path cost calculated including variation due to random numbers ;
Route determining means for determining a communication route to be used for communication from among the possible communication route candidates based on the calculated route cost;
Route notification means for notifying the determined communication route to other mesh point devices;
Function as
When functioning as the computing means, a plurality of path costs for each of the possible communication path candidates are calculated for each communication path candidate using different random numbers , respectively .
When functioning as the route determination means, based on the route cost calculated for each of the communication route candidates, to determine a plurality of communication routes from among the communication route candidates as communication routes to be used for communication,
A program for notifying other mesh point devices of the determined plurality of communication paths when functioning as the path notification means.

Images