# On Modeling and Analysis of MIMO Wireless Mesh Networks with Triangular Overlay Topology

Authors: Zhanmao Cao; Chase Q. Wu; Yuanping Zhang; Sajjan G. Shiva; Yi Gu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Multiple input multiple output (MIMO) wireless
mesh networks (WMNs) aim to provide the last-mile broadband
wireless access to the Internet. Along with the algorithmic development
for WMNs, some fundamental mathematical problems
also emerge in various aspects such as routing, scheduling, and
channel assignment, all of which require an effective mathematical
model and rigorous analysis of network properties. In
this paper, we propose to employ Cartesian product of graphs
(CPG) as a multichannel modeling approach and explore a
set of unique properties of triangular WMNs. In each layer of
CPG with a single channel, we design a node coordinate scheme
that retains the symmetric property of triangular meshes and
develop a function for the assignment of node identity numbers
based on their coordinates. We also derive a necessary-sufficient
condition for interference-free links and combinatorial formulas
to determine the number of the shortest paths for channel
realization in triangular WMNs.


---

## Body

## 1. Introduction

The WiMax group advocated the last-mile broadband services, IEEE 802.16 Standard [1], which defines broadband backbones as wireless mesh networks (WMNs). Such networks typically consist of two types of nodes, that is, base station (BS) and subscriber station (SS). BS is a wireless gateway connected to the Internet, while SS is a node that acts as a relay station. In multiple input multiple output (MIMO) WMNs, all nodes are equipped with multiple interfaces and support both multicast and mesh modes. Particularly, in a mesh mode, nodes can communicate with neighbors without the help of BS and the relay strategy provides an economical way to expand the mesh covering area. MIMO WMNs (in the rest of the paper, we use the term WMNs for conciseness) are well recognized as an efficient extension to the Internet backhaul [2].WMNs possess some inherent characteristics that are different from ad hoc or wireless sensor networks. Since the nodes in WMNs are almost fixed and typically powered by electrical wires, the links or routing paths in WMNs generally last longer than those in mobile ad hoc networks. Also, every node in WMNs typically has nonzero traffic requests because it needs to route aggregated traffic from the terminal devices in its region for either upload or download. The topology of WMNs may be determined based on the predicted traffic requests or geographical environments. Since both BS and SS can be considered static, it is reasonable to view the mesh topology as a fixed graph.The rapidly growing demand for ubiquitous Internet access requires an effective mathematical model for WMNs as it may simplify the tasks of routing, scheduling, and channel assignment. To achieve a maximum fair usage of multiple channels in WMNs, it is important to employ an efficient channel allocation scheme and an appropriate overlay graph topology for a given area [3]. In [4], the virtual topology is viewed as CPG to simplify the channel assignment problem through a graph. In addition, the CPG model also brings convenience for the analysis of routing and scheduling in WMNs. As nodes are static in WMNs, they can be identified geographically through their coordinates [5]. Therefore, the routing and scheduling problems can be analyzed using the node coordinates. Interference is another fundamental issue in either scheduling or routing, and the properties of interference under a given coordinate scheme, if defined properly and described rigorously, may bring benefits to resource utilization and interference avoidance.In this work, we use CPG as a modeling approach and explore a set of unique properties of WMNs with a triangular topology. In each layer of CPG with a single channel, the network topology is a planar mesh. Our work makes several theoretical contributions to the analysis of WMN properties: (i) we design a coordinate scheme that retains the symmetric property of triangular meshes and develop a function to assign a unique identity number to a specific wireless node based on its coordinates. (ii) We derive a necessary-sufficient condition for interference-free links under the proposed node coordinate scheme. (iii) We derive combinatorial formulas in terms of the number of transceivers and channels to determine the number of the shortest paths for channel realization in triangular WMNs.The rest of the paper is organized as follows. Section2 surveys related work. Section 3 presents a channel-layered CPG model with emphasis on interference detection. In each layer of CPG, we propose a coordinate scheme, named parallel cluster coordinate, derive a necessary-sufficient condition for interference avoidance, and develop a function for node identity number assignment to support efficient WMN maintenance and administration. Section 4 derives formulas for determining the number of the shortest paths in WMNs.


## 2. Related Work

We conduct a brief survey of work directly related to mathematical models for WMNs.In the past decade, most efforts in WMN topology were focused on interference and performance in planar meshes [6–9]. With geographical information from satellite or control channel communications, it is relatively easy to acquire a planar topology since the nodes in WMNs are almost static. For example, in IEEE Standard 802.21 for media-independent handover, Media Independent Information Service (MIIS) stores the geographical information of all access network operators available in a particular region [10].Square and hexagonal meshes have been proposed to act as wireless broadband backbones [11]. However, they are less competitive than triangular meshes, as the latter outperforms the former and other random meshes in terms of various performance metrics such as coverage area, link quality, per-user fair rate, and node density [12]. Hong and Hua conducted a comparative evaluation of the throughput performance between square, hexagonal, and triangular meshes. Their experiments showed that triangular meshes achieve higher throughput than others in several cases, and their total throughput does not vary significantly in response to topology changes in large wireless networks with a constant density [13]. Therefore, we also adopt a triangular mesh topology in our model.A unified network model based on super graph may further facilitate the analysis of various aspects of WMNs such as interference, scheduling, routing, and channel assignment. However, research efforts along this line are still quite limited. Several researchers considered some of these aspects simultaneously [3, 11, 14], which motivates us to design a unified model for WMNs.In a given network topology, a properly designed coordinate scheme may facilitate link interference detection and path finding. In hexagonal meshes, Chin et al. proposed a node coordinate scheme with three parallel line clusters [15], where a node is represented by a 3-tuple. In triangular meshes consisting of BS nodes with a node degree of six, Cao et al. proposed two BS-centered coordinate schemes [5] and explored interference and link groups in each of these schemes. Furthermore, in addition to coordinates, a router should also be assigned a unique identity number to support convenient simulation, administration, and maintenance. In [4, 5], Cao et al. also represented the coordinates of a node by a 3-tuple but did not tackle the identity number assignment problem.The performance of WMNs is largely affected by link interference. Most research efforts on this subject have been made through generic methods or experimental studies, instead of conclusive results in the form of necessary-sufficient conditions [3, 16, 17]. In our work, we attempt to design a suitable node coordinate scheme and then model the interference in WMNs as a specific checking list based on set theory.Routing in WMNs is a 2-step procedure, that is, path finding followed by channel assignment. One basic approach to find an alternative interference-free path is to count the number of shortest paths and the number of all possible channel assignment schemes. A tree-like path finding scheme is proposed in [6] without any node coordinate. Cao and Xiao proposed path counting formulas for a source-destination pair in square grids [18], while the path counting problem in triangular meshes is still left unexplored. In our work, based on the proposed CPG model and coordinate scheme, we tackle this problem in triangular meshes with multiple channels and interfaces. Channel assignment is another important problem involving several network layers in WMNs, which is essentially an NP-complete edge coloring problem [14, 19].


## 3. A Channel-Layered Graph Model

As massive MIMO is on its way from theory to realistic deployment, one of the key problems is the interchannel cooperation, which calls for the development of sophisticated analytical channel models. Larsson et al. provide an overview of massive MIMO and motivate researchers to develop channel models capturing the essential channel behaviors despite their limitations [20]. For example, the Kronecker model, which is widely used to model channel correlation, is not an exact representation of reality but provides a useful model for certain types of analysis.WMNs are conventionally modeled by a directed graph where a directed edge between two neighbor nodes represents a communication link over a specific channel. Since a node equipped withξ transceivers may have (at most) ξ simultaneous links over ξ orthogonal channels (assuming that more than ξ channels are available), we can split a physical node into ξ fully connected virtual nodes, each of which is equipped with a single transceiver. This way, we are able to represent the original WMN as ξ identical layers of networks, each of which operates over a different channel.


### 3.1. Cartesian Product of Graphs

The topology-based modeling approach has been commonly used in wireless networks for various purposes, but often in a planar view [8, 12, 14], and most of the discussions on scheduling, routing, and channel assignment are also based on a planar topology [6, 11, 13, 17]. The recent development of MIMO WMNs calls for a suitable model to describe MIMO-specific properties and understand the cooperative activities across different interfaces over multiple channels [20]. The planar topology can be used to determine the internode interference [8] but is insufficient to provide a visual representation for analyzing the cooperation between links or channels. On the other hand, modeling MIMO WMNs as a super graph still remains largely unexploited except the work in [4]. In this paper, our goal is to develop an effective model to facilitate the analysis of MIMO channel cooperation.We propose to employ the CPG to model WMNs by combining a triangular mesh of physical nodes and a graph of fully connected virtual nodes. Together with the coordinates of triangular overlay nodes, the CPG model provides a convenient way to analyze the properties of interference avoidance, channel assignment, and routing path counting. This model retains the independence between orthogonal channels while providing a general approach to analyzing link behaviors over multiple channels.Cartesian Product of Graphs. Given two graphs G and H, the Cartesian product G
×
H is a graph such that(i)
the graphG
×
H has a vertex set V
(
G
)
×
V
(
H
); that is, a vertex in G
×
H is denoted by a pair (
v
,
v
′
), v
∈
V
(
G
), and v
′
∈
V
(
H
);
(ii)
any two nodes(
u
,
u
′
) and (
v
,
v
′
) and u
,
v
∈
V
(
G
) and u
′
,
v
′
∈
V
(
H
) are adjacent in G
×
H, if and only if one of the following holds: (a) u
=
v and u
′ is adjacent to v
′ in H, or (b) u
′
=
v
′ and u is adjacent to v in G.For illustration, Figure1(a) shows a mesh network of five physical nodes (left side) and a graph of two connected virtual nodes (right side) corresponding to a physical node equipped with two transceivers, each operating on a different channel c
1 or c
2. Figure 1(b) shows a channel-layered virtual topology of the original mesh network modeled by CPG.Figure 1
The CPG-modeled virtual topology of a physical network with five physical nodes and two channels.In this example, the CPG of two graphs in Figure1(a) results in a two-layered graph in Figure 1(b). A solid directed edge in the top or bottom planar meshes in Figures 1(b), 1(c), and 1(d) represents a communication link l
=
(
S
,
R
)
c, transmitting data from node S to node R over a channel c, while a dashed edge has a conflict with some active links.The maximum possible number of concurrent active links on a given channel in a mesh is largely affected by the selection of the senders. As shown in Figure1(b), when node A in the top layer is sending data on channel c
1, the three neighbors of A, that is, nodes B, C, and D, in the same layer (over channel c
1) cannot send data. Furthermore, node E can be selected as a sender, but neither of its neighbors, that is, nodes C and D, can receive data from E without interference, illustrated as the dashed directed edges in Figure 1(c). In this case, there is no other active link except (
A
,
B
)
c
1. However, if we choose the initial senders properly, as shown in Figure 1(d), there could exist two concurrent interference-free links on channel c
i,  i
=
1,2, that is, (
B
,
A
)
c
i and (
E
,
D
)
c
i.Since all active links must be interference-free on the same channel at the same time, links are generally sparsely distributed in a planar mesh with respect to a certain channel. Note that more links mean better service to traffic requests. The CPG model allows us to consider concurrent paths in multiple layers over different channels through radio cooperation among channel layers for a given traffic task, hence providing more capacity and higher throughput compared to the situation with a single channel and radio. This is consistent with the experimental results presented by Draves et al. [16]. The proposed CPG model is aligned well with existing research in terms of interference relation, link activity, and network throughput, as well as routing and scheduling [6, 7, 14, 19, 21] and enables us to conduct deeper theoretical analysis of WMNs.One advantage that CPG brings is to simplify the expression of multichannel links. Since different layers (operating on different channels) are of the same topology, the scheduling strategy derived in one layer is readily applicable to another layer. For example, there exists a certain link distribution pattern among concurrent links. In CPG, it is obvious that such an interference-free link distribution pattern on one channel also exists on others.


### 3.2. Coordinate Scheme

A well-designed coordinate scheme may facilitate the analysis of WMNs. Since all channel layers are of the same topology, we only need to design the coordinate scheme for one layer or channel. The channel information can be added to the node coordinates to uniquely identify a specific layer.Chin et al. proposed a coordinate scheme in hexagonal cellular networks where each node has a degree of three [15]. Inspired by their work, we propose a parallel cluster coordinate scheme in a local triangular mesh with one BS node and a number of SS nodes with a degree of six. This scheme can be readily extended to larger networks with multiple BSs by inserting the BS information to the node coordinates.


#### 3.2.1. Parallel Cluster Coordinate Scheme

In a triangular mesh, we first define three clusters of parallel lines along three different directions, that is, north-east, east, and south-east. Since each node is a point intersected by three lines, each from one of the three clusters, we propose a parallel cluster coordinate scheme (PCCS), which uses a 3-tuple(
i
,
j
,
k
) to represent the coordinates of a node intersected by the ith, jth, and kth line in the corresponding clusters [5]. As illustrated in Figure 2, the BS node with the coordinates (
0,0
,
0
) is located at the center, and the SS nodes A, B, C, D, E, and F, which are one hop away from the BS node, have the coordinates A
=
(
1,0
,
1
), B
=
(
0,1
,
1
), C
=
(
-
1
,
-
1,0
), D
=
(
-
1,0
,
-
1
), E
=
(
0
,
-
1
,
-
1
), and F
=
(
1,1
,
0
).Figure 2
The parallel cluster coordinate scheme.Note that not every combination of three integers can represent a node in a triangular mesh because some lines defined by combinatorial 3-tuples do not intersect at a common point. We summarize such lines as follows:(1)
Ω
=
(
i
-
1
,
j
-
1
,
k
)
,
(
i
+
1
,
j
+
1
,
k
)
,
(
i
,
j
-
1
,
k
+
1
)
,
p
p
(
i
,
j
+
1
,
k
-
1
)
,
(
i
+
1
,
j
,
k
-
1
)
,
(
i
-
1
,
j
,
k
+
1
)
.Under the proposed PCCS scheme, for a given sender(
i
,
j
,
k
), there are six possible receivers, which form its neighbor set N
b
(
i
,
j
,
k
):
(2)
N
b
i
,
j
,
k
=
(
i
-
1
,
j
+
1
,
k
)
,
(
i
+
1
,
j
-
1
,
k
)
,
p
p
p
(
i
,
j
+
1
,
k
+
1
)
,
(
i
,
j
-
1
,
k
-
1
)
,
p
p
p
(
i
+
1
,
j
,
k
+
1
)
,
(
i
-
1
,
j
,
k
-
1
)
.PCCS retains the symmetric nature of a triangular mesh and facilitates the calculation of the distance between a pair of nodes.


#### 3.2.2. Symmetric Property of PCCS

In PCCS, the coordinates of any two nodes that are symmetric with respect to the central BS node located at(
0,0
,
0
) are negated. For example, the pairs of nodes A and D, B and E, and C and F in Figure 2 are symmetric, and their coordinates are negated from their counterparts.The symmetric properties of CPG and Cayley graph have been well studied [22]. According to the vertex/edge transitive properties, a link group can be transited to generate another one in any layer.Similarly, due to the symmetric property, we are able to transform a link group to another one through rotation. For example, link group of(
(
0,2
,
2
)
,
(
0,1
,
1
)
)
c and (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c is interference-free. After a clockwise rotation of π
/
3, a new group of interference-free links is of (
(
2,0
,
2
)
,
(
1,0
,
1
)
)
c and (
(
0
,
-
2
,
-
2
)
,
(
0
,
-
1
,
-
1
)
)
c, respectively. With another clockwise rotation of π
/
3, the derived interference-free links are (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c and (
(
-
2,0
,
-
2
)
,
(
-
1,0
,
-
1
)
)
c, respectively. Note that the rotation operation is edge transitive, and it generates a new link group because of the symmetric property.


#### 3.2.3. Distance between Two Nodes

As most traffic is upload/download (to/from BS), we need to count the number of hops from a router node to BS in PCCS. We have the following properties.Property 1.
In triangular WMNs with PCCS, the minimum numberħ of hops from A
=
(
i
,
j
,
k
) to BS
=
(
0,0
,
0
) is
(3)
ħ
=
i
+
j
+
k
2
=
max
⁡
i
,
j
,
k
which is consistent with the one in [4].Property 2.
Suppose that BS is positioned at an arbitrary location(
i
0
,
j
0
,
k
0
), instead of (
0,0
,
0
). Node (
i
,
j
,
k
) can be translated to (
i
,
j
,
k
)
-
(
i
0
,
j
0
,
k
0
) by a translation function:
(4)
δ
:
(
i
,
j
,
k
)
⟶
i
,
j
,
k
-
i
0
,
j
0
,
k
0
.In general, suppose that(
i
0
,
j
0
,
k
0
) is the destination of a traffic path; we may virtually view (
i
0
,
j
0
,
k
0
) as the BS node after applying the translation of 4. Then, the formula in 3 may facilitate further analysis.Given two nodesA
=
(
i
1
,
j
1
,
k
1
) and B
=
(
i
2
,
j
2
,
k
2
) in PCCS, the distance between A and B, denoted by d
(
A
,
B
), is theminimum number of hops between them, which is calculated as d
(
A
,
B
)
=
(
|
i
1
-
i
2
|
+
|
j
1
-
j
2
|
+
|
k
1
-
k
2
|
)
/
2.


#### 3.2.4. Mapping to 2D Points

In order to draw a planar mesh, we need to map 3-tuple coordinates(
i
,
j
,
k
) to 2-dimensional (2D) points (
x
,
y
). To do this, we first overlap a rectangular plane coordinate system to the PCCS triangular mesh. Let the x-axis overlap the axis j
=
0 while keeping the positive rightward direction. Meanwhile, the y-axis passes the BS node and is vertical to the line j
=
0 with a positive upward direction. Then, we can determine (
x
,
y
) by projecting (
i
,
j
,
k
) onto axes x and y. The PCCS supports a function f mapping (
i
,
j
,
k
) to (
x
,
y
) as follows.Property 3.
A one-to-one mapping functionf maps node coordinates (
i
,
j
,
k
) in PCCS to 2D coordinates (
x
,
y
):
(5)
x
,
y
=
f
i
,
j
,
k
=
x
=
i
+
k
2
y
=
j
.For example, node(
0,1
,
1
) is mapped to (
1
/
2,1
), and (
-
1,3
,
2
) is mapped to (
1
/
2,3
). If a node is on the y-axis, i
=
-
k always holds. For example, (
-
1,2
,
1
) is mapped to (
0,2
). If node is located on k
=
0 in PCCS, x
=
i
/
2. For example, (
-
2,2
,
0
) is mapped to (
-
1,2
). This property facilitates the plotting of a triangular mesh in PCCS.


### 3.3. Interference-Free Conditions

To analyze the interference between links, we need to consider node interference relations, which are critical to scheduling links in WMNs. As interference is an inherent nature for radio media, the wireless communication performance may be severely degraded if radios operate without a proper scheduling scheme [17].Minimizing interference has been extensively investigated in the literature [9, 17]. Subramanian et al. discussed channel assignment in a multiradio situation [9]. Tan et al. designed algorithms to set up a skeleton of minimum interference for a single channel [17]. Scheduling links in a cooperative way will improve the energy efficiency and reduce collision. These discussions assume variable transmitting power or interface channel switching. However, the variation of transmitting power may lead to the variation of network topology, which may cause changes in the interference relation. Xu et al. use a sensing scheme to achieve power efficiency for convergence communication [23]. Their method can help set the initial power in an almost-static WMN topology while promising interference-free cognitive access with link status as busy or idle.When senderS is sending over channel c
0, neither can S receive data over channel c
0, nor can its neighbors in its effective radio coverage send data. If a valid neighbor node R receives data over channel c
0, we have a link (
S
,
R
)
c
0. Furthermore, the neighbors of receiver R cannot send data over channel c
0 at the same time. Therefore, to be link interference-free in multiradio multichannel environments using PCCS, we need to consider three classes of node interferences: sender-to-sender, receiver-to-receiver, and sender-to-receiver.


#### 3.3.1. Sender-to-Sender

Given a certain channel, any two senders must be at least two hops away in a triangular mesh to avoid mutual interference, which could help construct an interference-free candidate set for possible senders.Definition 1.
A router setS
C is called a sender candidate set if every two nodes in S
C are at least two hops away.Given two nodesS
i
=
(
a
,
b
,
c
) and S
j
=
(
d
,
e
,
f
) in S
C, the distance between them must satisfy d
(
S
i
,
S
j
)
≥
2.For a given nodeS
j
∉
S
C, we can add S
j to S
C only if it is at least two hops away to any node S
i in S
C. We have the following necessary condition on interference-free links:
(6)
d
S
i
,
S
j
=
a
-
d
+
b
-
e
+
c
-
f
2
≥
2
.


#### 3.3.2. Receiver-to-Receiver

Two nodesR
i and R
j can each act as a receiver simultaneously if they have a distance larger than 1. Similar to the sender candidate set, we use R
C to denote a receiver candidate set, in which any two nodes R
i
=
(
l
,
m
,
n
) and R
j
=
(
u
,
p
,
q
) satisfy the following condition:
(7)
d
R
i
,
R
j
=
l
-
u
+
m
-
p
+
n
-
q
2
≥
1
.Note that bothS
C and R
C are candidate sets, and the actual sender and receiver sets are a subset of S
C and R
C, respectively. The relations between nodes largely depend on the previous selected links.Property 4.
If links(
S
1
,
R
1
)
c and (
S
2
,
R
2
)
c can be scheduled at the same time, then d
(
S
1
,
S
2
) must satisfy condition 6 and d
(
R
1
,
R
2
) must satisfy condition 7.Note that Property4 is only a necessary condition for interference-free links.


#### 3.3.3. Sender-to-Receiver

Given a certain channel, a node cannot receive data if it is in the effective radio range of the sender of any other active link; otherwise, interference occurs. If two linksl
i and l
j (i
≠
j) coexist, the nodes involved in these two links must satisfy the following condition:
(8)
d
S
i
,
R
j
=
a
-
u
+
b
-
p
+
c
-
q
2
>
1
,
i
≠
j
,
where S
i is the sender of link l
i and R
j is the receiver of link l
j.For example, in Figure1(d), since A’s neighbor D does not conflict with link (
B
,
A
)
c
1, D can be a receiver of another link (
E
,
D
)
c
1.We summarize three necessary conditions for link coexistence in the aforementioned three classes in Table1.Table 1
Conditions for simultaneous links over one channel.
Three neighbor pairs
Link interference-free conditions
Nodes
Nodes
Necessary
Sufficient
inS
C
inR
C
condition
condition
S
i, S
j
∀
i
≠
j, d
(
S
i
,
S
j
)
≥
2 (1)
R
i, R
j
∀
i
≠
j, d
(
R
i
,
R
j
)
≥
1 (2)
(1) ∧ (2) ∧ (3)
S
i
R
j
∀
i
≠
j, d
(
S
i
,
R
j
)
>
1 (3)We have the following theorem.Theorem 2.
Two linksl
i and l
j can be simultaneously scheduled (coexist) on the same channel, if and only if they satisfy all of the three necessary conditions in Table 1.Theorem2 is based on the PCCS scheme and the set theory. As long as the PCCS node coordinates are given, we are able to determine the interference between links. These known conditions are helpful to find as many links as possible, while contributing to concurrent central scheduling.


### 3.4. Transformations of Link Groups

We attempt to find as many coexisting links as possible in a given local area. Since a link can be established only between a valid sender candidate and a valid receiver candidate, the actual (final) scheduled link set is a subset ofS
C
×
R
C. Generally, coexisting links are sparsely distributed in the network. Based on a known group of coexisting links around one triangle, we wish to obtain a new group of coexisting links through certain transformations.Starting from a linkl
1
=
(
S
1
,
R
1
)
c
1, where S
1
=
(
i
,
j
,
k
) and R
1
=
(
i
,
j
+
1
,
k
+
1
), we want to set up a dense link group in a local area. The set of S
1’s neighbor nodes is N
b
(
S
1
)
=
{
v
∣
d
(
v
,
(
i
,
j
,
k
)
)
≤
1
,
v
∈
V
}. The set of R
1’s neighbor nodes is N
b
(
R
1
)
=
{
v
∣
d
(
v
,
(
i
,
j
+
1
,
k
+
1
)
)
≤
1
,
∀
v
∈
V
}. As any neighbor node of the sender or the receiver of an active link should remain silent if it does not receive data from the sender S
1, to avoid interference with l
1, nodes in N
b
(
i
,
j
,
k
)
∪
N
b
(
R
1
) cannot send data on c
1 when l
1 is active.To expand the active link group containingl
1
=
(
S
1
,
R
1
)
c
1, two nodes S
2
=
(
i
,
j
+
3
,
k
+
3
) and R
2
=
(
i
,
j
+
2
,
k
+
2
), which are not in N
b
(
S
1
) and N
b
(
R
1
), may negotiate for a new link. If successful, (
S
2
,
R
2
)
c
1 is added to the active link group. According to the conditions in Theorem 2, link l
2
=
(
S
2
,
R
2
)
c
1 can coexist with l
1.Any node inN
b
(
R
1
)
∪
N
b
(
R
2
) cannot be a new sender, except S
1 and S
2. However, it is completely different on the receiver side, where one node may be the receiver of a new link, even if it is in N
b
(
R
1
)
∩
N
b
(
R
2
). For example, in Figure 3, S
3
=
(
i
-
2
,
j
+
3
,
k
+
1
) and R
3
=
(
i
-
1
,
j
+
2
,
k
+
1
) form a new link l
3
=
(
S
3
,
R
3
)
c
1, which can coexist with l
1 and l
2. Around the central triangle in Figure 3, we find three interference-free links coexisting over one channel.Figure 3
Coexisting links in a local area.Although the three nodes of the central triangle are involved in three active links as shown in Figure3, neither of these three nodes can act as a sender while the other two are receiving data from their respective senders. To obtain the same number of new coexisting links, we need to keep the receivers unchanged, while considering a certain switching to the three senders of active links l
1, l
2, and l
3.By passing the sending token from the current sender to its neighbor node clockwise while keeping the original receiver, we are able to establish three possible new links:(9)
l
1
′
=
i
-
1
,
j
+
1
,
k
,
i
,
j
+
1
,
k
+
1
c
1

,
l
2
′
=
i
+
1
,
j
+
2
,
k
+
3
,
i
,
j
+
2
,
k
+
2
c
1

,
l
3
′
=
i
-
1
,
j
+
3
,
k
+
2
,
i
-
1
,
j
+
2
,
k
+
1
c
1

.Since the sender(
i
-
1
,
j
+
3
,
k
+
2
) of l
3
′ is one hop away from the receiver (
i
,
j
+
2
,
k
+
2
) of l
2
′, which violates the third condition in Theorem 2, l
2
′ and l
3
′ cannot coexist on channel c
1, which means that l
1
′, l
2
′, and l
3
′ cannot coexist. In other words, switching the senders of interference-free links may incur new interferences. Therefore, we must perform interference check after switching the sender of an active link.Sender switching may generate a new dense link group in a local mesh. For example, we obtain a new linkl
1
*
=
(
(
i
+
1
,
j
,
k
+
1
)
,
(
i
,
j
+
1
,
k
+
1
)
)
c
1, by switching the sender of link l
1 to its neighbor node anticlockwise. The three links l
1
*, l
2, and l
3 are interference-free. Similarly, link l
3
*
=
(
(
i
-
2
,
j
+
2
,
k
)
,
(
i
-
1
,
j
+
2
,
k
+
1
)
)
c
1 is also interference-free with links l
1 and l
2.Since triangular meshes possess symmetric properties, transformations such as rotation and translation can retain the interference-free features, which may save computing time in finding new link groups [24, 25].


### 3.5. Node Identity Number Assignment

The nodes in triangular meshes can be viewed not only as wireless router nodes, but also as resources or data sets. Assigning a unique identification (ID) number to each node brings several benefits. For example, such IDs can help to locate or identify nodes quickly for various administration or maintenance purposes.Given the coordinates(
i
,
j
,
k
) of a node in PCCS, there exists a general function g that maps (
i
,
j
,
k
) to a unique integer. For example, in Figure 2, we can map BS
=
(
0,0
,
0
) to 0, while B
=
(
1,0
,
-
1
) to 1, and C
=
(
-
1,1
,
0
) to 2.Definition 3.
In PCCS,M-circle in a triangular mesh is a set of nodes that have exact distance of M hops to the node BS.Suppose that(
i
,
j
,
k
) is in M-circle, where M
=
max
⁡
{
|
i
|
,
|
j
|
,
|
k
|
} according to 3. To construct a mapping function g
(
i
,
j
,
k
), we classify nodes according to their coordinates. For any node A
=
(
i
,
j
,
k
), we consider the following seven cases in Figure 4, which is a logical route extracted from Figure 2. The first and special case M
=
0, g
(
0,0
,
0
)
=
0. The node IDs in M-circle increase along an anticlockwise direction. These cases are applicable to any M-circle. The parallel solid line segments are corresponding to identity counting piecewise functions; for example, the 2nd case includes three parallel segments of different M-circle in Figure 4, in which nodes on these segments get their ID number following the 2nd one in 11. The dashed line means that the inner node is counted already, and the outer node is the new start of the next circle.Figure 4
The cases for node identity number assignment.To assign an identity to each node onM-circle, we need to know the total number κ of nodes inside this circle:
(10)
κ
=
1
+
6
1
+
2
+
⋯
+
M
-
1
=
1
+
3
M
(
M
-
1
)
.LetΔ
=
3
M
(
M
-
1
); we have κ
=
Δ
+
1. For example, there is one node inside circle M
=
1, there are Δ
+
1
=
7 nodes inside circle M
=
2, and there are Δ
+
1
=
18
+
1
=
19 nodes inside circle M
=
3.The number of nodes onM-circle depends on the value of M. According to 11, for any M-circle, with the six solid line segments in the order as shown by arrows in Figure 4, we assign each node a unique integer on M-circle with an ID number in {
Δ
+
1
,
Δ
+
2
,
…
,
Δ
+
j
+
1
,
…
,
Δ
+
6
M
}. After overlapping Figure 4 on Figure 2, a node is assigned with its identity number in one of the seven cases in 11 corresponding to the line segment case in Figure 4:
(11)
g
(
i
,
j
,
k
)
=
0
M
=
0
i
1st
Δ
+
j
+
1
M
≠
0
∧
M
=
k
iii
2
nd
Δ
+
M
-
i
+
1
M
≠
0
∧
M
=
j
iii
3rd
Δ
+
2
M
-
k
+
1
M
≠
0
∧
M
=
-
i
i
4
th
Δ
+
3
M
-
j
+
1
M
≠
0
∧
M
=
-
k
5
th
Δ
+
4
M
+
i
+
1
M
≠
0
∧
M
=
-
j
i
6
th
Δ
+
5
M
+
k
+
1
M
=
i
∧
i
≠
k
,
0
i
i
7
th.For example, in the 6th case, node(
1
,
-
4
,
-
3
) is assigned with an ID number of 3
×
4
×
(
4
-
1
)
+
4
×
4
+
1
+
1
=
54.Some nodes may satisfy two cases in11 while getting the same ID. For example, node (
0,3
,
3
), which is on the 3-circle and the line segment in parallel with k-axis, is assigned with an ID number of 3
×
M
×
(
M
-
1
)
+
j
+
1
=
3
×
3
×
2
+
3
+
1
=
22 in the 2nd case in 11. Meanwhile, node (
0,3
,
3
), as it is on one line segment of Case  3 in Figure 4, can get its ID of 3
×
M
×
(
M
-
1
)
+
M
-
i
+
1
=
3
×
3
×
2
+
3
+
1
=
22 by following the 3rd case in 11.We shall provide more explanations for the 2nd and 7th cases to facilitate a better understanding of11. In the 2nd case where M
≠
0
∧
M
=
k, the coordinate k of node (
i
,
j
,
k
) must be positive. Node (
i
,
j
,
k
) on this M-circle (M
=
k) segment should be assigned with an ID number in {
Δ
+
1
,
Δ
+
2
,
…
,
Δ
+
j
+
1
,
…
,
Δ
+
M
}. In this case, node (
i
,
j
,
k
) is located above the lines j
=
0 and k
>
0, as shown in Case  2 in Figure 4. Hence, with the increasing j, each node (
i
,
j
,
k
) is assigned with an ID number g
(
i
,
j
,
k
)
=
Δ
+
j
+
1. Generally, on each M-circle (M
>
0), from the 2nd case to the 7th case, each with M nodes, the total number of nodes is 6
M.In the 7th case, we need to avoid repeatedly counting the node on linej
=
0, as shown in Figure 2. The number of hops to the BS is M
=
i. The last node on this circle is on a line segment of the i-axis parallel cluster with j
=
0 according to Figure 4. The condition M
=
i
∧
i
≠
k excludes the nodes already counted in the previous Case  2 in this circle, while M
=
i
∧
i
≠
0 prevents the 1st case from being reconsidered. Meanwhile, the condition M
≠
k ensures that we count nodes on the next circle following the 2nd case again where M
=
k. In the 7th case, a node can be assigned with an ID number in a finite set {
Δ
+
5
M
+
1
,
…
,
Δ
+
5
M
+
k
+
1
,
…
,
Δ
+
6
M
}. With the increasing k, where k
=
0,1
,
…
,
M
-
1, node (
i
,
j
,
k
) on this segment is assigned with an ID number of Δ
+
5
M
+
k
+
1.Note that the mapping functiong
(
i
,
j
,
k
) is a segmented linear function, which is invertible for any finite set.


## 3.1. Cartesian Product of Graphs

The topology-based modeling approach has been commonly used in wireless networks for various purposes, but often in a planar view [8, 12, 14], and most of the discussions on scheduling, routing, and channel assignment are also based on a planar topology [6, 11, 13, 17]. The recent development of MIMO WMNs calls for a suitable model to describe MIMO-specific properties and understand the cooperative activities across different interfaces over multiple channels [20]. The planar topology can be used to determine the internode interference [8] but is insufficient to provide a visual representation for analyzing the cooperation between links or channels. On the other hand, modeling MIMO WMNs as a super graph still remains largely unexploited except the work in [4]. In this paper, our goal is to develop an effective model to facilitate the analysis of MIMO channel cooperation.We propose to employ the CPG to model WMNs by combining a triangular mesh of physical nodes and a graph of fully connected virtual nodes. Together with the coordinates of triangular overlay nodes, the CPG model provides a convenient way to analyze the properties of interference avoidance, channel assignment, and routing path counting. This model retains the independence between orthogonal channels while providing a general approach to analyzing link behaviors over multiple channels.Cartesian Product of Graphs. Given two graphs G and H, the Cartesian product G
×
H is a graph such that(i)
the graphG
×
H has a vertex set V
(
G
)
×
V
(
H
); that is, a vertex in G
×
H is denoted by a pair (
v
,
v
′
), v
∈
V
(
G
), and v
′
∈
V
(
H
);
(ii)
any two nodes(
u
,
u
′
) and (
v
,
v
′
) and u
,
v
∈
V
(
G
) and u
′
,
v
′
∈
V
(
H
) are adjacent in G
×
H, if and only if one of the following holds: (a) u
=
v and u
′ is adjacent to v
′ in H, or (b) u
′
=
v
′ and u is adjacent to v in G.For illustration, Figure1(a) shows a mesh network of five physical nodes (left side) and a graph of two connected virtual nodes (right side) corresponding to a physical node equipped with two transceivers, each operating on a different channel c
1 or c
2. Figure 1(b) shows a channel-layered virtual topology of the original mesh network modeled by CPG.Figure 1
The CPG-modeled virtual topology of a physical network with five physical nodes and two channels.In this example, the CPG of two graphs in Figure1(a) results in a two-layered graph in Figure 1(b). A solid directed edge in the top or bottom planar meshes in Figures 1(b), 1(c), and 1(d) represents a communication link l
=
(
S
,
R
)
c, transmitting data from node S to node R over a channel c, while a dashed edge has a conflict with some active links.The maximum possible number of concurrent active links on a given channel in a mesh is largely affected by the selection of the senders. As shown in Figure1(b), when node A in the top layer is sending data on channel c
1, the three neighbors of A, that is, nodes B, C, and D, in the same layer (over channel c
1) cannot send data. Furthermore, node E can be selected as a sender, but neither of its neighbors, that is, nodes C and D, can receive data from E without interference, illustrated as the dashed directed edges in Figure 1(c). In this case, there is no other active link except (
A
,
B
)
c
1. However, if we choose the initial senders properly, as shown in Figure 1(d), there could exist two concurrent interference-free links on channel c
i,  i
=
1,2, that is, (
B
,
A
)
c
i and (
E
,
D
)
c
i.Since all active links must be interference-free on the same channel at the same time, links are generally sparsely distributed in a planar mesh with respect to a certain channel. Note that more links mean better service to traffic requests. The CPG model allows us to consider concurrent paths in multiple layers over different channels through radio cooperation among channel layers for a given traffic task, hence providing more capacity and higher throughput compared to the situation with a single channel and radio. This is consistent with the experimental results presented by Draves et al. [16]. The proposed CPG model is aligned well with existing research in terms of interference relation, link activity, and network throughput, as well as routing and scheduling [6, 7, 14, 19, 21] and enables us to conduct deeper theoretical analysis of WMNs.One advantage that CPG brings is to simplify the expression of multichannel links. Since different layers (operating on different channels) are of the same topology, the scheduling strategy derived in one layer is readily applicable to another layer. For example, there exists a certain link distribution pattern among concurrent links. In CPG, it is obvious that such an interference-free link distribution pattern on one channel also exists on others.


## 3.2. Coordinate Scheme

A well-designed coordinate scheme may facilitate the analysis of WMNs. Since all channel layers are of the same topology, we only need to design the coordinate scheme for one layer or channel. The channel information can be added to the node coordinates to uniquely identify a specific layer.Chin et al. proposed a coordinate scheme in hexagonal cellular networks where each node has a degree of three [15]. Inspired by their work, we propose a parallel cluster coordinate scheme in a local triangular mesh with one BS node and a number of SS nodes with a degree of six. This scheme can be readily extended to larger networks with multiple BSs by inserting the BS information to the node coordinates.


### 3.2.1. Parallel Cluster Coordinate Scheme

In a triangular mesh, we first define three clusters of parallel lines along three different directions, that is, north-east, east, and south-east. Since each node is a point intersected by three lines, each from one of the three clusters, we propose a parallel cluster coordinate scheme (PCCS), which uses a 3-tuple(
i
,
j
,
k
) to represent the coordinates of a node intersected by the ith, jth, and kth line in the corresponding clusters [5]. As illustrated in Figure 2, the BS node with the coordinates (
0,0
,
0
) is located at the center, and the SS nodes A, B, C, D, E, and F, which are one hop away from the BS node, have the coordinates A
=
(
1,0
,
1
), B
=
(
0,1
,
1
), C
=
(
-
1
,
-
1,0
), D
=
(
-
1,0
,
-
1
), E
=
(
0
,
-
1
,
-
1
), and F
=
(
1,1
,
0
).Figure 2
The parallel cluster coordinate scheme.Note that not every combination of three integers can represent a node in a triangular mesh because some lines defined by combinatorial 3-tuples do not intersect at a common point. We summarize such lines as follows:(1)
Ω
=
(
i
-
1
,
j
-
1
,
k
)
,
(
i
+
1
,
j
+
1
,
k
)
,
(
i
,
j
-
1
,
k
+
1
)
,
p
p
(
i
,
j
+
1
,
k
-
1
)
,
(
i
+
1
,
j
,
k
-
1
)
,
(
i
-
1
,
j
,
k
+
1
)
.Under the proposed PCCS scheme, for a given sender(
i
,
j
,
k
), there are six possible receivers, which form its neighbor set N
b
(
i
,
j
,
k
):
(2)
N
b
i
,
j
,
k
=
(
i
-
1
,
j
+
1
,
k
)
,
(
i
+
1
,
j
-
1
,
k
)
,
p
p
p
(
i
,
j
+
1
,
k
+
1
)
,
(
i
,
j
-
1
,
k
-
1
)
,
p
p
p
(
i
+
1
,
j
,
k
+
1
)
,
(
i
-
1
,
j
,
k
-
1
)
.PCCS retains the symmetric nature of a triangular mesh and facilitates the calculation of the distance between a pair of nodes.


### 3.2.2. Symmetric Property of PCCS

In PCCS, the coordinates of any two nodes that are symmetric with respect to the central BS node located at(
0,0
,
0
) are negated. For example, the pairs of nodes A and D, B and E, and C and F in Figure 2 are symmetric, and their coordinates are negated from their counterparts.The symmetric properties of CPG and Cayley graph have been well studied [22]. According to the vertex/edge transitive properties, a link group can be transited to generate another one in any layer.Similarly, due to the symmetric property, we are able to transform a link group to another one through rotation. For example, link group of(
(
0,2
,
2
)
,
(
0,1
,
1
)
)
c and (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c is interference-free. After a clockwise rotation of π
/
3, a new group of interference-free links is of (
(
2,0
,
2
)
,
(
1,0
,
1
)
)
c and (
(
0
,
-
2
,
-
2
)
,
(
0
,
-
1
,
-
1
)
)
c, respectively. With another clockwise rotation of π
/
3, the derived interference-free links are (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c and (
(
-
2,0
,
-
2
)
,
(
-
1,0
,
-
1
)
)
c, respectively. Note that the rotation operation is edge transitive, and it generates a new link group because of the symmetric property.


### 3.2.3. Distance between Two Nodes

As most traffic is upload/download (to/from BS), we need to count the number of hops from a router node to BS in PCCS. We have the following properties.Property 1.
In triangular WMNs with PCCS, the minimum numberħ of hops from A
=
(
i
,
j
,
k
) to BS
=
(
0,0
,
0
) is
(3)
ħ
=
i
+
j
+
k
2
=
max
⁡
i
,
j
,
k
which is consistent with the one in [4].Property 2.
Suppose that BS is positioned at an arbitrary location(
i
0
,
j
0
,
k
0
), instead of (
0,0
,
0
). Node (
i
,
j
,
k
) can be translated to (
i
,
j
,
k
)
-
(
i
0
,
j
0
,
k
0
) by a translation function:
(4)
δ
:
(
i
,
j
,
k
)
⟶
i
,
j
,
k
-
i
0
,
j
0
,
k
0
.In general, suppose that(
i
0
,
j
0
,
k
0
) is the destination of a traffic path; we may virtually view (
i
0
,
j
0
,
k
0
) as the BS node after applying the translation of 4. Then, the formula in 3 may facilitate further analysis.Given two nodesA
=
(
i
1
,
j
1
,
k
1
) and B
=
(
i
2
,
j
2
,
k
2
) in PCCS, the distance between A and B, denoted by d
(
A
,
B
), is theminimum number of hops between them, which is calculated as d
(
A
,
B
)
=
(
|
i
1
-
i
2
|
+
|
j
1
-
j
2
|
+
|
k
1
-
k
2
|
)
/
2.


### 3.2.4. Mapping to 2D Points

In order to draw a planar mesh, we need to map 3-tuple coordinates(
i
,
j
,
k
) to 2-dimensional (2D) points (
x
,
y
). To do this, we first overlap a rectangular plane coordinate system to the PCCS triangular mesh. Let the x-axis overlap the axis j
=
0 while keeping the positive rightward direction. Meanwhile, the y-axis passes the BS node and is vertical to the line j
=
0 with a positive upward direction. Then, we can determine (
x
,
y
) by projecting (
i
,
j
,
k
) onto axes x and y. The PCCS supports a function f mapping (
i
,
j
,
k
) to (
x
,
y
) as follows.Property 3.
A one-to-one mapping functionf maps node coordinates (
i
,
j
,
k
) in PCCS to 2D coordinates (
x
,
y
):
(5)
x
,
y
=
f
i
,
j
,
k
=
x
=
i
+
k
2
y
=
j
.For example, node(
0,1
,
1
) is mapped to (
1
/
2,1
), and (
-
1,3
,
2
) is mapped to (
1
/
2,3
). If a node is on the y-axis, i
=
-
k always holds. For example, (
-
1,2
,
1
) is mapped to (
0,2
). If node is located on k
=
0 in PCCS, x
=
i
/
2. For example, (
-
2,2
,
0
) is mapped to (
-
1,2
). This property facilitates the plotting of a triangular mesh in PCCS.


## 3.2.1. Parallel Cluster Coordinate Scheme

In a triangular mesh, we first define three clusters of parallel lines along three different directions, that is, north-east, east, and south-east. Since each node is a point intersected by three lines, each from one of the three clusters, we propose a parallel cluster coordinate scheme (PCCS), which uses a 3-tuple(
i
,
j
,
k
) to represent the coordinates of a node intersected by the ith, jth, and kth line in the corresponding clusters [5]. As illustrated in Figure 2, the BS node with the coordinates (
0,0
,
0
) is located at the center, and the SS nodes A, B, C, D, E, and F, which are one hop away from the BS node, have the coordinates A
=
(
1,0
,
1
), B
=
(
0,1
,
1
), C
=
(
-
1
,
-
1,0
), D
=
(
-
1,0
,
-
1
), E
=
(
0
,
-
1
,
-
1
), and F
=
(
1,1
,
0
).Figure 2
The parallel cluster coordinate scheme.Note that not every combination of three integers can represent a node in a triangular mesh because some lines defined by combinatorial 3-tuples do not intersect at a common point. We summarize such lines as follows:(1)
Ω
=
(
i
-
1
,
j
-
1
,
k
)
,
(
i
+
1
,
j
+
1
,
k
)
,
(
i
,
j
-
1
,
k
+
1
)
,
p
p
(
i
,
j
+
1
,
k
-
1
)
,
(
i
+
1
,
j
,
k
-
1
)
,
(
i
-
1
,
j
,
k
+
1
)
.Under the proposed PCCS scheme, for a given sender(
i
,
j
,
k
), there are six possible receivers, which form its neighbor set N
b
(
i
,
j
,
k
):
(2)
N
b
i
,
j
,
k
=
(
i
-
1
,
j
+
1
,
k
)
,
(
i
+
1
,
j
-
1
,
k
)
,
p
p
p
(
i
,
j
+
1
,
k
+
1
)
,
(
i
,
j
-
1
,
k
-
1
)
,
p
p
p
(
i
+
1
,
j
,
k
+
1
)
,
(
i
-
1
,
j
,
k
-
1
)
.PCCS retains the symmetric nature of a triangular mesh and facilitates the calculation of the distance between a pair of nodes.


## 3.2.2. Symmetric Property of PCCS

In PCCS, the coordinates of any two nodes that are symmetric with respect to the central BS node located at(
0,0
,
0
) are negated. For example, the pairs of nodes A and D, B and E, and C and F in Figure 2 are symmetric, and their coordinates are negated from their counterparts.The symmetric properties of CPG and Cayley graph have been well studied [22]. According to the vertex/edge transitive properties, a link group can be transited to generate another one in any layer.Similarly, due to the symmetric property, we are able to transform a link group to another one through rotation. For example, link group of(
(
0,2
,
2
)
,
(
0,1
,
1
)
)
c and (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c is interference-free. After a clockwise rotation of π
/
3, a new group of interference-free links is of (
(
2,0
,
2
)
,
(
1,0
,
1
)
)
c and (
(
0
,
-
2
,
-
2
)
,
(
0
,
-
1
,
-
1
)
)
c, respectively. With another clockwise rotation of π
/
3, the derived interference-free links are (
(
2
,
-
2,0
)
,
(
1
,
-
1,0
)
)
c and (
(
-
2,0
,
-
2
)
,
(
-
1,0
,
-
1
)
)
c, respectively. Note that the rotation operation is edge transitive, and it generates a new link group because of the symmetric property.


## 3.2.3. Distance between Two Nodes

As most traffic is upload/download (to/from BS), we need to count the number of hops from a router node to BS in PCCS. We have the following properties.Property 1.
In triangular WMNs with PCCS, the minimum numberħ of hops from A
=
(
i
,
j
,
k
) to BS
=
(
0,0
,
0
) is
(3)
ħ
=
i
+
j
+
k
2
=
max
⁡
i
,
j
,
k
which is consistent with the one in [4].Property 2.
Suppose that BS is positioned at an arbitrary location(
i
0
,
j
0
,
k
0
), instead of (
0,0
,
0
). Node (
i
,
j
,
k
) can be translated to (
i
,
j
,
k
)
-
(
i
0
,
j
0
,
k
0
) by a translation function:
(4)
δ
:
(
i
,
j
,
k
)
⟶
i
,
j
,
k
-
i
0
,
j
0
,
k
0
.In general, suppose that(
i
0
,
j
0
,
k
0
) is the destination of a traffic path; we may virtually view (
i
0
,
j
0
,
k
0
) as the BS node after applying the translation of 4. Then, the formula in 3 may facilitate further analysis.Given two nodesA
=
(
i
1
,
j
1
,
k
1
) and B
=
(
i
2
,
j
2
,
k
2
) in PCCS, the distance between A and B, denoted by d
(
A
,
B
), is theminimum number of hops between them, which is calculated as d
(
A
,
B
)
=
(
|
i
1
-
i
2
|
+
|
j
1
-
j
2
|
+
|
k
1
-
k
2
|
)
/
2.


## 3.2.4. Mapping to 2D Points

In order to draw a planar mesh, we need to map 3-tuple coordinates(
i
,
j
,
k
) to 2-dimensional (2D) points (
x
,
y
). To do this, we first overlap a rectangular plane coordinate system to the PCCS triangular mesh. Let the x-axis overlap the axis j
=
0 while keeping the positive rightward direction. Meanwhile, the y-axis passes the BS node and is vertical to the line j
=
0 with a positive upward direction. Then, we can determine (
x
,
y
) by projecting (
i
,
j
,
k
) onto axes x and y. The PCCS supports a function f mapping (
i
,
j
,
k
) to (
x
,
y
) as follows.Property 3.
A one-to-one mapping functionf maps node coordinates (
i
,
j
,
k
) in PCCS to 2D coordinates (
x
,
y
):
(5)
x
,
y
=
f
i
,
j
,
k
=
x
=
i
+
k
2
y
=
j
.For example, node(
0,1
,
1
) is mapped to (
1
/
2,1
), and (
-
1,3
,
2
) is mapped to (
1
/
2,3
). If a node is on the y-axis, i
=
-
k always holds. For example, (
-
1,2
,
1
) is mapped to (
0,2
). If node is located on k
=
0 in PCCS, x
=
i
/
2. For example, (
-
2,2
,
0
) is mapped to (
-
1,2
). This property facilitates the plotting of a triangular mesh in PCCS.


## 3.3. Interference-Free Conditions

To analyze the interference between links, we need to consider node interference relations, which are critical to scheduling links in WMNs. As interference is an inherent nature for radio media, the wireless communication performance may be severely degraded if radios operate without a proper scheduling scheme [17].Minimizing interference has been extensively investigated in the literature [9, 17]. Subramanian et al. discussed channel assignment in a multiradio situation [9]. Tan et al. designed algorithms to set up a skeleton of minimum interference for a single channel [17]. Scheduling links in a cooperative way will improve the energy efficiency and reduce collision. These discussions assume variable transmitting power or interface channel switching. However, the variation of transmitting power may lead to the variation of network topology, which may cause changes in the interference relation. Xu et al. use a sensing scheme to achieve power efficiency for convergence communication [23]. Their method can help set the initial power in an almost-static WMN topology while promising interference-free cognitive access with link status as busy or idle.When senderS is sending over channel c
0, neither can S receive data over channel c
0, nor can its neighbors in its effective radio coverage send data. If a valid neighbor node R receives data over channel c
0, we have a link (
S
,
R
)
c
0. Furthermore, the neighbors of receiver R cannot send data over channel c
0 at the same time. Therefore, to be link interference-free in multiradio multichannel environments using PCCS, we need to consider three classes of node interferences: sender-to-sender, receiver-to-receiver, and sender-to-receiver.


### 3.3.1. Sender-to-Sender

Given a certain channel, any two senders must be at least two hops away in a triangular mesh to avoid mutual interference, which could help construct an interference-free candidate set for possible senders.Definition 1.
A router setS
C is called a sender candidate set if every two nodes in S
C are at least two hops away.Given two nodesS
i
=
(
a
,
b
,
c
) and S
j
=
(
d
,
e
,
f
) in S
C, the distance between them must satisfy d
(
S
i
,
S
j
)
≥
2.For a given nodeS
j
∉
S
C, we can add S
j to S
C only if it is at least two hops away to any node S
i in S
C. We have the following necessary condition on interference-free links:
(6)
d
S
i
,
S
j
=
a
-
d
+
b
-
e
+
c
-
f
2
≥
2
.


### 3.3.2. Receiver-to-Receiver

Two nodesR
i and R
j can each act as a receiver simultaneously if they have a distance larger than 1. Similar to the sender candidate set, we use R
C to denote a receiver candidate set, in which any two nodes R
i
=
(
l
,
m
,
n
) and R
j
=
(
u
,
p
,
q
) satisfy the following condition:
(7)
d
R
i
,
R
j
=
l
-
u
+
m
-
p
+
n
-
q
2
≥
1
.Note that bothS
C and R
C are candidate sets, and the actual sender and receiver sets are a subset of S
C and R
C, respectively. The relations between nodes largely depend on the previous selected links.Property 4.
If links(
S
1
,
R
1
)
c and (
S
2
,
R
2
)
c can be scheduled at the same time, then d
(
S
1
,
S
2
) must satisfy condition 6 and d
(
R
1
,
R
2
) must satisfy condition 7.Note that Property4 is only a necessary condition for interference-free links.


### 3.3.3. Sender-to-Receiver

Given a certain channel, a node cannot receive data if it is in the effective radio range of the sender of any other active link; otherwise, interference occurs. If two linksl
i and l
j (i
≠
j) coexist, the nodes involved in these two links must satisfy the following condition:
(8)
d
S
i
,
R
j
=
a
-
u
+
b
-
p
+
c
-
q
2
>
1
,
i
≠
j
,
where S
i is the sender of link l
i and R
j is the receiver of link l
j.For example, in Figure1(d), since A’s neighbor D does not conflict with link (
B
,
A
)
c
1, D can be a receiver of another link (
E
,
D
)
c
1.We summarize three necessary conditions for link coexistence in the aforementioned three classes in Table1.Table 1
Conditions for simultaneous links over one channel.
Three neighbor pairs
Link interference-free conditions
Nodes
Nodes
Necessary
Sufficient
inS
C
inR
C
condition
condition
S
i, S
j
∀
i
≠
j, d
(
S
i
,
S
j
)
≥
2 (1)
R
i, R
j
∀
i
≠
j, d
(
R
i
,
R
j
)
≥
1 (2)
(1) ∧ (2) ∧ (3)
S
i
R
j
∀
i
≠
j, d
(
S
i
,
R
j
)
>
1 (3)We have the following theorem.Theorem 2.
Two linksl
i and l
j can be simultaneously scheduled (coexist) on the same channel, if and only if they satisfy all of the three necessary conditions in Table 1.Theorem2 is based on the PCCS scheme and the set theory. As long as the PCCS node coordinates are given, we are able to determine the interference between links. These known conditions are helpful to find as many links as possible, while contributing to concurrent central scheduling.


## 3.3.1. Sender-to-Sender

Given a certain channel, any two senders must be at least two hops away in a triangular mesh to avoid mutual interference, which could help construct an interference-free candidate set for possible senders.Definition 1.
A router setS
C is called a sender candidate set if every two nodes in S
C are at least two hops away.Given two nodesS
i
=
(
a
,
b
,
c
) and S
j
=
(
d
,
e
,
f
) in S
C, the distance between them must satisfy d
(
S
i
,
S
j
)
≥
2.For a given nodeS
j
∉
S
C, we can add S
j to S
C only if it is at least two hops away to any node S
i in S
C. We have the following necessary condition on interference-free links:
(6)
d
S
i
,
S
j
=
a
-
d
+
b
-
e
+
c
-
f
2
≥
2
.


## 3.3.2. Receiver-to-Receiver

Two nodesR
i and R
j can each act as a receiver simultaneously if they have a distance larger than 1. Similar to the sender candidate set, we use R
C to denote a receiver candidate set, in which any two nodes R
i
=
(
l
,
m
,
n
) and R
j
=
(
u
,
p
,
q
) satisfy the following condition:
(7)
d
R
i
,
R
j
=
l
-
u
+
m
-
p
+
n
-
q
2
≥
1
.Note that bothS
C and R
C are candidate sets, and the actual sender and receiver sets are a subset of S
C and R
C, respectively. The relations between nodes largely depend on the previous selected links.Property 4.
If links(
S
1
,
R
1
)
c and (
S
2
,
R
2
)
c can be scheduled at the same time, then d
(
S
1
,
S
2
) must satisfy condition 6 and d
(
R
1
,
R
2
) must satisfy condition 7.Note that Property4 is only a necessary condition for interference-free links.


## 3.3.3. Sender-to-Receiver

Given a certain channel, a node cannot receive data if it is in the effective radio range of the sender of any other active link; otherwise, interference occurs. If two linksl
i and l
j (i
≠
j) coexist, the nodes involved in these two links must satisfy the following condition:
(8)
d
S
i
,
R
j
=
a
-
u
+
b
-
p
+
c
-
q
2
>
1
,
i
≠
j
,
where S
i is the sender of link l
i and R
j is the receiver of link l
j.For example, in Figure1(d), since A’s neighbor D does not conflict with link (
B
,
A
)
c
1, D can be a receiver of another link (
E
,
D
)
c
1.We summarize three necessary conditions for link coexistence in the aforementioned three classes in Table1.Table 1
Conditions for simultaneous links over one channel.
Three neighbor pairs
Link interference-free conditions
Nodes
Nodes
Necessary
Sufficient
inS
C
inR
C
condition
condition
S
i, S
j
∀
i
≠
j, d
(
S
i
,
S
j
)
≥
2 (1)
R
i, R
j
∀
i
≠
j, d
(
R
i
,
R
j
)
≥
1 (2)
(1) ∧ (2) ∧ (3)
S
i
R
j
∀
i
≠
j, d
(
S
i
,
R
j
)
>
1 (3)We have the following theorem.Theorem 2.
Two linksl
i and l
j can be simultaneously scheduled (coexist) on the same channel, if and only if they satisfy all of the three necessary conditions in Table 1.Theorem2 is based on the PCCS scheme and the set theory. As long as the PCCS node coordinates are given, we are able to determine the interference between links. These known conditions are helpful to find as many links as possible, while contributing to concurrent central scheduling.


## 3.4. Transformations of Link Groups

We attempt to find as many coexisting links as possible in a given local area. Since a link can be established only between a valid sender candidate and a valid receiver candidate, the actual (final) scheduled link set is a subset ofS
C
×
R
C. Generally, coexisting links are sparsely distributed in the network. Based on a known group of coexisting links around one triangle, we wish to obtain a new group of coexisting links through certain transformations.Starting from a linkl
1
=
(
S
1
,
R
1
)
c
1, where S
1
=
(
i
,
j
,
k
) and R
1
=
(
i
,
j
+
1
,
k
+
1
), we want to set up a dense link group in a local area. The set of S
1’s neighbor nodes is N
b
(
S
1
)
=
{
v
∣
d
(
v
,
(
i
,
j
,
k
)
)
≤
1
,
v
∈
V
}. The set of R
1’s neighbor nodes is N
b
(
R
1
)
=
{
v
∣
d
(
v
,
(
i
,
j
+
1
,
k
+
1
)
)
≤
1
,
∀
v
∈
V
}. As any neighbor node of the sender or the receiver of an active link should remain silent if it does not receive data from the sender S
1, to avoid interference with l
1, nodes in N
b
(
i
,
j
,
k
)
∪
N
b
(
R
1
) cannot send data on c
1 when l
1 is active.To expand the active link group containingl
1
=
(
S
1
,
R
1
)
c
1, two nodes S
2
=
(
i
,
j
+
3
,
k
+
3
) and R
2
=
(
i
,
j
+
2
,
k
+
2
), which are not in N
b
(
S
1
) and N
b
(
R
1
), may negotiate for a new link. If successful, (
S
2
,
R
2
)
c
1 is added to the active link group. According to the conditions in Theorem 2, link l
2
=
(
S
2
,
R
2
)
c
1 can coexist with l
1.Any node inN
b
(
R
1
)
∪
N
b
(
R
2
) cannot be a new sender, except S
1 and S
2. However, it is completely different on the receiver side, where one node may be the receiver of a new link, even if it is in N
b
(
R
1
)
∩
N
b
(
R
2
). For example, in Figure 3, S
3
=
(
i
-
2
,
j
+
3
,
k
+
1
) and R
3
=
(
i
-
1
,
j
+
2
,
k
+
1
) form a new link l
3
=
(
S
3
,
R
3
)
c
1, which can coexist with l
1 and l
2. Around the central triangle in Figure 3, we find three interference-free links coexisting over one channel.Figure 3
Coexisting links in a local area.Although the three nodes of the central triangle are involved in three active links as shown in Figure3, neither of these three nodes can act as a sender while the other two are receiving data from their respective senders. To obtain the same number of new coexisting links, we need to keep the receivers unchanged, while considering a certain switching to the three senders of active links l
1, l
2, and l
3.By passing the sending token from the current sender to its neighbor node clockwise while keeping the original receiver, we are able to establish three possible new links:(9)
l
1
′
=
i
-
1
,
j
+
1
,
k
,
i
,
j
+
1
,
k
+
1
c
1

,
l
2
′
=
i
+
1
,
j
+
2
,
k
+
3
,
i
,
j
+
2
,
k
+
2
c
1

,
l
3
′
=
i
-
1
,
j
+
3
,
k
+
2
,
i
-
1
,
j
+
2
,
k
+
1
c
1

.Since the sender(
i
-
1
,
j
+
3
,
k
+
2
) of l
3
′ is one hop away from the receiver (
i
,
j
+
2
,
k
+
2
) of l
2
′, which violates the third condition in Theorem 2, l
2
′ and l
3
′ cannot coexist on channel c
1, which means that l
1
′, l
2
′, and l
3
′ cannot coexist. In other words, switching the senders of interference-free links may incur new interferences. Therefore, we must perform interference check after switching the sender of an active link.Sender switching may generate a new dense link group in a local mesh. For example, we obtain a new linkl
1
*
=
(
(
i
+
1
,
j
,
k
+
1
)
,
(
i
,
j
+
1
,
k
+
1
)
)
c
1, by switching the sender of link l
1 to its neighbor node anticlockwise. The three links l
1
*, l
2, and l
3 are interference-free. Similarly, link l
3
*
=
(
(
i
-
2
,
j
+
2
,
k
)
,
(
i
-
1
,
j
+
2
,
k
+
1
)
)
c
1 is also interference-free with links l
1 and l
2.Since triangular meshes possess symmetric properties, transformations such as rotation and translation can retain the interference-free features, which may save computing time in finding new link groups [24, 25].


## 3.5. Node Identity Number Assignment

The nodes in triangular meshes can be viewed not only as wireless router nodes, but also as resources or data sets. Assigning a unique identification (ID) number to each node brings several benefits. For example, such IDs can help to locate or identify nodes quickly for various administration or maintenance purposes.Given the coordinates(
i
,
j
,
k
) of a node in PCCS, there exists a general function g that maps (
i
,
j
,
k
) to a unique integer. For example, in Figure 2, we can map BS
=
(
0,0
,
0
) to 0, while B
=
(
1,0
,
-
1
) to 1, and C
=
(
-
1,1
,
0
) to 2.Definition 3.
In PCCS,M-circle in a triangular mesh is a set of nodes that have exact distance of M hops to the node BS.Suppose that(
i
,
j
,
k
) is in M-circle, where M
=
max
⁡
{
|
i
|
,
|
j
|
,
|
k
|
} according to 3. To construct a mapping function g
(
i
,
j
,
k
), we classify nodes according to their coordinates. For any node A
=
(
i
,
j
,
k
), we consider the following seven cases in Figure 4, which is a logical route extracted from Figure 2. The first and special case M
=
0, g
(
0,0
,
0
)
=
0. The node IDs in M-circle increase along an anticlockwise direction. These cases are applicable to any M-circle. The parallel solid line segments are corresponding to identity counting piecewise functions; for example, the 2nd case includes three parallel segments of different M-circle in Figure 4, in which nodes on these segments get their ID number following the 2nd one in 11. The dashed line means that the inner node is counted already, and the outer node is the new start of the next circle.Figure 4
The cases for node identity number assignment.To assign an identity to each node onM-circle, we need to know the total number κ of nodes inside this circle:
(10)
κ
=
1
+
6
1
+
2
+
⋯
+
M
-
1
=
1
+
3
M
(
M
-
1
)
.LetΔ
=
3
M
(
M
-
1
); we have κ
=
Δ
+
1. For example, there is one node inside circle M
=
1, there are Δ
+
1
=
7 nodes inside circle M
=
2, and there are Δ
+
1
=
18
+
1
=
19 nodes inside circle M
=
3.The number of nodes onM-circle depends on the value of M. According to 11, for any M-circle, with the six solid line segments in the order as shown by arrows in Figure 4, we assign each node a unique integer on M-circle with an ID number in {
Δ
+
1
,
Δ
+
2
,
…
,
Δ
+
j
+
1
,
…
,
Δ
+
6
M
}. After overlapping Figure 4 on Figure 2, a node is assigned with its identity number in one of the seven cases in 11 corresponding to the line segment case in Figure 4:
(11)
g
(
i
,
j
,
k
)
=
0
M
=
0
i
1st
Δ
+
j
+
1
M
≠
0
∧
M
=
k
iii
2
nd
Δ
+
M
-
i
+
1
M
≠
0
∧
M
=
j
iii
3rd
Δ
+
2
M
-
k
+
1
M
≠
0
∧
M
=
-
i
i
4
th
Δ
+
3
M
-
j
+
1
M
≠
0
∧
M
=
-
k
5
th
Δ
+
4
M
+
i
+
1
M
≠
0
∧
M
=
-
j
i
6
th
Δ
+
5
M
+
k
+
1
M
=
i
∧
i
≠
k
,
0
i
i
7
th.For example, in the 6th case, node(
1
,
-
4
,
-
3
) is assigned with an ID number of 3
×
4
×
(
4
-
1
)
+
4
×
4
+
1
+
1
=
54.Some nodes may satisfy two cases in11 while getting the same ID. For example, node (
0,3
,
3
), which is on the 3-circle and the line segment in parallel with k-axis, is assigned with an ID number of 3
×
M
×
(
M
-
1
)
+
j
+
1
=
3
×
3
×
2
+
3
+
1
=
22 in the 2nd case in 11. Meanwhile, node (
0,3
,
3
), as it is on one line segment of Case  3 in Figure 4, can get its ID of 3
×
M
×
(
M
-
1
)
+
M
-
i
+
1
=
3
×
3
×
2
+
3
+
1
=
22 by following the 3rd case in 11.We shall provide more explanations for the 2nd and 7th cases to facilitate a better understanding of11. In the 2nd case where M
≠
0
∧
M
=
k, the coordinate k of node (
i
,
j
,
k
) must be positive. Node (
i
,
j
,
k
) on this M-circle (M
=
k) segment should be assigned with an ID number in {
Δ
+
1
,
Δ
+
2
,
…
,
Δ
+
j
+
1
,
…
,
Δ
+
M
}. In this case, node (
i
,
j
,
k
) is located above the lines j
=
0 and k
>
0, as shown in Case  2 in Figure 4. Hence, with the increasing j, each node (
i
,
j
,
k
) is assigned with an ID number g
(
i
,
j
,
k
)
=
Δ
+
j
+
1. Generally, on each M-circle (M
>
0), from the 2nd case to the 7th case, each with M nodes, the total number of nodes is 6
M.In the 7th case, we need to avoid repeatedly counting the node on linej
=
0, as shown in Figure 2. The number of hops to the BS is M
=
i. The last node on this circle is on a line segment of the i-axis parallel cluster with j
=
0 according to Figure 4. The condition M
=
i
∧
i
≠
k excludes the nodes already counted in the previous Case  2 in this circle, while M
=
i
∧
i
≠
0 prevents the 1st case from being reconsidered. Meanwhile, the condition M
≠
k ensures that we count nodes on the next circle following the 2nd case again where M
=
k. In the 7th case, a node can be assigned with an ID number in a finite set {
Δ
+
5
M
+
1
,
…
,
Δ
+
5
M
+
k
+
1
,
…
,
Δ
+
6
M
}. With the increasing k, where k
=
0,1
,
…
,
M
-
1, node (
i
,
j
,
k
) on this segment is assigned with an ID number of Δ
+
5
M
+
k
+
1.Note that the mapping functiong
(
i
,
j
,
k
) is a segmented linear function, which is invertible for any finite set.


## 4. Path Counting

Routing is one fundamental problem in WMNs. To develop a good routing scheme, one needs to know the number of alternative paths and the number of channel assignments for a given pair of source and destination. We discuss path finding and realization based on the proposed CPG model and coordinate scheme. The total number of shortest paths in grid meshes was discussed in [18]. In this section, we tackle the path counting problem in triangular meshes.We used
(
S
,
D
) to denote the distance between source S
=
(
i
1
,
j
1
,
k
1
) and destination D
=
(
i
2
,
j
2
,
k
2
). Firstly, d
(
S
,
D
)
=
(
|
i
1
-
i
2
|
+
|
j
1
-
j
2
|
+
|
k
1
-
k
2
|
)
/
2. In order to transmit data from S to D, we need to select one path from P
(
S
,
D
), which is the set of all shortest paths from S to D.


### 4.1. Path Alternatives

Every step along the shortest path fromS to D is one hop forward in one of the directions i, j, and k. The two smaller numbers of {
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} indicate the lines of parallel clusters that form a grid mesh for path selection, as illustrated in the grid of dashed lines in Figure 5. We refer to the two corresponding directions from S to D in the grid mesh as thecorrect directions.Figure 5
The shortest path alternatives in triangular meshes.Thecorrect directions ensure that the data is transmitted through one of the shortest path, where every hop selection makes one hop closer to the destination. Through the use of correct directions, we are able to reduce the problem of counting all shortest paths from S to D in triangular meshes to a problem in grid meshes.We provide an example in Figure5 to count the number of paths, where |
i
1
-
i
2
|
=
2, |
j
1
-
j
2
|
=
3, and |
k
1
-
k
2
|
=
5. The grid with dashed lines contains all the shortest paths from S to D.In a simple situation where one of{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} is 0, the dashed grid degrades to a line. Therefore, there is only one shortest path available.For convenience, let℘
=
{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
}. The correct directions are consistent with min
⁡
(
℘
) (the minimum of three elements in ℘) and mid
(
℘
) (the middle of three elements in ℘). To select a shortest path, it is necessary to remove the direction corresponding to max
⁡
(
℘
) (the maximum of three elements in ℘); otherwise, it would lead to a longer path.If the smallest in{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} is 1 or 2, in the corresponding direction, the sender and receiver must be on two neighbor parallel lines or two parallel lines with one line between them. We can use the corresponding grid to calculate the number p
(
S
,
D
) of paths from S to D as follows:
(12)
p
(
S
,
D
)
=
1
if
min
⁡
(
℘
)
=
0
,
mid
(
℘
)
+
1
if
min
⁡
(
℘
)
=
1
,
mid
℘
+
1
mid
℘
+
2
2
if
min
⁡
(
℘
)
=
2
.For example, in Figure5, the number of paths from S to D is determined by two directions i and j, as |
i
1
-
i
2
|
=
2 and |
j
1
-
j
2
|
=
3 are smaller than |
k
1
-
k
2
|
=
5. The total number of path alternatives from S to D is 10. However, one step along the direction of k (it becomes either k
+
1 or k
-
1) obviously leads to a longer path. We present two more lemmas on direction-related properties as follows.Lemma 4.
On a shortest path, the coordinate displacements betweenS and D along the three directions satisfy
(13)
min
⁡
(
℘
)
+
mid
(
℘
)
=
max
⁡
(
℘
)
.Proof.
The number of hops on a path defined by the correct direction ofmin
⁡
(
℘
) and mid
(
℘
) is min
⁡
(
℘
)
+
mid
(
℘
), and the path traverses exactly min
⁡
(
℘
)
+
mid
(
℘
)
+
1 different points. As each node is intersected by three lines, each from one cluster, one of the three lines must belong to the max
⁡
(
℘
) cluster. It follows that the path traverses min
⁡
(
℘
)
+
mid
(
℘
)
+
1 lines in the max
⁡
(
℘
) cluster. Hence, the displacement of the two line numbers (i.e., max
⁡
(
℘
)) traversing S and D is equal to the height of the tree (
min
⁡
(
℘
)
+
mid
(
℘
)
+
1
)
-
1. We have max
⁡
(
℘
)
=
(
min
⁡
(
℘
)
+
mid
(
℘
)
+
1
)
-
1
=
min
⁡
(
℘
)
+
mid
(
℘
).Lemma 5.
The distance from sourceS to destination D is
(14)
d
(
S
,
D
)
=
min
⁡
(
℘
)
+
mid
(
℘
)
.The proof of Lemma5 simply follows the definition of d
(
S
,
D
) and Lemma 4.In triangular WMNs, given a source-destination pairS and D, the number of shortest paths satisfies the following theorem.Theorem 6.
Whenmin
⁡
(
℘
)
>
0, the number p
(
S
,
D
) of paths is determined in a grid of the two correct directions corresponding to min
⁡
(
℘
) and mid
(
℘
) as follows:
(15)
p
(
S
,
D
)
=
d
(
S
,
D
)
min
⁡
(
℘
)
,
which is the number of min
⁡
(
℘
) combinations chosen from d
(
S
,
D
) objects.Proof.
Without loss of generality, leti and j be the correct directions. Note that i is determined by min
⁡
(
℘
), while j is determined by mid
(
℘
). The coordinates of the next receiver node would lead to one hop closer to the destination along the direction i or j.
The numberp
(
S
,
D
) of paths is equal to the number of strings of i’s and j’s: i is repeated min
⁡
(
℘
) times, and j is repeated mid
(
℘
) times in a permutation of min
⁡
(
℘
)
+
mid
(
℘
) elements, that is, d
(
S
,
D
) in Lemma 5. The total number of permutations is d
(
S
,
D
)
!
=
(
min
⁡
(
℘
)
+
mid
(
℘
)
)
!, but with repetitions. Note that the same permutated strings can only be counted once. The number of duplicated permutations is min
⁡
(
℘
)
! and mid
(
℘
)
! in the direction of i and j, respectively. Then, the total number of different paths is obtained by dividing the total number of permutations by the number of duplications in both directions:
(16)
d
S
,
D
!
min
⁡
℘
!
×
mid
℘
!
=
d
(
S
,
D
)
min
⁡
(
℘
)
=
d
(
S
,
D
)
mid
(
℘
)
.For example, in Figure5, ℘
=
{
2,3
,
5
} with i and j being the correct directions, where i appears min
⁡
(
℘
)
=
2 times and j appears mid
(
℘
)
=
3 times in every permutation. A valid routing path is determined by the number of i’s and j’s as well as their relative positions in the string. For example, i
j
j
i
j, i
i
j
j
j, and i
j
i
j
j are all valid paths with two i’s and three j’s. The path p
1
=
S
→
U
→
V
→
W
→
X
→
D, which is in the set P
(
S
,
D
) of all shortest paths from S to D, can be expressed as a constrained permutation of the two correct directions, that is, i
j
j
i
j.Given the node coordinates, data packets are delivered hop by hop along the correct directions, taking the receiver of the current hop as the sender of the next hop, untilmax
⁡
(
℘
)
=
0. This can be done recursively and may help avoid the overhead of maintaining a routing table.


### 4.2. Path Counting with Channel Assignment

For a given path fromS to D with a constant number of available orthogonal channels, we need to decide the number of feasible channel assignment schemes for implementing this path by using three channels.To illustrate this problem, we show a path with a channel assigned to each hop in Figure6, which is derived from Figure 5: S
→
c
2

U
→
c
1

V
→
c
3

W
→
c
2

X
→
c
1

D, where the label c
i between two neighbor nodes is the channel assigned to the corresponding link.Figure 6
Channel assignment to realize a path fromS to D.The directed edges distributed in different layers form a feasible orthogonal channel assignment to a path fromS to D. A valid path realization allows simultaneous transmission of all the component links on the path. For example, in Figure 6, links (
S
,
U
)
c
2, (
W
,
X
)
c
2, (
U
,
V
)
c
1, (
X
,
D
)
c
1, and (
V
,
W
)
c
3 can coexist at the same time.Let the correct directions bei and j. Given ϖ orthogonal channels, the first hop has ϖ
1 channel choices, the second hop has ϖ
-
1
1 channel choices, and the third hop has ϖ
-
2
1 channel choices. Then, the three selected channels can be used repeatedly without interference; that is, the fourth hop selects the same channel as the first hop, and the fifth hop selects the same channel as the second hop and so on. Channel c
i can be selected at most d
(
S
,
D
)
/
3 times.In realizing a path using three channels at timet, the first three hops determine the channel assignment order in every three downstream hops. For example, if the first three hops are arranged in a channel order of c
2, c
1, and c
3, then the second three hops should be assigned channels in the same order. Otherwise, a realization of the path from S to D would require more channels. For example, with d
(
S
,
D
)
=
4, if the first three hops use channels in the order of c
2, c
1, and c
3, the fourth hop cannot use channels c
1 and c
3, but only c
2 or a new channel.Note that using 3 channels, the channel assignment permutations of the first three hops (i.e.,3
!) are all possible schemes for downstream three-hop groups.Lemma 7.
Whenmin
⁡
(
℘
)
≠
0, with ϖ orthogonal channels, the number of valid channel assignment schemes for a given path from source S to destination D using three channels at the same time is
(17)
λ
=
ϖ
3
×
3
!
.Based on Theorem6 and Lemma 7, we have the following theorem.Theorem 8.
When using three channels to realize a path, the number of channel assignments for all shortest paths fromS to D is
(18)
d
(
S
,
D
)
min
⁡
(
℘
)
·
λ
.Proof.
Whenmin
⁡
(
℘
)
=
0, there is only one shortest path, and the number of channel assignments for this path is obtained by Lemma 7.
We focus on a general case wheremin
⁡
(
℘
)
>
0. The number of channel assignments can be counted in two independent steps.
The first step is to count all shortest paths fromS to D in a plane mesh. This step does not assign channels. For example, Figure 5 shows one such path: S
→
U
→
V
→
W
→
X
→
D.
The second step assigns channels to the selected path using three channels without interference. For example, Figure6 shows the channel assignment for p
1 from S to D in Figure 5: S
→
c
2

U
→
c
1

V
→
c
3

W
→
c
2

X
→
c
1

D.
Since the above two steps are independent, by the multiplication principle, the total number of path realization schemes satisfies18. This result could be extended to different numbers of channels assigned to one path.


## 4.1. Path Alternatives

Every step along the shortest path fromS to D is one hop forward in one of the directions i, j, and k. The two smaller numbers of {
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} indicate the lines of parallel clusters that form a grid mesh for path selection, as illustrated in the grid of dashed lines in Figure 5. We refer to the two corresponding directions from S to D in the grid mesh as thecorrect directions.Figure 5
The shortest path alternatives in triangular meshes.Thecorrect directions ensure that the data is transmitted through one of the shortest path, where every hop selection makes one hop closer to the destination. Through the use of correct directions, we are able to reduce the problem of counting all shortest paths from S to D in triangular meshes to a problem in grid meshes.We provide an example in Figure5 to count the number of paths, where |
i
1
-
i
2
|
=
2, |
j
1
-
j
2
|
=
3, and |
k
1
-
k
2
|
=
5. The grid with dashed lines contains all the shortest paths from S to D.In a simple situation where one of{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} is 0, the dashed grid degrades to a line. Therefore, there is only one shortest path available.For convenience, let℘
=
{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
}. The correct directions are consistent with min
⁡
(
℘
) (the minimum of three elements in ℘) and mid
(
℘
) (the middle of three elements in ℘). To select a shortest path, it is necessary to remove the direction corresponding to max
⁡
(
℘
) (the maximum of three elements in ℘); otherwise, it would lead to a longer path.If the smallest in{
|
i
1
-
i
2
|
,
|
j
1
-
j
2
|
,
|
k
1
-
k
2
|
} is 1 or 2, in the corresponding direction, the sender and receiver must be on two neighbor parallel lines or two parallel lines with one line between them. We can use the corresponding grid to calculate the number p
(
S
,
D
) of paths from S to D as follows:
(12)
p
(
S
,
D
)
=
1
if
min
⁡
(
℘
)
=
0
,
mid
(
℘
)
+
1
if
min
⁡
(
℘
)
=
1
,
mid
℘
+
1
mid
℘
+
2
2
if
min
⁡
(
℘
)
=
2
.For example, in Figure5, the number of paths from S to D is determined by two directions i and j, as |
i
1
-
i
2
|
=
2 and |
j
1
-
j
2
|
=
3 are smaller than |
k
1
-
k
2
|
=
5. The total number of path alternatives from S to D is 10. However, one step along the direction of k (it becomes either k
+
1 or k
-
1) obviously leads to a longer path. We present two more lemmas on direction-related properties as follows.Lemma 4.
On a shortest path, the coordinate displacements betweenS and D along the three directions satisfy
(13)
min
⁡
(
℘
)
+
mid
(
℘
)
=
max
⁡
(
℘
)
.Proof.
The number of hops on a path defined by the correct direction ofmin
⁡
(
℘
) and mid
(
℘
) is min
⁡
(
℘
)
+
mid
(
℘
), and the path traverses exactly min
⁡
(
℘
)
+
mid
(
℘
)
+
1 different points. As each node is intersected by three lines, each from one cluster, one of the three lines must belong to the max
⁡
(
℘
) cluster. It follows that the path traverses min
⁡
(
℘
)
+
mid
(
℘
)
+
1 lines in the max
⁡
(
℘
) cluster. Hence, the displacement of the two line numbers (i.e., max
⁡
(
℘
)) traversing S and D is equal to the height of the tree (
min
⁡
(
℘
)
+
mid
(
℘
)
+
1
)
-
1. We have max
⁡
(
℘
)
=
(
min
⁡
(
℘
)
+
mid
(
℘
)
+
1
)
-
1
=
min
⁡
(
℘
)
+
mid
(
℘
).Lemma 5.
The distance from sourceS to destination D is
(14)
d
(
S
,
D
)
=
min
⁡
(
℘
)
+
mid
(
℘
)
.The proof of Lemma5 simply follows the definition of d
(
S
,
D
) and Lemma 4.In triangular WMNs, given a source-destination pairS and D, the number of shortest paths satisfies the following theorem.Theorem 6.
Whenmin
⁡
(
℘
)
>
0, the number p
(
S
,
D
) of paths is determined in a grid of the two correct directions corresponding to min
⁡
(
℘
) and mid
(
℘
) as follows:
(15)
p
(
S
,
D
)
=
d
(
S
,
D
)
min
⁡
(
℘
)
,
which is the number of min
⁡
(
℘
) combinations chosen from d
(
S
,
D
) objects.Proof.
Without loss of generality, leti and j be the correct directions. Note that i is determined by min
⁡
(
℘
), while j is determined by mid
(
℘
). The coordinates of the next receiver node would lead to one hop closer to the destination along the direction i or j.
The numberp
(
S
,
D
) of paths is equal to the number of strings of i’s and j’s: i is repeated min
⁡
(
℘
) times, and j is repeated mid
(
℘
) times in a permutation of min
⁡
(
℘
)
+
mid
(
℘
) elements, that is, d
(
S
,
D
) in Lemma 5. The total number of permutations is d
(
S
,
D
)
!
=
(
min
⁡
(
℘
)
+
mid
(
℘
)
)
!, but with repetitions. Note that the same permutated strings can only be counted once. The number of duplicated permutations is min
⁡
(
℘
)
! and mid
(
℘
)
! in the direction of i and j, respectively. Then, the total number of different paths is obtained by dividing the total number of permutations by the number of duplications in both directions:
(16)
d
S
,
D
!
min
⁡
℘
!
×
mid
℘
!
=
d
(
S
,
D
)
min
⁡
(
℘
)
=
d
(
S
,
D
)
mid
(
℘
)
.For example, in Figure5, ℘
=
{
2,3
,
5
} with i and j being the correct directions, where i appears min
⁡
(
℘
)
=
2 times and j appears mid
(
℘
)
=
3 times in every permutation. A valid routing path is determined by the number of i’s and j’s as well as their relative positions in the string. For example, i
j
j
i
j, i
i
j
j
j, and i
j
i
j
j are all valid paths with two i’s and three j’s. The path p
1
=
S
→
U
→
V
→
W
→
X
→
D, which is in the set P
(
S
,
D
) of all shortest paths from S to D, can be expressed as a constrained permutation of the two correct directions, that is, i
j
j
i
j.Given the node coordinates, data packets are delivered hop by hop along the correct directions, taking the receiver of the current hop as the sender of the next hop, untilmax
⁡
(
℘
)
=
0. This can be done recursively and may help avoid the overhead of maintaining a routing table.


## 4.2. Path Counting with Channel Assignment

For a given path fromS to D with a constant number of available orthogonal channels, we need to decide the number of feasible channel assignment schemes for implementing this path by using three channels.To illustrate this problem, we show a path with a channel assigned to each hop in Figure6, which is derived from Figure 5: S
→
c
2

U
→
c
1

V
→
c
3

W
→
c
2

X
→
c
1

D, where the label c
i between two neighbor nodes is the channel assigned to the corresponding link.Figure 6
Channel assignment to realize a path fromS to D.The directed edges distributed in different layers form a feasible orthogonal channel assignment to a path fromS to D. A valid path realization allows simultaneous transmission of all the component links on the path. For example, in Figure 6, links (
S
,
U
)
c
2, (
W
,
X
)
c
2, (
U
,
V
)
c
1, (
X
,
D
)
c
1, and (
V
,
W
)
c
3 can coexist at the same time.Let the correct directions bei and j. Given ϖ orthogonal channels, the first hop has ϖ
1 channel choices, the second hop has ϖ
-
1
1 channel choices, and the third hop has ϖ
-
2
1 channel choices. Then, the three selected channels can be used repeatedly without interference; that is, the fourth hop selects the same channel as the first hop, and the fifth hop selects the same channel as the second hop and so on. Channel c
i can be selected at most d
(
S
,
D
)
/
3 times.In realizing a path using three channels at timet, the first three hops determine the channel assignment order in every three downstream hops. For example, if the first three hops are arranged in a channel order of c
2, c
1, and c
3, then the second three hops should be assigned channels in the same order. Otherwise, a realization of the path from S to D would require more channels. For example, with d
(
S
,
D
)
=
4, if the first three hops use channels in the order of c
2, c
1, and c
3, the fourth hop cannot use channels c
1 and c
3, but only c
2 or a new channel.Note that using 3 channels, the channel assignment permutations of the first three hops (i.e.,3
!) are all possible schemes for downstream three-hop groups.Lemma 7.
Whenmin
⁡
(
℘
)
≠
0, with ϖ orthogonal channels, the number of valid channel assignment schemes for a given path from source S to destination D using three channels at the same time is
(17)
λ
=
ϖ
3
×
3
!
.Based on Theorem6 and Lemma 7, we have the following theorem.Theorem 8.
When using three channels to realize a path, the number of channel assignments for all shortest paths fromS to D is
(18)
d
(
S
,
D
)
min
⁡
(
℘
)
·
λ
.Proof.
Whenmin
⁡
(
℘
)
=
0, there is only one shortest path, and the number of channel assignments for this path is obtained by Lemma 7.
We focus on a general case wheremin
⁡
(
℘
)
>
0. The number of channel assignments can be counted in two independent steps.
The first step is to count all shortest paths fromS to D in a plane mesh. This step does not assign channels. For example, Figure 5 shows one such path: S
→
U
→
V
→
W
→
X
→
D.
The second step assigns channels to the selected path using three channels without interference. For example, Figure6 shows the channel assignment for p
1 from S to D in Figure 5: S
→
c
2

U
→
c
1

V
→
c
3

W
→
c
2

X
→
c
1

D.
Since the above two steps are independent, by the multiplication principle, the total number of path realization schemes satisfies18. This result could be extended to different numbers of channels assigned to one path.


## 5. Conclusion

We conducted a theoretical exploration on mathematical models and combinatorial characteristics of MIMO WMNs. For a single-channeled mesh, we designed a coordinate scheme and a node identity assignment scheme and derived the interference-free conditions. For multiradio multichannel WMNs, we derived rigorous formulas to count the number of shortest paths from source to destination.It is of our future interest to find some transformations to generate new link groups from the known ones. Along this direction, we plan to investigate the CPG vertex/edge transitive properties for performance improvement.



---

*Source: 185262-2015-03-09.xml*