Granted Patent B2

US 8,249,094 · App. 11/501,388 · Granted Aug 21, 2012

Abstract

Claims (108)

1. A method of simulating communications among a plurality of nodes via a communication channel, comprising:

defining a model of the communication channel that is common to the plurality of nodes and is configured to receive a measure of contention and to provide therefrom a throughput measure,

simulating, on a simulation system, receipt of messages at a source node, for transmission to a destination node,

determining, on the simulation system, the measure of contention for the communication channel,

determining, on the simulation system, a service delay based on the model of the communication channel and the measure of contention,

simulating, on the simulation system, communication of at least one message from the transmitter to the receiver via the communication channel at a time of completion of transmission that depends upon the service delay,

wherein the communication channel is characterized as having a total available bandwidth that decreases with increased contention, and the model is configured to provide the throughput measure based on the total available bandwidth, which is determined based on the measure of contention.

2. The method of claim 1 , wherein the model of the communication channel includes values of a throughput parameter that are dependent upon a number of contenders for the communication channel, and determining the service delay is based on a mapping of the measure of channel contention to the number of contenders to determine the corresponding throughput measure upon which the service delay depends.

3. The method of claim 2 , wherein the service delay is based upon a size of each message divided by the throughput measure.

4. The method of claim 2 , wherein the model of the communication channel is configured to determine a likelihood of dropping each message based on the measure of contention; the method including:

determining the likelihood of dropping each message, based on the model of the communication channel and the measure of contention, and

simulating non-communication of at least one message from the transmitter to the receiver based on the likelihood of dropping the message.

5. The method of claim 4 , wherein the likelihood of dropping each message is based on a number of contenders within a contention domain associated with the communication channel.

6. The method of claim 5 , wherein the contention domain includes each other node that can reach the source node during a giving time period.

7. The method of claim 5 , including determining a relation between the likelihood of dropping each message and the number of contenders based on at least one of:

empirical evidence,

measurements based on actual communications, and

measurements based on other simulations of communication behavior in a single contention domain.

8. The method of claim 2 , including determining a number of other nodes reachable by the source node, and wherein the measure of contention is based on the number of other nodes reachable by the source node.

9. The method of claim 1 , including determining a number of other nodes reachable by the source node, and wherein the measure of contention is based on the number of other nodes reachable by the source node.

10. The method of claim 9 , wherein the model of the communication channel is configured to determine a likelihood of dropping each message based on the measure of contention; the method including:

determining the likelihood of dropping each message, based on the model of the communication channel and the measure of contention, and

simulating non-communication of at least one message from the transmitter to the receiver based on the likelihood of dropping the message.

11. The method of claim 1 , including simulating communication of other messages on the communication channel from other transmitters, and simulating non-communication of at least one message from the transmitter to the receiver based on a first time interval of communication of the at least one message from the transmitter to the receiver and a second time interval of the communication of the other messages on the communication channel.

12. The method of claim 11 , wherein the first time interval occurs at an end of the service delay.

13. The method of claim 12 , wherein the first time interval is substantially shorter than the service delay.

14. The method of claim 13 , wherein:

the first time interval is based on a communication rate of the communication channel, and

the throughput measure includes a throughput rate of the communication channel.

15. The method of claim 11 , wherein the model of the communication channel includes:

a first parameter that facilitates the determination of the service delay and

a second parameter that facilitates determination of the first time interval.

16. The method of claim 15 , including determining a relation between the throughput measure and the contention measure based on at least one of:

empirical evidence,

measurements based on actual communications, and

measurements based on other simulations of communication behavior in a single contention domain.

17. The method of claim 15 , wherein the first parameter includes the throughput measure that is based on the measure of contention.

18. The method of claim 17 , wherein the second parameter includes an overhead that is based on the measure of contention.

19. The method of claim 1 , including determining a location associated with the source node, and wherein the measure of contention is based on the location associated with the source node.

20. The method of claim 1 , including determining a distance between the source node and each of the plurality of nodes, and wherein the measure of contention is based on the distance between the source node and each other node of the plurality of nodes.

21. The method of claim 20 , including determining a change of location of at least one of the plurality of nodes, and updating the set of reachable nodes if the change of location exceeds a given distance threshold.

22. The method of claim 21 , including recording a time of occurrence of the updating of the set of reachable nodes for the source node, and precluding a subsequent update of the set of reachable nodes for the source node based on the time of occurrence of the updating.

23. The method of claim 1 , including:

determining a first set of distances between the source node and each other node of the plurality of nodes,

determining a second set of distances between the destination node and each other node of the plurality of nodes,

identifying a set of hidden nodes, which are nodes that are not within a range of the source node, but able to interfere with the destination node based on the first and second set of distances, and

simulating non-communication of at least one message from the transmitter to the receiver based the set of hidden nodes.

24. The method of claim 23 , including simulating communication of other messages on the communication channel from the hidden nodes transmitters, and wherein the simulating of non-communication of at least one message from the transmitter to the receiver is based on a first time interval of communication of the at least one message from the transmitter to the receiver and a second time interval of the communication of the other messages on the communication channel.

25. The method of claim 24 , wherein the model of the communication channel includes:

a first parameter that facilitates the determination of the service delay and

a second parameter that facilitates determination of the first time interval.

26. The method of claim 1 , wherein the simulating of communications from each node of the plurality of nodes includes determining a service delay based on the same model of the communication channel.

27. A method of simulating communications among a plurality of nodes via a communication channel, comprising:

defining a model of a MAC layer for each of the plurality of nodes that facilitates modeling of a dynamic state of the communication channel that varies during simulation of the communications;

defining a model of the communication channel that is common to the plurality of nodes and includes a channel state variable as an input parameter and provides a throughput measure as an output parameter;

simulating, on a simulation system, communication of application messages from source nodes to destination nodes by executing the model of the MAC layer at each source node for each of the application messages;

wherein:

executing the model of the MAC layer for each message includes:

determining a current state of the communication channel,

using the model of the communication channel to determine a current throughput measure based on the current state of the communication channel, the communication channel being characterized as having a total available bandwidth that decreases with increased contention, and the model being configured to provide the throughput measure based on the total available bandwidth, which is determined based on the current state of the communication channel, and

determining a service delay based on the current throughput measure; and

simulating, on the simulation system, the communication of the message is based on the service delay.

28. The method of claim 27 , wherein the state of the communication channel is dependent upon effects of a physical layer.

29. The method of claim 28 , wherein the effects of the physical layer are dependent upon locations of some or all of the source and destination nodes.

30. The method of claim 27 , wherein the state of the communication channel includes a number of nodes contending for the communication channel.

31. The method of claim 27 , wherein the model of the communication channel also provides one or more of the following as other output parameters that are based on the state of the channel:

a likelihood of dropping messages, and

a retransmission rate, and

simulating the communication of the messages is based on one or both of these other output parameters.

32. The method of claim 31 , wherein the state of the communication channel includes a number of nodes contending for the communication channel.

33. The method of claim 27 , wherein the model of the communication channel is based on at least one of:

empirical evidence,

measurements based on actual communications, and

measurements based on other simulations of communication behavior in a single contention domain.

34. The method of claim 27 , wherein executing the model of the MAC layer for each message includes determining each other node that can reach the source node during a giving time period.

35. The method of claim 27 , wherein:

executing the model of the MAC layer for each message from each source node to each destination node includes:

determining a first set of distances between the source node and each other node of the plurality of nodes,

determining a second set of distances between the destination node and each other node of the plurality of nodes, and

identifying a set of hidden nodes, which are nodes that are not within a range of the source node, but able to interfere with the destination node, based on the first and second set of distances, and

simulating the communication of the messages includes simulating non-communication of at least one message based the set of hidden nodes.

36. A simulation system for simulating communications among a plurality of nodes in a network that includes:

a model of a communication channel that is common to the plurality of nodes and includes a channel state variable as an input parameter and provides a throughput measure as an output parameter,

a model of a MAC layer for each of the plurality of nodes that includes a dynamic state of the communication channel that varies during simulation,

wherein the model of the MAC layer is configured to facilitate simulation of communication of a message from a source node to a destination node during a current simulation time period by causing the simulation system to:

determine a current state of the communication channel,

use the model of the communication channel to determine a current throughput measure based on the current state of the communication channel, the communication channel being characterized as having a total available bandwidth that decreases with increased contention, and the model being configured to provide the throughput measure based on the total available bandwidth, which is determined based on the measure of contention,

determine a service delay based on the current throughput measure, and

simulate the communication of the message based on the service delay.

37. The simulation system of claim 36 , wherein the state of the communication channel is dependent upon simulated effects of a physical layer.

38. The simulation system of claim 37 , wherein the effects of the physical layer are dependent upon simulated locations of the source and destination nodes.

39. The simulation system of claim 36 , wherein the state of the communication channel includes a measure of the plurality of nodes contending for the communication channel.

40. The simulation system of claim 36 , wherein

the model of the communication channel also provides one or more of the following as other output parameters based on the state of the communication channel:

a likelihood of dropping messages, and

a retransmission rate, and

the simulation system is configured to simulate the communication of the messages based on one or both of these other output parameters.

41. The simulation system of claim 40 , wherein the state of the communication channel includes a measure of the plurality of nodes contending for the communication channel.

42. The simulation system of claim 36 , wherein the model of the communication channel is based on at least one of:

empirical evidence,

measurements based on actual communications, and

measurements based on other simulations of communication behavior in a single contention domain.

43. The simulation system of claim 36 , wherein the model of the MAC layer is configured to cause the simulation system to determine each other node of the plurality of nodes that can reach the source node during the current simulation time period.

44. The simulation system of claim 36 , wherein the model of the MAC layer is configured to cause the simulation system to:

determine a first set of distances between the source node and each other node of the plurality of nodes,

determine a second set of distances between the destination node and each other node of the plurality of nodes, and

identify a set of hidden nodes, which are nodes that are not within a range of the source node, but able to interfere with the destination node, based on the first and second set of distances, and

simulate the communication of the message, including non-delivery of at least one message based the set of hidden nodes.

Assignments (18)