CoderFrank

Average Hop Count of a Mesh Network

Hi,

I haven’t posted in a while, and I thought I’d update my blog with a fun problem I worked on for my Architecture II course. I present my solution for various reasons, but mainly academic. The problem was to prove the average hop count of a 2 dimensional mesh network is equal to Latex formula, where Latex formula is the width and height of the mesh network and is considered even.

In order to keep this simple I added an image of a Latex formula mesh network. Using Manhattan distance we can determine the distance from a specified node to all other nodes in the network.

Screen Shot 2015-11-23 at 4.56.29 PM

An assumption is made to ignore the node used to compute the total hop count. The total hop count per row can be computed by adding the hop count on both sides of the specified node. Using mathematical notation the following function, Latex formula, is used to compute the total hop count of a row relative to a node.
Latex formula
Next we consider the rows above and below the node. As the image suggests, rows above and below is the total relative rows multiplied by k and added to Latex formula. This is expressed as the function Latex formula.

Latex formula

Adding Latex formula and Latex formula together will provide us with the TotalHopCount for specified node. Now we must average over all possible node pairs, Latex formula, and as assumed we ignore hop counts between a node and itself, Latex formula, therefore the total pairs we average over is expressed as Latex formula. Using Latex formula we compute the average hop count of a 2 dimensional network with an even k.

Latex formula
derivation of Latex formula is omitted due to length.

Latex formula
Latex formula
Latex formula
Latex formula
Latex formula Latex formula