# Borel Cayley Graph-Based Topology Control for  Consensus Protocol in Wireless Sensor Networks

Authors: Junghun Ryu; Jaewook Yu; Eric Noel; K. Wendy Tang
Journal: ISRN Sensor Networks
 (2013)

---

## Abstract

Borel Cayley graphs have been shown to be an efficient candidate topology in interconnection networks due to their small diameter, short path length, and low degree. In this paper, we propose topology control algorithms based on Borel Cayley graphs. In particular, we propose two methods to assign node IDs of Borel Cayley graphs as logical topologies in wireless sensor networks. The first one aims at minimizing communication distance between nodes, while the entire graph is imposed as a logical topology; while the second one aims at maximizing the number of edges of the graph to be used, while the network nodes are constrained with a finite radio transmission range. In the latter case, due to the finite transmission range, the resultant topology is an “incomplete” version of the original BCG. In both cases, we apply our algorithms in consensus protocol and compare its performance with that of the random node ID assignment and other existing topology control algorithms. Our simulation indicates that the proposed ID assignments have better performance when consensus protocols are used as a benchmark application.


---

## Body

## 1. Introduction

An adhoc wireless sensor network (WSN) is a self-organized and distributed network consisting of a large number of small and light sensor nodes [1, 2]. A sensor node includes a processor, a wireless radio, and various sensors to monitor and sense environmental parameters such as temperature, moisture, and pressure. In a WSN, sensor nodes interchange information and collaborate with each other to achieve a common mission. The flexibility, fault tolerance, high sensing fidelity, low cost, and rapid deployment characteristics of sensor networks create many new and exciting application areas for remote sensing [3]. Examples of ad-hoc wireless sensor networks applications include building monitoring [4], environmental sensing [5–7], traffic monitoring [8], and surveillance [9].Some WSN applications require very dense networks. Hundreds to several thousands of nodes can be deployed throughout a sensor field. For example, some machine diagnosis applications use up to 3000 nodes in a 100 m by 100 m area [10] or sensors can be deployed within tens of feet of each other for object tracking [11]. The topology of a large and dense sensor network is important to its performance. For example, topology control algorithms are essential in reducing energy consumption and radio interference [12], thus expanding the network’s lifetime.According to [13], topology control algorithms can be classified as location-based, direction-based, or neighbor-based approaches. In all these approaches, a network topology is formed in an adhoc manner based on sensor nodes’ location, direction, or some sort of neighbor ordering. However, since these approaches do not generate a predefined graph, there is no guarantee on the topology’s overall properties such as a bounded diameter and average path length.We approach topology control with predefined graphs. Structured graphs have been studied for a long time and are good candidates for interconnection networks [14, 15]. Various graph-based interconnection networks have been applied to wavelength division multiplexed optical networks [15], satellite constellations [16], and chip design [17]. In peer-to-peer overlay network schemes, various structured graphs are investigated and compared to unstructured P2P overlay network [18]. Examples of P2P overlay networks include k ring lattices with Chords [19], de Bruijn graphs with Koorde, and distance halving [20, 21]. There is theoretic analysis to apply de Bruin and Cayley graphs to P2P [22, 23]. Graph-based wireless sensor networks have also been explored by other researchers [24–28]. In general, a predefined graph topology with its deterministic connection rule facilitates performance analysis. In addition, some offer symmetry, hierarchy, and hamiltonicity, and can have a constant low degree and existing distributed routing protocol, all preferable properties for WSNs.We focus on Borel Cayley graphs, a member of Cayley graph family [29]. In [30], it was shown that Borel Cayley graphs have potential to be efficient logical topologies for dense WSNs because of their small degree and short diameter. Also, BCGs are symmetric graphs, a property that enables distributed routing [31]. One of BCG applications is the consensus protocol, a distributed node-to-node message exchange rule to drive nodes to an agreement for a quantity of interest [32]. BCGs showed good performance when compared to mesh, torus, and small world networks [33].In this paper, we propose two ID assignment algorithms for applying BCGs as logical topologies in WSNs. The first one, the chordal ring based node ID assignment algorithm, uses a specific representation (the chordal ring representation) of BCG to assign node IDs of the entire graph. Its goal is to minimize long distance communications. In the second algorithm, the distributed node ID swapping assignment, we consider the realistic constraint of network nodes’ finite transmission constraint, and thus the imposition of the entire BCG is not always possible.In the former case, when the goal is to minimize communication distance, the proposed chordal ring-based node ID assignment algorithm requires a smaller radio range (57% that of the random ID assignment). In the latter case, when the nodes are subject to a finite transmission range and the imposition of the entire BCGs is not feasible, the proposed distributed node ID swapping assignment imposes more edges of the original graph (43% more edges in comparison to random ID assignment).It must be noted that a shorter paper describing an initial version of Section5 was published in [34]. The main differences between two papers are the addition in this paper of the experiment to evaluate a consensus protocol comparing with known topology control algorithms.This paper is organized as follows. Section2 reviews the basic concept of BCGs and consensus protocol. Section 3 presents the goals of this paper. Section 4 describes our proposed algorithm to reduce the average communication distance. Section 5 presents our proposed algorithm to maximize connections of BCGs under transmission range constraints. Section 6 shows our topology control’s performance in a consensus protocol. Conclusions are presented in Section 7.


## 2. Preliminaries

In the following, we provide a definition of Cayley graphs, Borel subgroup, and Borel Cayley graphs.Definition 1 (Cayley graph [29]).
A graphC=ℂ(V,G) is a Cayley graph with vertex set V if two nodes v1,v2∈V are adjacent ⇔v1=v2*g for some g∈G, where (V,*) is a finite group and G⊂V∖{I}. G is called the generator set of the graph and I is the identity element of the finite group (V,*).The definition of a Cayley graph requires vertices to be elements of a group but does not specify a particular group.Definition 2 (Borel subgroup).
IfV is a Borel subgroup of general linear 2×2 matrices set, then
(1)V={(xy01):x=at(modp),y∈Zp,t∈Zk},
where a fixed parameter a∈Zp∖{0,1}, p is prime, and k is the order of a. That is, k is the smallest positive integer such that ak=1(modp).Definition 3 (Borel Cayley graph (BCG) [29]).
LetV be a Borel subgroup, and let G be a generator set such that G⊆V∖{I}; then B=ℬ(V,G) is a Borel Cayley graph with vertices for the 2×2 matrix elements of V and with directed edge from v to u if u=v*g, where u≠v∈V, g∈G, and * is a modulo-p multiplication chosen as a group operation.Definition 4 (GCR [29]).
A graphR is a generalized chordal ring (GCR) if nodes of R can be labeled with integers modulo the number of nodes N, and there is a divisor q of N such that node i is connected to node j if and only if node i+q(modN) is connected to node j+q(modN).The connection rules of elements are defined by connection constants. Connection constants ofi and i+q are the same according to the definition. There are four connection constants when the graph is four regular. For example, Figure 1(a) shows a degree 4 GCR with 21 nodes and q=3 classes. The connection rules can be defined as follows: let V=0,1,2,…,20. For any i∈V, if imod3=:
(2)“0”:iisconnectedtoi+3,i-3,i+4,i-10(mod21),“1”:iisconnectedtoi+6,i-6,i+7,i-4(mod21),“2”:iisconnectedtoi+9,i-9,i-7,i+10(mod21).
The connection constants for class 0 are +3, -3, +4, and -10.A Borel Cayley graph in GCR and CR representations withp=7, a=2, k=3, t1=0, t2=1, y1=1, and y2=1.
(a)
GCR representation
(b)
CR representationA chordal ring (CR) is a special case of GCR, in which every node has+1 and -1 modulo N connections. In other words, all nodes on the circumference of the ring are connected to form a Hamiltonian cycle. A Hamiltonian cycle is a graph cycle through a graph that visits each node exactly once.Proposition 5.
For any finite Cayley graph with vertex setV and any T∈V such that Tm=I, there exists a GCR representation of C with divisor q=N/m, where I is the identity element.Proposition 6.
All degree-4 Borel Cayley graphs have CR representations.The proofs of these propositions are given in [29] and not repeated here. T is referred as the transform element. ai are class representing elements.For the simplicity of GCR representation, we choseT and ai for simple representation as follows [29]:
(3)T=(1101),ai=(a001)i.
Any vertex v∈V is represented with T and ai as follows [29]:
(4)v=Tj*ai=(1j01)(ai001)=(aij01).BCGs are defined over a group of matrices. The systematic representation of BCGs from the group domain to the integer domain is useful for routing because nodes are defined in the integer domain and there is a systematic description of connections. The node ID representation in GCR (IDg(v)) is denoted as follows [29]:
(5)IDg(v)=q*j+i,
where q is k.Symmetry or vertex-transitivity is a preferable attribute for an efficient interconnection network topology. Informally, a symmetric or vertex-transitive graph looks the same from any node. This property allows to use an identical routing table at every node. Mathematically, this implies that for any two nodesa and b in the graph, there exists an automorphism of the graph that maps a to b. This property is very useful for practical implementation of interconnection networks. Most of the well-known interconnection graphs, such as the toroidal mesh, hypercube, and cube-connected cycle, exhibit such property.In Table1, we list the parameter values for BCGs used in this paper. Parameters p and a determine N and BCG parameter k. Parameters t1 and y1 were used to construct the first generator. Parameters t2 and y2 were used to construct the second generator. Using two different generators and their inverse, we construct undirected BCGs. We arbitrarily chose parameters ts and ys for generators.Table 1
Parameters of Borel Cayley Graphs.
N
p
k
a
t
1
t
2
y
1
y
2
272
17
16
3
1
2
1
1
506
23
22
7
1
7
1
1
1081
47
23
2
1
7
1
1
1474
67
22
3
1
7
1
1
2265
151
15
2
1
7
1
1


## 3. Problem Statement

A WSN can be represented as a graph, where each node of the graph corresponds to a sensor node and each edge represents a radio connection between nodes. Obviously, for dense WSNs, the number of physical neighbors (nodes within radio range) is large. For ease of description, we call the topology representing the physical neighbors ahost graph. Besides representing the number of neighbors within communication reach of each other, an edge of a host graph is also weighted by the communication distance or cost between nodes.We are interested in the problem of imposing a BCG with a small degree on a dense WSN. We call the BCG topology thetarget graph, and the host graph after the imposition, the resultant graph. We consider the two following cases: (i)
the radio range of each node covers the whole sensor deployment area. In this case, any ID assignment always produces a resultant graph with a fully connected BCG topology. But depending on the ID assignment, the communication distances between neighbors vary. So, in this case, the goal of this ID assignment is to reduce the communication distance between connected nodes;(ii)
the radio range does not cover the whole sensor deployment area. A careful node ID assignment is required to produce a resultant graph as similar as possible to the target graph (a BCG topology). In this case, the goal is to find the ID assignment that establishes the most communication edges following BCG connection rules.


### 3.1. Minimize the Average Communication Distance When the Radio Range Covers the Deployment Area

Our node ID assignment problem can now be described in terms of finding the assignment that yields the minimum sum of weights of the resultant graph after imposing a target graph onto the host graph. Figure2 illustrates these terminologies. Figure 2(a) is the host graph with each node’s physical neighbors and weights on the edges that represent the connections communication cost. Figure 2(b) is the target graph. Figures 2(c) and 2(d) show two example resultant graphs, where each graph has a different sum of weights, depending on how node IDs were assigned.Graph representation with radio range enough to cover the whole deployment area.
(a)
Host graph
(b)
Target graph
(c)
Resultant graph 1
(d)
Resultant graph 2Let a host graphG=(V,E) in the Euclidean space represent the underlying network before applying our proposed methods, with V being the set of sensor nodes and E representing the set of communication distances between nodes. We assume that the radio range of each node in the host graph is large enough to cover the whole deployment area. So the host graph is a fully connected graph. The weight of E(u,v), denoted by wuv, represents the Euclidean distance between nodes u and v. The weight between two nodes u and v with coordinates (ux,uy) and (vx,vy) is computed as
(6)wuv=(ux-vx)2+(uy-vy)2.


### 3.2. Completing Communication Edges with Finite Radio Range

This node ID assignment problem can be described as finding the maximum number of edges of the resultant graph after imposing a target graph onto the host graph. Figure3 illustrates these terminologies. Figure 3(a) is the host graph that shows the physical neighbors of each node. Figure 3(b) is the target graph. Figures 3(c) and 3(d) show two different ways to impose the target graph on the host graph, where each results in a different number of edges, depending on how node IDs were assigned.Graph representation with finite radio range.
(a)
Host graph
(b)
Target graph
(c)
Resultant graph 1
(d)
Resultant graph 2The edgeE(u,v) is determined by the radio range and the Euclidean distance between nodes u and v. The distance between two nodes u and v with coordinates (ux,uy) and (vx,vy) is wuv. The edge E(u,v) is defined as follows:
(7)E(u,v)={1ifwu,v≤radiorange0otherwise.In the remaining sections, we will propose algorithms to solve these two problems: (a) reducing the average of communication ranges of BCG-based networks and (b) completing as many as possible communication edges that follow BCG connection rules. Each problem is dealt with a distributed method. Regardless of the application type, a distributed method is preferred in wireless sensor networks.


## 3.1. Minimize the Average Communication Distance When the Radio Range Covers the Deployment Area

Our node ID assignment problem can now be described in terms of finding the assignment that yields the minimum sum of weights of the resultant graph after imposing a target graph onto the host graph. Figure2 illustrates these terminologies. Figure 2(a) is the host graph with each node’s physical neighbors and weights on the edges that represent the connections communication cost. Figure 2(b) is the target graph. Figures 2(c) and 2(d) show two example resultant graphs, where each graph has a different sum of weights, depending on how node IDs were assigned.Graph representation with radio range enough to cover the whole deployment area.
(a)
Host graph
(b)
Target graph
(c)
Resultant graph 1
(d)
Resultant graph 2Let a host graphG=(V,E) in the Euclidean space represent the underlying network before applying our proposed methods, with V being the set of sensor nodes and E representing the set of communication distances between nodes. We assume that the radio range of each node in the host graph is large enough to cover the whole deployment area. So the host graph is a fully connected graph. The weight of E(u,v), denoted by wuv, represents the Euclidean distance between nodes u and v. The weight between two nodes u and v with coordinates (ux,uy) and (vx,vy) is computed as
(6)wuv=(ux-vx)2+(uy-vy)2.


## 3.2. Completing Communication Edges with Finite Radio Range

This node ID assignment problem can be described as finding the maximum number of edges of the resultant graph after imposing a target graph onto the host graph. Figure3 illustrates these terminologies. Figure 3(a) is the host graph that shows the physical neighbors of each node. Figure 3(b) is the target graph. Figures 3(c) and 3(d) show two different ways to impose the target graph on the host graph, where each results in a different number of edges, depending on how node IDs were assigned.Graph representation with finite radio range.
(a)
Host graph
(b)
Target graph
(c)
Resultant graph 1
(d)
Resultant graph 2The edgeE(u,v) is determined by the radio range and the Euclidean distance between nodes u and v. The distance between two nodes u and v with coordinates (ux,uy) and (vx,vy) is wuv. The edge E(u,v) is defined as follows:
(7)E(u,v)={1ifwu,v≤radiorange0otherwise.In the remaining sections, we will propose algorithms to solve these two problems: (a) reducing the average of communication ranges of BCG-based networks and (b) completing as many as possible communication edges that follow BCG connection rules. Each problem is dealt with a distributed method. Regardless of the application type, a distributed method is preferred in wireless sensor networks.


## 4. Chordal Ring Based Node ID Assignment

### 4.1. CR Representation and Node ID Conversion between GCR and CR

Recall that nodes of IDn in a chordal ring (CR) have +1 and -1 modulo N connections. In other words, all nodes on the circumference of the ring are connected to form a Hamiltonian cycle. In the CR representation of BCG, the transform element and class representing elements are function of BCG parameters. Let 𝕋 be a transform element in CR, and let 𝕒i be the class representing elements in CR. Then, any vertex v∈V is represented by 𝕋 and 𝕒i as follows:
(8)v=𝕋j′*𝕒i′.Since there is no systematic representation for CR and no conversion method between GCR ID and CR ID, we propose (a) a CR representation in the integer domain and (b) a conversion method between GCR ID and CR ID. The number of classes,q, can be different in the CR and GCR domains [29]. Therefore, we use qg for the number of classes in the GCR domain and qc in the CR domain. The node ID representation in the CR domain (IDc(v)) is given as follows:
(9)IDc(v)=qc*j′+i′,
where qc is k or p and IDc(v) is the node ID of v in the CR domain. Figure 1(b) shows the CR representation of a Borel Cayley graph in the integer domain. The graphs shown in Figure 1 represent the same BCG represented in both the CR and GCR domains.By combining (5) and (8), the conversion formulation from CR ID to GCR ID is
(10)IDc(v)=qc*j′+i′,v=𝕋j′*𝕒i′=(aij01),IDg(v)=qg*j+i,
where IDg(v) is the node ID representation in the GCR domain.Similarly, the conversion formulation from GCR ID to CR ID is(11)IDg(v)=qg*j+i,v=Tj*ai=(aij01)=𝕋j′*𝕒i′,IDc(v)=qc*j′+i′.
Based on the set of class representing elements 𝕒 given in [29], the integers i′ and j′ can be calculated from Algorithm 1. Note that Algorithm 1 does not have any infinite loop since the matrix v is 𝕋j′ multiplied by 𝕒i′.Algorithm 1:Calculating j′ and i′.
Require: 𝕋 is nonsingular.
(1)procedure CALCULATING j′ AND i′(𝕋,v)
(2)j′,i′←0
(3)while  Not v∈𝕒  do          ⊳ Find j′ of 𝕋 using (8)
(4)v←𝕋-1v
(5)j′←j′+1
(6)end while
(7)while  v≠𝕒i′  do           ⊳ Find i′ of 𝕒i′ using (8)
(8)i′←i′+1
(9)end while
(10)returnj′,i′
(11)end procedureWe already discussed the relationship between GCR ID and the CR ID. The GCR and CR representations of BCG have different advantages. The GCR representation of BCG has an optimal routing algorithm to identify the shortest paths between any sources and destination pairs [31]. On the other hand, the CR representation supports a Hamiltonian cycle and a simple suboptimal routing algorithm. Therefore, we assign IDs in the CR domain to minimize the communication distance and then map them to the GCR domain for optimal routing performance.


### 4.2. Algorithm

The chordal ring-based method (CR assignment) consists of three main steps:(1)
making a Hamiltonian cycle in the CR domain;(2)
converting node IDs from the CR domain to the GCR domain;(3)
establishing edges.Figure4 illustrates the CR assignment algorithm. There, the algorithm starts by choosing the lowest weighted edge of sensor node ID 0 and then assigns the ID 1 plus node ID 0 to the corresponding node (Figure 4(b)). The next node selects the edge with the lowest weight among edges that are not connected to already assigned nodes. The algorithm repeats until the last node ID is assigned (Figure 4(c)). Then, the node IDs are mapped from the CR domain to the GCR domain (Figure 4(d)). Finally, the actual connections are established using GCR connection constants following the BCG connection rule (Figure 4(e)). Algorithm 2 summarizes the CR assignment.Algorithm 2:CR assignment.
(1)procedure CR ASSIGNMENT (𝕋,𝕒)
(2)v←v0                  ⊳v0: starting node
(3)IDc(v)←0
(4)while  IDc(v)≠N  do         ⊳ Until all nodes are assigned
(5)vn← select unassigned node closest to v
(6)IDc(vn)←IDc(v)+1
(7)v←vn
(8)end while
(9)   Convert all IDs from CR to GCR⊳ Using (10)
(10) Establish the remained edges using GCR constants
(11)end procedureIllustration of CR assignment. Note that each alphabet represents a physical sensor node.
(a)
Select the closet edge
(b)
Assign the next node ID to the selected node
(c)
All sensors are assigned node IDs using a Hamiltonian cycle
(d)
Convert to GCR
(e)
Establish connectionsThe CR assignment guarantees that at least the lowest weighted edges of consecutive node IDs are selected as communication links, except for the edge between the starting node and the last assigned node. As a result, we optimize two out of four edges per node excluding first and last ones. We expect the total weights of edges from the CR assignment to be smaller than those of a random ID assignment. Moreover, the CR assignment is a fully distributed algorithm and does not require preassigned node IDs.


### 4.3. Average Communication Distance

We define the average communication distance as the average weights of the target graph communication distance between pairs of nodes. Our goal is to minimize the average communication distance. To evaluate our assignment algorithm, we calculated the expected communication distance analytically. From (6), the expected communication distance between randomly chosen positions is as follows:
(12)E(D)=1a2b2∬0b∬0awuvduxdvxduydvy,
where a and b represent the horizontal and vertical dimensions, respectively.Figure5 shows the average communication distance for each node ID assignment algorithm where a,b=100 m. The random assignment algorithm uniformly and randomly assigns a unique BCG node ID to all the sensors. We call the resultant network topology with Random assignment BCG-0 and the resultant network topology with CR assignment BCG-1. The average weight of the random assignment and the expected distance are both approximately equal to 52.Figure 5
Average communication distance.We also calculated the standard deviation for the average communication distance from 100 CR assignment samples. The results show that selection of the initial node does not affect the average communication distance. For graphs of sizesN=272, 506, 1081, 1474, and 2265, the standard deviations for the CR assignment were 0.58, 0.53, 0.62, 0.72, and 0.60, respectively.


## 4.1. CR Representation and Node ID Conversion between GCR and CR

Recall that nodes of IDn in a chordal ring (CR) have +1 and -1 modulo N connections. In other words, all nodes on the circumference of the ring are connected to form a Hamiltonian cycle. In the CR representation of BCG, the transform element and class representing elements are function of BCG parameters. Let 𝕋 be a transform element in CR, and let 𝕒i be the class representing elements in CR. Then, any vertex v∈V is represented by 𝕋 and 𝕒i as follows:
(8)v=𝕋j′*𝕒i′.Since there is no systematic representation for CR and no conversion method between GCR ID and CR ID, we propose (a) a CR representation in the integer domain and (b) a conversion method between GCR ID and CR ID. The number of classes,q, can be different in the CR and GCR domains [29]. Therefore, we use qg for the number of classes in the GCR domain and qc in the CR domain. The node ID representation in the CR domain (IDc(v)) is given as follows:
(9)IDc(v)=qc*j′+i′,
where qc is k or p and IDc(v) is the node ID of v in the CR domain. Figure 1(b) shows the CR representation of a Borel Cayley graph in the integer domain. The graphs shown in Figure 1 represent the same BCG represented in both the CR and GCR domains.By combining (5) and (8), the conversion formulation from CR ID to GCR ID is
(10)IDc(v)=qc*j′+i′,v=𝕋j′*𝕒i′=(aij01),IDg(v)=qg*j+i,
where IDg(v) is the node ID representation in the GCR domain.Similarly, the conversion formulation from GCR ID to CR ID is(11)IDg(v)=qg*j+i,v=Tj*ai=(aij01)=𝕋j′*𝕒i′,IDc(v)=qc*j′+i′.
Based on the set of class representing elements 𝕒 given in [29], the integers i′ and j′ can be calculated from Algorithm 1. Note that Algorithm 1 does not have any infinite loop since the matrix v is 𝕋j′ multiplied by 𝕒i′.Algorithm 1:Calculating j′ and i′.
Require: 𝕋 is nonsingular.
(1)procedure CALCULATING j′ AND i′(𝕋,v)
(2)j′,i′←0
(3)while  Not v∈𝕒  do          ⊳ Find j′ of 𝕋 using (8)
(4)v←𝕋-1v
(5)j′←j′+1
(6)end while
(7)while  v≠𝕒i′  do           ⊳ Find i′ of 𝕒i′ using (8)
(8)i′←i′+1
(9)end while
(10)returnj′,i′
(11)end procedureWe already discussed the relationship between GCR ID and the CR ID. The GCR and CR representations of BCG have different advantages. The GCR representation of BCG has an optimal routing algorithm to identify the shortest paths between any sources and destination pairs [31]. On the other hand, the CR representation supports a Hamiltonian cycle and a simple suboptimal routing algorithm. Therefore, we assign IDs in the CR domain to minimize the communication distance and then map them to the GCR domain for optimal routing performance.


## 4.2. Algorithm

The chordal ring-based method (CR assignment) consists of three main steps:(1)
making a Hamiltonian cycle in the CR domain;(2)
converting node IDs from the CR domain to the GCR domain;(3)
establishing edges.Figure4 illustrates the CR assignment algorithm. There, the algorithm starts by choosing the lowest weighted edge of sensor node ID 0 and then assigns the ID 1 plus node ID 0 to the corresponding node (Figure 4(b)). The next node selects the edge with the lowest weight among edges that are not connected to already assigned nodes. The algorithm repeats until the last node ID is assigned (Figure 4(c)). Then, the node IDs are mapped from the CR domain to the GCR domain (Figure 4(d)). Finally, the actual connections are established using GCR connection constants following the BCG connection rule (Figure 4(e)). Algorithm 2 summarizes the CR assignment.Algorithm 2:CR assignment.
(1)procedure CR ASSIGNMENT (𝕋,𝕒)
(2)v←v0                  ⊳v0: starting node
(3)IDc(v)←0
(4)while  IDc(v)≠N  do         ⊳ Until all nodes are assigned
(5)vn← select unassigned node closest to v
(6)IDc(vn)←IDc(v)+1
(7)v←vn
(8)end while
(9)   Convert all IDs from CR to GCR⊳ Using (10)
(10) Establish the remained edges using GCR constants
(11)end procedureIllustration of CR assignment. Note that each alphabet represents a physical sensor node.
(a)
Select the closet edge
(b)
Assign the next node ID to the selected node
(c)
All sensors are assigned node IDs using a Hamiltonian cycle
(d)
Convert to GCR
(e)
Establish connectionsThe CR assignment guarantees that at least the lowest weighted edges of consecutive node IDs are selected as communication links, except for the edge between the starting node and the last assigned node. As a result, we optimize two out of four edges per node excluding first and last ones. We expect the total weights of edges from the CR assignment to be smaller than those of a random ID assignment. Moreover, the CR assignment is a fully distributed algorithm and does not require preassigned node IDs.


## 4.3. Average Communication Distance

We define the average communication distance as the average weights of the target graph communication distance between pairs of nodes. Our goal is to minimize the average communication distance. To evaluate our assignment algorithm, we calculated the expected communication distance analytically. From (6), the expected communication distance between randomly chosen positions is as follows:
(12)E(D)=1a2b2∬0b∬0awuvduxdvxduydvy,
where a and b represent the horizontal and vertical dimensions, respectively.Figure5 shows the average communication distance for each node ID assignment algorithm where a,b=100 m. The random assignment algorithm uniformly and randomly assigns a unique BCG node ID to all the sensors. We call the resultant network topology with Random assignment BCG-0 and the resultant network topology with CR assignment BCG-1. The average weight of the random assignment and the expected distance are both approximately equal to 52.Figure 5
Average communication distance.We also calculated the standard deviation for the average communication distance from 100 CR assignment samples. The results show that selection of the initial node does not affect the average communication distance. For graphs of sizesN=272, 506, 1081, 1474, and 2265, the standard deviations for the CR assignment were 0.58, 0.53, 0.62, 0.72, and 0.60, respectively.


## 5. Distributed Node ID Swapping Assignment

In the previous section, we showed the CR assignment algorithm for reducing the average communication distance without radio range constraint. In this section, we propose the distributed node ID swapping assignment for completing communication edges with radio range constraint. The distributed node ID swapping assignment (Dist-swap assignment) consists of four main steps executed by the current node:(1)
broadcast its node ID to its physical neighbors;(2)
collect IDs of physical neighbors that can be swapped;(3)
select the best-fit node ID to be swapped with;(4)
swap node IDs and update each logical neighbor table of its physical neighbors.


### 5.1. Terminologies

We denote the logical node ID of nodex by xid and define the following. (i)
D(xid): set of logical neighbors of node ID xid in the target graph;(ii)
T(x): set of logical IDs of node x’s physical neighbors;(iii)
L(xid,y)=|D(xid)∩T(y)|: the number of logical neighbors of node ID xid that are also physical neighbors of node y.We define four different packet types.(1)
Token packet: forwarded by nodes and used to initiate the node swapping algorithm by the node recipient. Also contains counter reptCnt.(2)
Info packet: used by the current node holding the token to broadcast xid to its physical neighbors so as to identify candidate nodes to be swapped.(3)
Request packet: Supports collection of candidate nodes. If a physical neighbor node y receiving an Info packet from node x determines that it can be swapped, it sends a Request packet back to node x. The Request packet contains yid, L(yid,y), and L(xid,y).(4)
Swap packet: used by the current node x to announce to its physical neighbors swapping with node y. Contains the pair (xid,yid). Nodes having those node IDs in T() need to update the swapped IDs.


### 5.2. Assumption

We assume that (a) a host graph is a connected graph (there is a path between all node pairs), (b) nodes have preassigned unique IDs ranging from0 to N-1, (c) T(x) (a set of logical IDs of its physical neighbors) at each node x∈V is obtained before the swapping process, and (d) the order of nodes to perform operation is based on token method.


### 5.3. Algorithm

The Dist-swap assignment is performed by one node at a time using a token method (i.e., there is one token in a network, and only the node holding the token executes the swapping algorithm). To prevent an infinite loop, we rely on a token counter (repCnt) that tracks the number of times the token is being passed around. At the beginning of the Dist-swap assignment, the node that starts the operation sets repCnt to repTotal that was heuristically selected based on previous simulation studies. As the token travels around the network, each node decreases repCnt by one before forwarding the token to the next node, and the Dist-swap assignment ends once repCnt reaches zero.We describe in detail the Dist-swap assignment as follows:(i) the following describes the Dist-swap assignment operation after nodex receives a Token packet. (1)
A nodex receives a Token packet.
(a)
If|D(xid)|=L(xid,x), forward the Token packet randomly to one of its physical neighbors.(b)
Otherwise, send an Info packet to all its physical neighbors.(2)
Nodex collects the Request packets.
(a)
If there is no Request packet received, forward the Token packet randomly to one of its physical neighbors.(3)
Nodex creates a list of candidate nodes. A node y is a candidate node if L(yid,x)+L(xid,y)-L(xid,x)-L(yid,y)>0.
(a)
If there is no candidate node, forward the Token packet randomly to one of its physical neighbors.(b)
Otherwise, select the nodey maximizing the number of logical neighbors when two node IDs are swapped.(4)
Nodex sends Swap packet with (xid,yid).(5)
Nodex sends Token packet to node y.First, node x determines whether or not it needs to execute the swapping process based on its current number of logical neighbor IDs in the physical neighbors and its target number of logical neighbors in the target graph. If those are not the same, node x sends an Info packet to its physical neighbors. After receiving Request packets from its physical neighbors, node x determines which node ID swapping is the most beneficial. Because the Request packet from node y contains yid, L(yid,y), and L(xid,y), node x can calculate the change in the number of logical neighbors from the physical neighbors when node IDs xid and yid are swapped. If a candidate node for swapping exists, node x sends a Swap packet with its own node ID and the selected node ID to its neighbors.(ii) The following illustrates the operation after nodey receives an Info packet.(1)
A nodey receives an Info packet.(2)
Nodey calculates the number of its logical neighbors among its physical neighbors if it was assigned node ID xid.
(a)
If that number is larger than or equal to the number of logical neighbors of the current ID, send theRequest packet.(b)
Otherwise, ignore theInfo packet.To determine whether or not to reply with a Request packet, node y checks the number of its logical neighbors that would be assigned to its physical neighbors if it were assigned node ID xid. If it is larger than that with the current node ID, node y sends a Request packet.(iii) The following shows the operation when nodez receives a Swap packet.(1)
A nodez receives a Swap packet that contains node IDs (xid,yid).
(a)
Ifzid is equal to yid, change zid to xid and send a Swap packet with node IDs (zid,xid) to its physical neighbors.(b)
Ifzid is equal to xid, ignore the Swap packet.(c)
Otherwise, changexid to yid in T(z).Swap packet contains node IDs (xid,yid). If yid is the same as zid, then the Request packet sent by z is accepted. So, node z changes its node ID to xid and sends a Swap packet with (zid,xid) to its physical neighbors so that they update their T()s. When xid is the same as zid, node z ignores that packet. Otherwise, node z updates T(z) to reflect that node ID xid is changed to yid.


### 5.4. Example

Next, we use an example to illustrate the Dist-swap assignment operation. The physical nodes of the host graph are denoted by nodesx, y, and z, and the logical node IDs of the target graph are denoted by 1,2,…, and so forth. Figure 6 shows that logical node IDs 5, 8, and 15 are assigned to nodes x, y, and z, respectively. We assume that the target graph has a simple connection rule; namely, node ID i is connected to i-4, i-2, i+2, and i+4. Given the connection rule in the target graph, the neighbors of node ID 5 in the target graph are: D(5)={1,3,7,9}. Similarly, D(8)={4,6,10,12}, and D(15)={11,13,17,19}.Figure 6
Host graph used as example of Dist-swap assignment.First, nodex receiving a Token packet decides whether or not to perform the swapping process based on the current number of logical neighbors among its physical neighbors (L(5,x)). The number of logical neighbors among the physical neighbors is not the same as the maximum number of logical neighbors 4 since T(x)={4,6,8,13,15}, D(5)={1,3,7,9} and L(5,x)=0. So, node x sends an Info packet to its physical neighbor nodes. Swapping node IDs is beneficial to node y because L(8,y) is zero and L(5,y) is two, which means node y gains two more logical neighbors after swapping IDs with node ID 5. Thus, node y sends the Request packet to node x. Node z also sends a Request packet to node x through the same process. Finally, node x determines to swap IDs with node y because L(8,x)+L(5,y)=4 is greater than L(15,x)+L(5,z)=3.


### 5.5. Completeness of Resultant Graph

Recall that an efficient ID assignment method should incorporate as many as possible target graph edges in the resultant graph from a given host graph, where sensor nodes are limited to a specific radio range. Therefore, to measure the performance of our assignment methods, we defineRc, the ratio of the number of edges of the resultant graph over that of the target graph. That is,
(13)Rc=NumberofedgesinresultantgraphNumberofedgesintargetgraph.For a given radio transmission range, the assignment method with the largestRc is the most efficient since most edges of the target graphs are incorporated in the resultant graph. We define the resultant network topology with Dist-swap assignment BCG-2. Figure 7 shows Rc for BCGs target graphs with N=1081. The Dist-swap assignment (BCG-2) shows larger Rc than that of the random assignment (BCG-0). Especially, with 50 m radio range in 100 m by 100 m area, it showed 43% more edges.Figure 7
Edge construction percentage with distributed node ID assignment.When applying BCGs to wireless sensor networks, we also need to consider network connectivity. Because the Dist-swap assignment maximizesRc without considering network connectivity, we apply a random node selection algorithm on processed nodes that do not have the right number of logical neighbors. We define the resultant graph from this method BCG-3. Table 2 summarizes resultant graphs from our proposed algorithms.Table 2
Summary of our proposed algorithms.
Resultant graphs
Algorithms
BCG-0
Random assignment
BCG-1
Chordal ring based node ID assignment
BCG-2
Distributed node ID swapping assignment
BCG-3
Distributed node ID swapping assignment and random node selectionFigure8 shows the percentage of connected network function of assignments for 100 network samples. BCG-0 with 105 m radio range results in a 100% connected network. BCG-2 and BCG-3 require 65 m and 10 m radio range, respectively, to produce a connected network. All connections of BCG-2 are satisfied by the connection rules of BCGs. However, BCG-3 has non-BCG connections since some are logical neighbors randomly selected for improved connectivity.Figure 8
Connected network percentage with node ID assignments.


## 5.1. Terminologies

We denote the logical node ID of nodex by xid and define the following. (i)
D(xid): set of logical neighbors of node ID xid in the target graph;(ii)
T(x): set of logical IDs of node x’s physical neighbors;(iii)
L(xid,y)=|D(xid)∩T(y)|: the number of logical neighbors of node ID xid that are also physical neighbors of node y.We define four different packet types.(1)
Token packet: forwarded by nodes and used to initiate the node swapping algorithm by the node recipient. Also contains counter reptCnt.(2)
Info packet: used by the current node holding the token to broadcast xid to its physical neighbors so as to identify candidate nodes to be swapped.(3)
Request packet: Supports collection of candidate nodes. If a physical neighbor node y receiving an Info packet from node x determines that it can be swapped, it sends a Request packet back to node x. The Request packet contains yid, L(yid,y), and L(xid,y).(4)
Swap packet: used by the current node x to announce to its physical neighbors swapping with node y. Contains the pair (xid,yid). Nodes having those node IDs in T() need to update the swapped IDs.


## 5.2. Assumption

We assume that (a) a host graph is a connected graph (there is a path between all node pairs), (b) nodes have preassigned unique IDs ranging from0 to N-1, (c) T(x) (a set of logical IDs of its physical neighbors) at each node x∈V is obtained before the swapping process, and (d) the order of nodes to perform operation is based on token method.


## 5.3. Algorithm

The Dist-swap assignment is performed by one node at a time using a token method (i.e., there is one token in a network, and only the node holding the token executes the swapping algorithm). To prevent an infinite loop, we rely on a token counter (repCnt) that tracks the number of times the token is being passed around. At the beginning of the Dist-swap assignment, the node that starts the operation sets repCnt to repTotal that was heuristically selected based on previous simulation studies. As the token travels around the network, each node decreases repCnt by one before forwarding the token to the next node, and the Dist-swap assignment ends once repCnt reaches zero.We describe in detail the Dist-swap assignment as follows:(i) the following describes the Dist-swap assignment operation after nodex receives a Token packet. (1)
A nodex receives a Token packet.
(a)
If|D(xid)|=L(xid,x), forward the Token packet randomly to one of its physical neighbors.(b)
Otherwise, send an Info packet to all its physical neighbors.(2)
Nodex collects the Request packets.
(a)
If there is no Request packet received, forward the Token packet randomly to one of its physical neighbors.(3)
Nodex creates a list of candidate nodes. A node y is a candidate node if L(yid,x)+L(xid,y)-L(xid,x)-L(yid,y)>0.
(a)
If there is no candidate node, forward the Token packet randomly to one of its physical neighbors.(b)
Otherwise, select the nodey maximizing the number of logical neighbors when two node IDs are swapped.(4)
Nodex sends Swap packet with (xid,yid).(5)
Nodex sends Token packet to node y.First, node x determines whether or not it needs to execute the swapping process based on its current number of logical neighbor IDs in the physical neighbors and its target number of logical neighbors in the target graph. If those are not the same, node x sends an Info packet to its physical neighbors. After receiving Request packets from its physical neighbors, node x determines which node ID swapping is the most beneficial. Because the Request packet from node y contains yid, L(yid,y), and L(xid,y), node x can calculate the change in the number of logical neighbors from the physical neighbors when node IDs xid and yid are swapped. If a candidate node for swapping exists, node x sends a Swap packet with its own node ID and the selected node ID to its neighbors.(ii) The following illustrates the operation after nodey receives an Info packet.(1)
A nodey receives an Info packet.(2)
Nodey calculates the number of its logical neighbors among its physical neighbors if it was assigned node ID xid.
(a)
If that number is larger than or equal to the number of logical neighbors of the current ID, send theRequest packet.(b)
Otherwise, ignore theInfo packet.To determine whether or not to reply with a Request packet, node y checks the number of its logical neighbors that would be assigned to its physical neighbors if it were assigned node ID xid. If it is larger than that with the current node ID, node y sends a Request packet.(iii) The following shows the operation when nodez receives a Swap packet.(1)
A nodez receives a Swap packet that contains node IDs (xid,yid).
(a)
Ifzid is equal to yid, change zid to xid and send a Swap packet with node IDs (zid,xid) to its physical neighbors.(b)
Ifzid is equal to xid, ignore the Swap packet.(c)
Otherwise, changexid to yid in T(z).Swap packet contains node IDs (xid,yid). If yid is the same as zid, then the Request packet sent by z is accepted. So, node z changes its node ID to xid and sends a Swap packet with (zid,xid) to its physical neighbors so that they update their T()s. When xid is the same as zid, node z ignores that packet. Otherwise, node z updates T(z) to reflect that node ID xid is changed to yid.


## 5.4. Example

Next, we use an example to illustrate the Dist-swap assignment operation. The physical nodes of the host graph are denoted by nodesx, y, and z, and the logical node IDs of the target graph are denoted by 1,2,…, and so forth. Figure 6 shows that logical node IDs 5, 8, and 15 are assigned to nodes x, y, and z, respectively. We assume that the target graph has a simple connection rule; namely, node ID i is connected to i-4, i-2, i+2, and i+4. Given the connection rule in the target graph, the neighbors of node ID 5 in the target graph are: D(5)={1,3,7,9}. Similarly, D(8)={4,6,10,12}, and D(15)={11,13,17,19}.Figure 6
Host graph used as example of Dist-swap assignment.First, nodex receiving a Token packet decides whether or not to perform the swapping process based on the current number of logical neighbors among its physical neighbors (L(5,x)). The number of logical neighbors among the physical neighbors is not the same as the maximum number of logical neighbors 4 since T(x)={4,6,8,13,15}, D(5)={1,3,7,9} and L(5,x)=0. So, node x sends an Info packet to its physical neighbor nodes. Swapping node IDs is beneficial to node y because L(8,y) is zero and L(5,y) is two, which means node y gains two more logical neighbors after swapping IDs with node ID 5. Thus, node y sends the Request packet to node x. Node z also sends a Request packet to node x through the same process. Finally, node x determines to swap IDs with node y because L(8,x)+L(5,y)=4 is greater than L(15,x)+L(5,z)=3.


## 5.5. Completeness of Resultant Graph

Recall that an efficient ID assignment method should incorporate as many as possible target graph edges in the resultant graph from a given host graph, where sensor nodes are limited to a specific radio range. Therefore, to measure the performance of our assignment methods, we defineRc, the ratio of the number of edges of the resultant graph over that of the target graph. That is,
(13)Rc=NumberofedgesinresultantgraphNumberofedgesintargetgraph.For a given radio transmission range, the assignment method with the largestRc is the most efficient since most edges of the target graphs are incorporated in the resultant graph. We define the resultant network topology with Dist-swap assignment BCG-2. Figure 7 shows Rc for BCGs target graphs with N=1081. The Dist-swap assignment (BCG-2) shows larger Rc than that of the random assignment (BCG-0). Especially, with 50 m radio range in 100 m by 100 m area, it showed 43% more edges.Figure 7
Edge construction percentage with distributed node ID assignment.When applying BCGs to wireless sensor networks, we also need to consider network connectivity. Because the Dist-swap assignment maximizesRc without considering network connectivity, we apply a random node selection algorithm on processed nodes that do not have the right number of logical neighbors. We define the resultant graph from this method BCG-3. Table 2 summarizes resultant graphs from our proposed algorithms.Table 2
Summary of our proposed algorithms.
Resultant graphs
Algorithms
BCG-0
Random assignment
BCG-1
Chordal ring based node ID assignment
BCG-2
Distributed node ID swapping assignment
BCG-3
Distributed node ID swapping assignment and random node selectionFigure8 shows the percentage of connected network function of assignments for 100 network samples. BCG-0 with 105 m radio range results in a 100% connected network. BCG-2 and BCG-3 require 65 m and 10 m radio range, respectively, to produce a connected network. All connections of BCG-2 are satisfied by the connection rules of BCGs. However, BCG-3 has non-BCG connections since some are logical neighbors randomly selected for improved connectivity.Figure 8
Connected network percentage with node ID assignments.


## 6. Simulation

### 6.1. Consensus Protocol

We use the consensus protocol as a benchmark to evaluate our topology control algorithms. Consensus protocol is a distributed node-to-node message exchange rule to reach a network-wide agreement over a quantity of interest (e.g., average of sensory data). Consensus protocol has a long history in distributed computing and has been used in a variety of applications. Moreover, it has been widely accepted as a reliable measure of data fusion performance of network topologies [35, 36]. In WSN, consensus protocol research focused on time synchronization and gossip algorithms [37–39]. Readers interested in more detail on consensus protocol and its application are referred to [40].The consensus agreement value can be the average, the maximum, the minimum, or any function and only depends on the initial states of the nodes in the network. Furthermore, the speed of consensus is a good measure of the efficiency of a network topology to distribute information. In this study, we consider the distributed average consensus protocol proposed in [40] which we summarize next.Let us consider a network system of which logical network topology is represented by an unweighted, undirected graph. Each nodev∈V in the system communicates its state value xv to its immediate neighbors N(v):=u:ev,u∈E(V), where E is an edge set. At each iteration τ, nodes exchange their current state values xv(τ) with their immediate neighbors. Given the state values xu(τ) received from their neighbors u∈N(v), each node u updates its state according to
(14)xu(t+1)=xu(t)+1ω∑v∈N(u)‍(xv(t)-xu(t)),
where ω is typically 0<1/ω<1/2dmax(G) and dmax(G) is the largest nodal degree. We set ω to 2×dmax(G)+1 in this paper. Consensus convergence can be controlled by ω value. However, finding an optimal ω value is out of scope for this paper.Following the method in [41], we use the average consensus protocol (14) to measure the information fusion performance of the network generated by the proposed topology control protocol. BCGs have already been shown to exhibit better consensus protocol performance than mesh, torus, and small world networks [33]. However, that research compared only topology level not considering nodes’ physical geometric information and radio range. In this paper, we compare a BCG with other network topologies when applied to wireless sensor network.


### 6.2. Simulation Setup

We evaluated our proposed topology control algorithms in terms of consensus speed and power consumption. The simulations were executed on100 host graphs, each with sensors uniformly and randomly distributed over a 100 m × 100 m area.Consensus protocol was initialized with nodes state value set to integers randomly chosen between-5 and 5 inclusive. We declared a network topology to have reached an agreement once all node values equal the average of all initial state values within a precision of 0.001. The performance of the consensus protocol was measured as the number of steps needed to reach a network-wide consensus.We also computed the energy needed for all the nodes in the network to reach a consensus using the average consensus protocol. To do this, we utilized the radio model described in [42]. For the sake of simplicity, we only considered the energy consumptions from data transmission (Etx) and reception (Erx) defined as follows:
(15)Etx=B(β1+β2ω(v,u)n),Erx=Bγ,
where n is the path loss exponent which, in typical, ranges from 2 to 6. The constants β1, β2, and γ are the energy dissipated by the transmitter module, transmit amplifier, and the receiver module, respectively. We denote the estimated distance between nodes v and u by ω(v,u) and the length of the message by B. We set n=2, equivalent to the free-space pass loss model, and assume that a sensor node v, regardless of the topology control protocols considered, can adjust its transmission power to reach its neighbors w. The parameters used in the simulation are summarized in  Table 3.Table 3
Radio model parameters.
Parameters
Values
n
2
β
1
45 nJ/bit
β
2
10 pJ/bit
γ
135 nJ/bit
B
320 bits (=40 bytes)Using the average consensus protocol, a node transmits and receives to and from each of its neighbors at every iteration. Thus, the node’s energy consumed by the network at theτth iteration is given by
(16)P0(v)=τB(∑∀(v,u)∈Ev≠u‍(β1+β2ω(v,u)n)+γdeg(v)),
where deg(v) is the number of logical neighbors, (v,u) is a logical connection, and E denotes the edge set. The average nodal energy consumption is given by P0¯=∑v∈V‍P0(v)/|V|. We call this power consumption model Power model0.In wireless sensor networks, a network can support multicasting routing to transmit at once to multiple nodes inside the radio range. Then power consumption is calculated not by each communication edge but by the maximum distance communication edge as follows:(17)P1(v)=τB(β1+β2Max{ω(v,u),u∈adj(v)}n+γdeg(v)).
We call this power consumption model Power model1.


### 6.3. Comparison between BCG-0 and BCG-1

Figure9 shows the histograms of the communication distance for N=1081 generated by the proposed node ID assignment algorithms. The histogram of the CR assignment (BCG-1) exhibits a right skewed distribution with a high frequency of short edges. The Dist-swap assignment (BCG-2) shows that all connection distance are under 80 m. We obtained similar histograms for the network sizes listed in Table 1. We compared power consumption between the random assignment and the CR assignment because they require a radio range that covers the whole node deployment area. Figure 10 summarizes the resulting consensus protocol energy consumption. We found that BCG-1 consumed 8% less energy than BCG-0 with power model 0 and 2% less with power model 1.Histograms of communication distance by the proposed algorithms withN=1081.
(a)
Random assignment (BCG-0)
(b)
CR assignment (BCG-1)
(c)
Dist-swap assignment (BCG-2)Figure 10
Power consumption comparison between BCG-0 and BCG-1.


### 6.4. Comparison between Our Proposed Topology Control and Existing Topology Controls

We compared our topology control algorithms with existing topology controls. The evaluation was done in terms of diameter, average path length, consensus steps, and nodal energy consumption.We used the following topologies for comparison against our approach.(i)
Max: network where all nodes within the maximum radio range are logical neighbors. Without any topology control, a network is called Max topology.(ii)
E-MST [43]: the Euclidean minimum spanning tree is a minimum spanning tree whose edge weight is the distance between nodes. This algorithm minimizes the summed weight of edges and generates a connected network.(iii)
K-Neigh [44]: network where the number of neighbors of a node equals to or is slightly below a given value k.(iv)
Gabriel Graph [45]: a planar graph (no edges cross one another) supports geographical routings and is defined such that an edge (v,u) exists if no other node is inside the circle with the diameter uv.Figure11 provides illustrations of the topologies constructed with (a) the random assignment (BCG-0), (b) the Dist-swapping assignment (BCG-2), (c) Max, (d) E-MST, (e) K-Neigh, and (f) Gabriel graph. For ease of description, we show sample graphs with N=272. However, we simulated with N=1081 in this section.BCG-0, BCG-3 with radio range 40 m, Max with 25 m, E-MST, K-Neigh withk=10 and 25 m, Gabriel graph. N=272.
(a)
BCG-0
(b)
BCG-3
(c)
Max
(d)
E-MST
(e)
K-Neigh
(f)
Gabriel graphFigures12 and 13 show the diameter and average path length function of the transmission range, respectively. We only compared the cases where the resultant graph is a connected graph. From these figures, we confirm again that the BCGs have the smallest diameter and the shortest average path length for a given radio range except Max topology. This is because as a radio range increases, BCGs have a constant number of logical neighbors, while Max topology has much more logical neighbors than others.Figure 12
Comparison of diameters.Figure 13
Comparison of average path lengths.From Figure14, at radio range 30 m, consensus protocol convergence for BCG-3 was 35.5, 2932, and 15.9 times faster than that of Gabriel, E-MST, and K-Neigh topologies. At radio range 50m, convergence of BCG-3 was 81.2, 6756.9, and 39.9 times faster than that of Gabriel, E-MST, and K-Neigh topologies. Even though Max topology has the best consensus steps, due to its large number of logical neighbors, it consumed 23 times more nodal power than BCG in Figure 15.Figure 14
Comparison of consensus steps.Figure 15
Comparison of power model0 for consensus protocol.When considering multicast routing (Power model1), the Max topology has an obvious advantage as only the maximum radio range is used in the power consumption computation. However, even with this advantage, our simulations showed that BCG continues to outperform the Max topology in Figure 16. This better performance can be explained by the fact that the Max topology has a larger number of logical neighbors and hence larger power is consumed at the receiver modules.Figure 16
Comparison of power model1 for consensus protocol.


## 6.1. Consensus Protocol

We use the consensus protocol as a benchmark to evaluate our topology control algorithms. Consensus protocol is a distributed node-to-node message exchange rule to reach a network-wide agreement over a quantity of interest (e.g., average of sensory data). Consensus protocol has a long history in distributed computing and has been used in a variety of applications. Moreover, it has been widely accepted as a reliable measure of data fusion performance of network topologies [35, 36]. In WSN, consensus protocol research focused on time synchronization and gossip algorithms [37–39]. Readers interested in more detail on consensus protocol and its application are referred to [40].The consensus agreement value can be the average, the maximum, the minimum, or any function and only depends on the initial states of the nodes in the network. Furthermore, the speed of consensus is a good measure of the efficiency of a network topology to distribute information. In this study, we consider the distributed average consensus protocol proposed in [40] which we summarize next.Let us consider a network system of which logical network topology is represented by an unweighted, undirected graph. Each nodev∈V in the system communicates its state value xv to its immediate neighbors N(v):=u:ev,u∈E(V), where E is an edge set. At each iteration τ, nodes exchange their current state values xv(τ) with their immediate neighbors. Given the state values xu(τ) received from their neighbors u∈N(v), each node u updates its state according to
(14)xu(t+1)=xu(t)+1ω∑v∈N(u)‍(xv(t)-xu(t)),
where ω is typically 0<1/ω<1/2dmax(G) and dmax(G) is the largest nodal degree. We set ω to 2×dmax(G)+1 in this paper. Consensus convergence can be controlled by ω value. However, finding an optimal ω value is out of scope for this paper.Following the method in [41], we use the average consensus protocol (14) to measure the information fusion performance of the network generated by the proposed topology control protocol. BCGs have already been shown to exhibit better consensus protocol performance than mesh, torus, and small world networks [33]. However, that research compared only topology level not considering nodes’ physical geometric information and radio range. In this paper, we compare a BCG with other network topologies when applied to wireless sensor network.


## 6.2. Simulation Setup

We evaluated our proposed topology control algorithms in terms of consensus speed and power consumption. The simulations were executed on100 host graphs, each with sensors uniformly and randomly distributed over a 100 m × 100 m area.Consensus protocol was initialized with nodes state value set to integers randomly chosen between-5 and 5 inclusive. We declared a network topology to have reached an agreement once all node values equal the average of all initial state values within a precision of 0.001. The performance of the consensus protocol was measured as the number of steps needed to reach a network-wide consensus.We also computed the energy needed for all the nodes in the network to reach a consensus using the average consensus protocol. To do this, we utilized the radio model described in [42]. For the sake of simplicity, we only considered the energy consumptions from data transmission (Etx) and reception (Erx) defined as follows:
(15)Etx=B(β1+β2ω(v,u)n),Erx=Bγ,
where n is the path loss exponent which, in typical, ranges from 2 to 6. The constants β1, β2, and γ are the energy dissipated by the transmitter module, transmit amplifier, and the receiver module, respectively. We denote the estimated distance between nodes v and u by ω(v,u) and the length of the message by B. We set n=2, equivalent to the free-space pass loss model, and assume that a sensor node v, regardless of the topology control protocols considered, can adjust its transmission power to reach its neighbors w. The parameters used in the simulation are summarized in  Table 3.Table 3
Radio model parameters.
Parameters
Values
n
2
β
1
45 nJ/bit
β
2
10 pJ/bit
γ
135 nJ/bit
B
320 bits (=40 bytes)Using the average consensus protocol, a node transmits and receives to and from each of its neighbors at every iteration. Thus, the node’s energy consumed by the network at theτth iteration is given by
(16)P0(v)=τB(∑∀(v,u)∈Ev≠u‍(β1+β2ω(v,u)n)+γdeg(v)),
where deg(v) is the number of logical neighbors, (v,u) is a logical connection, and E denotes the edge set. The average nodal energy consumption is given by P0¯=∑v∈V‍P0(v)/|V|. We call this power consumption model Power model0.In wireless sensor networks, a network can support multicasting routing to transmit at once to multiple nodes inside the radio range. Then power consumption is calculated not by each communication edge but by the maximum distance communication edge as follows:(17)P1(v)=τB(β1+β2Max{ω(v,u),u∈adj(v)}n+γdeg(v)).
We call this power consumption model Power model1.


## 6.3. Comparison between BCG-0 and BCG-1

Figure9 shows the histograms of the communication distance for N=1081 generated by the proposed node ID assignment algorithms. The histogram of the CR assignment (BCG-1) exhibits a right skewed distribution with a high frequency of short edges. The Dist-swap assignment (BCG-2) shows that all connection distance are under 80 m. We obtained similar histograms for the network sizes listed in Table 1. We compared power consumption between the random assignment and the CR assignment because they require a radio range that covers the whole node deployment area. Figure 10 summarizes the resulting consensus protocol energy consumption. We found that BCG-1 consumed 8% less energy than BCG-0 with power model 0 and 2% less with power model 1.Histograms of communication distance by the proposed algorithms withN=1081.
(a)
Random assignment (BCG-0)
(b)
CR assignment (BCG-1)
(c)
Dist-swap assignment (BCG-2)Figure 10
Power consumption comparison between BCG-0 and BCG-1.


## 6.4. Comparison between Our Proposed Topology Control and Existing Topology Controls

We compared our topology control algorithms with existing topology controls. The evaluation was done in terms of diameter, average path length, consensus steps, and nodal energy consumption.We used the following topologies for comparison against our approach.(i)
Max: network where all nodes within the maximum radio range are logical neighbors. Without any topology control, a network is called Max topology.(ii)
E-MST [43]: the Euclidean minimum spanning tree is a minimum spanning tree whose edge weight is the distance between nodes. This algorithm minimizes the summed weight of edges and generates a connected network.(iii)
K-Neigh [44]: network where the number of neighbors of a node equals to or is slightly below a given value k.(iv)
Gabriel Graph [45]: a planar graph (no edges cross one another) supports geographical routings and is defined such that an edge (v,u) exists if no other node is inside the circle with the diameter uv.Figure11 provides illustrations of the topologies constructed with (a) the random assignment (BCG-0), (b) the Dist-swapping assignment (BCG-2), (c) Max, (d) E-MST, (e) K-Neigh, and (f) Gabriel graph. For ease of description, we show sample graphs with N=272. However, we simulated with N=1081 in this section.BCG-0, BCG-3 with radio range 40 m, Max with 25 m, E-MST, K-Neigh withk=10 and 25 m, Gabriel graph. N=272.
(a)
BCG-0
(b)
BCG-3
(c)
Max
(d)
E-MST
(e)
K-Neigh
(f)
Gabriel graphFigures12 and 13 show the diameter and average path length function of the transmission range, respectively. We only compared the cases where the resultant graph is a connected graph. From these figures, we confirm again that the BCGs have the smallest diameter and the shortest average path length for a given radio range except Max topology. This is because as a radio range increases, BCGs have a constant number of logical neighbors, while Max topology has much more logical neighbors than others.Figure 12
Comparison of diameters.Figure 13
Comparison of average path lengths.From Figure14, at radio range 30 m, consensus protocol convergence for BCG-3 was 35.5, 2932, and 15.9 times faster than that of Gabriel, E-MST, and K-Neigh topologies. At radio range 50m, convergence of BCG-3 was 81.2, 6756.9, and 39.9 times faster than that of Gabriel, E-MST, and K-Neigh topologies. Even though Max topology has the best consensus steps, due to its large number of logical neighbors, it consumed 23 times more nodal power than BCG in Figure 15.Figure 14
Comparison of consensus steps.Figure 15
Comparison of power model0 for consensus protocol.When considering multicast routing (Power model1), the Max topology has an obvious advantage as only the maximum radio range is used in the power consumption computation. However, even with this advantage, our simulations showed that BCG continues to outperform the Max topology in Figure 16. This better performance can be explained by the fact that the Max topology has a larger number of logical neighbors and hence larger power is consumed at the receiver modules.Figure 16
Comparison of power model1 for consensus protocol.


## 7. Conclusions

Our goal was to use Borel Cayley graphs, a family of predefined graph topology, to overlay on dense wireless sensor networks for topology control. In this paper, we proposed node ID assignment methods to reduce the communication distance between nodes or to increase the number of logical connections following predefined graph connection rules in a distributed manner. In particular, we proposed the chordal ring-based node ID assignment method and the distributed node ID swapping assignment method.In the chordal ring-based method, we exploit that all BCGs have CR representations which imply the existence of a Hamiltonian cycle. With this observation, node IDs can simply be progressively assigned in numerical order based on their physical locations. Once the node IDs are assigned in the CR domain, we provide an explicit formulation to convert the CR domain ID to GCR domain ID which supports efficient routing. Our simulation results over a range of network sizes between 300 and 2000 nodes showed that this node ID assignment requires a smaller radio range (57%) than the random ID assignment.In the distributed node ID swapping assignment method, we consider that nodes have a limited transmission range. In WSNs, it is challenging to impose an entire logical graph to a physical network of finite radio range. An efficient node ID assignment will allow more connections to be imposed. For a range of network sizes from 200 to 1,000 nodes, the simulation showed that our proposed method achieved 43% more connections of all desired edges maximally than that of the random assignment. We also showed that our proposed topology control algorithms are efficient in consensus protocol comparing existing topology controls such as K-Neigh, Gabriel, and E-MST.In summary, in this paper, we showed that BCGs are good candidates as a family of predefined graphs for topology control for WSNs. However, there are many practical issues in the application of BCG as predefined graphs. For example, wireless packet transmission is interfered by simultaneous transmission of packets among nodes in the network. In future work, we will investigate the effects of interferences on BCG-based networks.



---

*Source: 805635-2013-09-14.xml*