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 , where 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 mesh network. Using Manhattan distance we can determine the distance from a specified node to all other nodes in the network.
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, , is used to compute the total hop count of a row relative to a node.
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 . This is expressed as the function .
Adding and together will provide us with the TotalHopCount for specified node. Now we must average over all possible node pairs, , and as assumed we ignore hop counts between a node and itself, , therefore the total pairs we average over is expressed as . Using we compute the average hop count of a 2 dimensional network with an even k.
derivation of is omitted due to length.