Method and device for dynamical protocol selection

• US 10,659,570 B2
• Filed: 10/14/2016
• Issued: 05/19/2020
• Est. Priority Date: 10/16/2015
• Status: Active Grant

• Current Assignee: Wsense S.r.l.
• Original Assignee: Universita' Degli Studi Di Roma La Sapienza (Repubblica Italiana)
• Inventors: Petrioli, Chiara, Lo Presti, Francesco, Di Valerio, Valerio, Spaccini, Daniele, Picari, Luigi
• Primary Examiner(s): Pollack, Melvin H
• Application Number:
  US15/768,275
• Publication Number:
  US 20180302504A1
• Time in Patent Office: 1,313 Days
• Field of Search: 709223
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols

Abstract

The method of the invention envisages estimation and learning of the state of the system using the data traffic of the network itself, with co-ordination of a node, selected as collector, which, in addition to its normal data-collection role, determines and changes dynamically the network-protocol stack used, for optimizing the performance of interest, where for this purpose said node, with a processing unit thereof, implements a computer program referred to as “protocol selector”, which: executes monitoring of the network state and collection of the data on the performance of the network itself; evaluates at periodic intervals the performance of the protocol in the last interval and executes a step of a reinforcement-learning algorithm at the end of which it evaluates whether to change or not the protocol for the next interval and resumes the main execution flow.

Claims

1. A device for selecting dynamically and autonomously in time the best solution to be used for the communication and the configuration that meets the user specifications, adapting autonomously and dynamically and in an effective way to the ever different and changeable conditions of the underwater environment, said device being suitable to be installed on the nodes and on the collector node of an underwater sensor network, equipped with one or more communication apparatuses that operate with different protocol stacks, wherein said device comprises:

a data-storage means where the data packets sent by the nodes are collected, said data packets having headers;

a plurality of connectors for the inter-connection of said device with one or more modems;

a processing unit;

a “

protocol selector”

computer program executed by said processing unit for determining and changing dynamically the network protocol stack as the current operating conditions of the network vary in order to optimize the performance of the application supported in terms of network latency, packet-delivery fraction, energy consumption, and/or a combination thereof, wherein said protocol selector computer program is constituted by the following modules;

a packet monitor module (module A), for analyzing the packets received by the collector node of said network for extracting the information necessary for;

(i) evaluating the performance of the current protocol; and

(ii) identifying possible changes in the conditions of the network;

a performance meter module (module C), for calculating the performance of the protocol currently in use;

a protocol-change manager module (module E), for managing the protocol change in the network, without interrupting operation thereof; and

a communication means for managing and enabling operation of said storage means, communication means, and data-processing means, wherein said protocol selector computer program further comprises the following modules;

a data analyser module (module B), for analyzing the data collected for identifying possible changes in the conditions of the network, said changes regard a different traffic in the network, the terms of amount of data per unit time, a variation in the quality of the acoustic channel, or a change in the size of the packets exchanged by the nodes; and

an optimizer module (module D), for executing a learning algorithm, to learn which is the optimal protocol stack for each state of the system, using for this purpose the results produced by the said performance meter (module C);

wherein the protocol selector module characterizes the operating state of the system through a triplet of values that summarizes the condition of the network at a given instant and that is defined as network state s=(λ

, q_snr, p_size), where q_snr is the mean signal-to-noise ratio, λ

is the network load, and p_size is the mean packet size; and

wherein, in order to carry out the monitoring the state, the headers of the network packets are extended so as to include the information necessary for identification of the state and evaluation of the protocol stack, to each transmitted packet k the node j adding the header field HDPRE=<

p_k^j,t_tx^j,t_k^j>

, where p_k^j is a progressive identifier of the packets sent by node k, t_tx^j is the total time of transmission of the node j in the current round, and t_k^j is the timestamp of the packet.

2. A method for enabling an underwater sensor network equipped with one or more communication apparatuses that operate with different protocol stacks, to select dynamically and autonomously in time the best solution to be used for the communication and the configuration that meets the user specifications, adapting autonomously and dynamically and in an effective way to the ever different and changeable conditions of the underwater environment, said method being characterized in that it comprises the steps of:

estimating and learning the state of the system, using the data traffic of the deployed system itself, with co-ordination of a node, selected as collector, the task of which is, in addition to its normal data-collection role, that of determining and changing dynamically the stack of network protocols used in order to optimize the performance features of interest,

where for this purpose said collector node, with a processing unit of its own, implements a “

protocol selector”

computer program, which comprises the following steps;

a) analysis of the packets received for extracting all the information necessary for;

i) evaluating the performance of the current protocol in use, and

ii) identifying possible changes in the system;

b) analysis of the data collected for identifying possible changes in the network, said changes possibly regarding a different traffic in the network, a variation in the quality of the acoustic channel, or else a change in the size of the packets exchanged by the nodes;

c) calculation of the performance of the protocol stack currently in use;

d) execution of a learning algorithm, for learning which is the protocol stack (steps 1 and

     2) optimal for each state of the system, using for this purpose the results produced by step a); and

e) management of the change of the protocol stack in the network, without interrupting operation thereof;

wherein in step a) the protocol selector characterizes the operating state of the system through a triplet of values that summarizes the condition of the network at a given instant and that is defined as network state s=(λ

, q_snr, p_size), where q_snr is the mean signal-to-noise ratio, λ

is the network load, and p_size is the mean packet size;

wherein the headers of the network packets are extended so as to include the information necessary for identification of the state and evaluation of the protocol stack, to each transmitted packet k the node i adding the header field HDPRE=<

p_k^j,t_tx^j,t_k^j>

, where p_k^j is a progressive identifier of the packets sent by node k, t_tx^j is the total time of transmission of the node j in the current round, and t_k^j is the timestamp of the packet.

3. The method according to claim 2, characterized in that the data-analysis module in step b), to detect even significant changes in the state of the network, resorts, for each of said three components of the state, mean signal-to-noise ratio, network load, mean packet size, to a change-detection algorithm of an adaptive type belonging to the CUSUM family [Mo08,CaTo12] combined with a low-pass filter (exponentially weighted moving average, EWMA) for monitoring the average of the values.

4. The method according to claim 2, characterized in that, if the protocol selector does not detect changes of the state, collection of the data proceeds up to the possible completion of the current evaluation interval;

if, instead, the state has changed, data collection is interrupted, the new state is detected, and the best protocol stack is chosen for the new conditions; and

once change of state is completed, a new interval of collection of statistics regarding the new state is started.

5. The method according to claim 2, characterized in that at the end of an i-th evaluation interval the performance features of the protocol are first analysed in terms of packet-delivery fraction r_i, energy consumption e_i, and network latency l_i in the interval just concluded, calculating these values starting from the information contained in the field HDPRE of the packets, as follows:

r_i is calculated as the ratio between the number of packets received in the interval just concluded and the total number of packets sent in the same interval, which for each node can be calculated starting from the header HDPRE using the unique progressive identifier of each packet;

l_i is calculated as mean network latency, the sum of the latencies of each packet received, divided by the total number of packets received, wherein the latency of each packet is obtained from the difference between the instant of receipt and the timestamp t_k^j); and

, finally;

e_i is calculated as the ratio between the total time spent by the nodes in transmission, by the sum of the values t^j_1x contained in the header HDPRE and the total number of data bits received;

starting from the indices r_i, l_i, and e_i, a single aggregate scalar index c_i is then calculated as linear combination of the various performance indices, appropriately normalized in the interval [0,1] and weighted according to the requirements of the application, where the normalization takes into account the maximum and minimum value that each index can assume, which may be precalculated via simulations, may be estimated, or may be based upon experience.

6. The method according to claim 2, characterized in that in the learning step the performance statistics of the protocol p_i used in the last interval are updated, for the current state of the system s=(λ

, q_snr, p_size), by re-calculating the mean value taking into account the aggregate index c_i just calculated;

the mean value of performance of the protocol p_i being calculated by averaging the values of performance of the protocol in the intervals, in which it has been used, possibly assigning a greater weight to the values of performance in the most recent intervals.

7. The method according to claim 2, characterized in that, following upon the learning step, it is evaluated which protocol stack to use in the next interval, interval i+1, with the system in the state s, where the solution proposed is based upon a general mathematical e-greedy reinforcement-learning technique known as n-armed bandit [SuBa98], so that the choice falls on the protocol stack that has guaranteed the best level of performance for the current state.