# Nonlinear Gossip Algorithms for Wireless Sensor Networks

Authors: Chao Shi; Yuanshi Zheng; Hongbing Qiu; Junyi Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We study some nonlinear gossip algorithms for wireless sensor networks. Firstly, two types of nonlinear single gossip algorithms are proposed. By using Lyapunov theory, Lagrange mean value theorem, and stochastic Lasalle’s invariance principle, we prove that the nonlinear single gossip algorithms can converge to the average of initial states with probability one. Secondly, two types of nonlinear multigossip algorithms are also presented and the convergence is proved by the same methods. Finally, computer simulation is also given to show the validity of the theoretical results.


---

## Body

## 1. Introduction

Wireless sensor networks that are composed of a large number of unreliable cheap sensors have drawn much attention from academia to industry in the past decade [1]. The sensors are deployed for the purpose of monitoring and sensing their environment over time, communicating with each other over a wireless network, and processing information that they have exchanged with each other [2]. Clearly, the primary purpose of such networks is to collect and process the sensed information by sensors rather than provide efficient communication [3]. Robustness, scalability, power consumption, memory resources, and computation ability are the main constraints of such networks. These constraints naturally lead to gossip algorithms. Gossiping is a distributed computation, where a node exchanges and updates information at each time at most with one of its neighbors according to some rules [4]. Gossip algorithms are canonical algorithmic architectural solutions to wireless sensor networks [2], whose purposes are to make all the sensors achieve agreement [5–7] or synchronization [8–11].Recently, there emerge lots of studies on gossip algorithms in the field of wireless communication [10, 12–14] and of control systems [15–18]. In wireless sensor networks, gossip algorithms are used to solve many practical problems including distributed average, distributed estimation, source localization, and data compression [10]. These traditional gossip algorithms reach agreement by exchanging information with neighbor and averaging the exchanged information. Averaging the exchanged information can be seen as a case of liner process. However, under many practical conditions, the processing ability of sensor is nonlinear. Gossip algorithm can be viewed as a form of consensus protocol, but it differs from generic consensus protocol greatly [19–22]. The goal of consensus is to agree on the value of some quantity whereas the goal of gossiping is to compute the average of the initial values of net nodes [4]. Though nonlinear consensus algorithms have been widely investigated [23, 24], to the best of our knowledge, few studies focus on nonlinear gossip algorithm. The present study tries to address this question and proposes some novel nonlinear gossip algorithms to do the exchanged information. Two types of nonlinear single gossip algorithms and nonlinear multigossip algorithms are presented for wireless sensor networks. By using Lyapunov theory, Lagrange mean value theorem, and stochastic Lasalle’s invariance principle, we prove that the proposed algorithms converge to the average of the initial states with probability one.The remainder of this paper is organized as follows. In Section2, we review some concepts on graph theory and introduce the linear gossip algorithm. Nonlinear gossip algorithm is presented in Section 3. We propose two types of nonlinear single gossip algorithm and nonlinear multigossip algorithm and prove their convergence properties. Section 4 gives the computer simulation to show the validity of the theoretical results. Section 5 offers our concluding remarks and the possible research line in the future.Notation. Let 1
N be the N dimension column vector of all ones, I
N
=
{
1,2
,
…
,
N
}
T, x
(
n
)
=
{
x
1
(
n
)
,
x
2
(
n
)
,
…
,
x
N
(
n
)
}
T. The superscript “T” stands for matrix transposition. E
(
·
) denotes the expectation of stochastic variable. I
N
/
I
m
=
{
m
+
1
,
…
,
N
}. w.p.1 is the shortened form of with probability one.


## 2. Preliminaries

Suppose there is a connected wireless sensor network which consists ofN sensors distributed randomly in an area. We describe this wireless sensor network by a unidirectional graph G
=
(
V
,
E
,
A
), where V
=
{
1,2
,
…
,
N
} is the vertex set with each element denoting a sensor. Let E
⊂
V
×
V denote the set of links along which node pairs can communicate.  A
=
[
a
i
j
] is the adjacency matrix. If sensor i can communicate with sensor j, a
i
j
=
1; otherwise, a
i
j
=
0. For the purpose of simplicity, we assume that the network graph is connected and unchanged over time in terms of V and E.The gossip algorithm can be described as the following: without loss of generality, we assume in discrete time slot(
n
,
n
+
1
] that node i can gossip with one of its neighbors j. First, node i sends its current information x
i
(
n
), called gossip variable, to node j. After it received this information, node j sends its own current gossip variable x
j
(
n
) to node i. Then node i and node j set their gossip variables by some rules at discrete time n
+
1, respectively. The gossip variables of the rest nodes remain unchanged, as showed by
(1)
x
i
(
n
+
1
)
=
x
i
(
n
)
+
f
(
x
j
(
n
)
,
x
i
(
n
)
)
,
x
j
(
n
+
1
)
=
x
j
(
n
)
+
f
(
x
i
(
n
)
,
x
j
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
,
where f
(
x
j
(
n
)
,
x
i
(
n
)
) is a function on gossip variables x
i
(
n
) and (or) x
j
(
n
). We call f
(
x
j
(
n
)
,
x
i
(
n
)
) gossip function, which indicates the change introduced by the cooperation of node j to node i. When the gossip function is a linear function, for instance, f
(
x
j
(
n
)
,
x
i
(
n
)
)
=
β
x
j
(
n
)
-
α
x
i
(
n
), where α
,
β
∈
(
0,1
) are constant, (1) becomes
(2)
x
i
(
n
+
1
)
=
(
1
-
α
)
x
i
(
n
)
+
β
x
j
(
n
)
,
x
j
(
n
+
1
)
=
(
1
-
α
)
x
j
(
n
)
+
β
x
i
(
n
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
.This is the traditional gossip algorithm, which is called linear gossip algorithm. Specially, ifα
=
β
=
1
/
2, this linear gossip algorithm is average gossip algorithm [4]. The gossip process repeats between each pair of nodes; then finally all the sensors will have the same value as the average of their initial information, which is showed as
(3)
lim
⁡
n
→
∞
x
1
(
n
)
=
lim
⁡
n
→
∞
x
2
(
n
)
=
⋯
=
lim
⁡
n
→
∞
x
N
(
n
)
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
The proof of conclusion (3) can be found in [22].


## 3. Nonlinear Gossip Algorithms

In gossip algorithms, different gossip functions denote different gossip rules. Iff
(
·
) is a nonlinear function, then the gossip algorithm is nonlinear. We call this algorithm nonlinear gossip algorithm. Two types of nonlinear gossip algorithms are presented for single gossip algorithm and multigossip algorithm, respectively. We will give a brief statement on these two types of nonlinear gossip algorithms and deliberate their convergence properties.


### 3.1. Nonlinear Gossip Algorithms Type-1

In this subsection, we consider the following nonlinear gossip algorithm:(4)
x
i
(
n
+
1
)
=
x
i
(
n
)
+
f
(
x
j
(
n
)
-
x
i
(
n
)
)
,
x
j
(
n
+
1
)
=
x
j
(
n
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
.In (4), we think of the nonlinear function on the increment of gossip variables x
j
(
n
) and x
i
(
n
) as the change introduced by the cooperation of node j to node i.Theorem 1.
Suppose the gossip functionf
(
·
) in gossip rule (4) can be any C
1 continuous function which satisfies (i) f
(
·
) is odd; (ii)   0
<
f
′
(
·
)
<
1; then all the gossip variables converge to the average of their initial values w.p.1.Proof.
First we will prove nonlinear gossip algorithm (4) can converge w.p.1.
Without loss of generality, in(
n
,
n
+
1
], we randomly choose node i and node j for gossiping. Define a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
), and we have
(5)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
j
2
(
n
+
1
)
+
x
i
2
(
n
+
1
)
-
x
j
2
(
n
)
-
x
i
2
(
n
)
+
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
+
1
)
-
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
)
∣
x
(
n
)
]
=
E
[
2
x
i
(
n
)
f
(
x
j
(
n
)
-
x
i
(
n
)
)
+
f
2
(
x
j
(
n
)
-
x
i
(
n
)
)
+
2
x
j
(
n
)
f
(
x
i
(
n
)
-
x
j
(
n
)
)
+
f
2
(
x
i
(
n
)
-
x
j
(
n
)
)
]
.
Since f
(
·
) is odd, that is, f
(
-
x
)
=
-
f
(
x
), hence f
(
0
)
=
0 and (5) can be simplified as
(6)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
2
f
(
x
j
(
n
)
-
x
i
(
n
)
)
×
[
f
(
x
j
(
n
)
-
x
i
(
n
)
)
-
(
x
j
(
n
)
-
x
i
(
n
)
)
]
]
.
According to Lagrange mean value theorem(7)
f
(
x
i
(
n
)
-
x
j
(
n
)
)
-
f
(
0
)
=
f
′
(
ξ
)
[
x
i
(
n
)
-
x
j
(
n
)
]
,
and due to 0
<
f
′
(
·
)
<
1, we can forward our proof by considering all three possible cases in terms of the difference between x
j
(
n
) and x
i
(
n
):(i)
ifx
j
(
n
)
-
x
i
(
n
)
<
0, we have f
(
x
j
(
n
)
-
x
i
(
n
)
)
<
0 and f
(
x
j
(
n
)
-
x
i
(
n
)
)
>
x
j
(
n
)
-
x
i
(
n
); thus,
(8)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
<
0
;
(ii)
ifx
j
(
n
)
-
x
i
(
n
)
>
0, then f
(
x
j
(
n
)
-
x
i
(
n
)
)
>
0 and f
(
x
j
(
n
)
-
x
i
(
n
)
)
<
(
x
j
(
n
)
-
x
i
(
n
)
); therefore, we can also obtain E
[
Δ
V
∣
x
(
n
)
]
<
0;
(iii)
ifx
j
(
n
)
-
x
i
(
n
)
=
0, then E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
0.
Hence, from (i), (ii), and (iii), we have(9)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
Invoking the stochastic version of LaSalle’s Theorem [25, 26], we conclude that
(10)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (10) indicates that the nonlinear gossip algorithms (4) can converge w.p.1.
Now we will prove that all the gossip variables converge to the average of their initial values. Consider(11)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
+
1
)
+
x
i
(
n
+
1
)
+
x
j
(
n
+
1
)
]
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
)
+
f
(
x
j
(
n
)
-
x
i
(
n
)
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
+
x
j
(
n
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
]
.
The gossip function f
(
·
) is an odd function; thus f
(
x
j
(
n
)
-
x
i
(
n
)
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
=
0. Then, (11) can be simplified as
(12)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Therefore, we have
(13)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (13) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear gossip rule (4).


### 3.2. Nonlinear Gossip Algorithms Type-2

We consider the following nonlinear gossip algorithm:(14)
x
i
(
n
+
1
)
=
x
i
(
n
)
+
f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
,
x
j
(
n
+
1
)
=
x
j
(
n
)
+
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
.In (14), we think of the increment of the nonlinear function on gossip variables x
j
(
n
) and on gossip variables x
i
(
n
) as the change introduced by the cooperation of node j to node i.Theorem 2.
Suppose the gossip functionf
(
·
) in gossip rule (14) can be any C
1 continuous function and satisfies 0
<
f
′
(
·
)
<
1; then all the gossip variables converge to the average of their initial values w.p.1.Proof.
Similar to the proof of Theorem1, in (
n
,
n
+
1
], we randomly choose node i and node j for gossiping. We define a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
). From (14),
(15)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
j
2
(
n
+
1
)
+
x
i
2
(
n
+
1
)
-
x
j
2
(
n
)
-
x
i
2
(
n
)
+
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
+
1
)
-
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
)
∣
x
(
n
)
]
=
E
[
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
2
2
x
i
(
n
)
[
f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
]
+
2
x
j
(
n
)
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
+
2
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
2
]
=
E
[
2
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
×
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
-
(
x
i
(
n
)
-
x
j
(
n
)
)
]
]
.
According to Lagrange mean value theorem(16)
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
-
f
(
0
)
=
f
′
(
ξ
)
[
x
i
(
n
)
-
x
j
(
n
)
]
,
and due to 0
<
f
′
(
·
)
<
1, we have that (i)
ifx
j
(
n
)
-
x
i
(
n
)
<
0, we have f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
<
0 and f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
>
x
j
(
n
)
-
x
i
(
n
); thus,
(17)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
(
V
(
n
+
1
)
-
V
(
n
)
)
∣
x
(
n
)
]
<
0
;
(ii)
ifx
j
(
n
)
-
x
i
(
n
)
>
0, then f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
>
0 and f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
<
x
j
(
n
)
-
x
i
(
n
); therefore, we can also obtain E
[
Δ
V
∣
x
(
n
)
]
<
0;
(iii)
ifx
j
(
n
)
-
x
i
(
n
)
=
0 then E
[
Δ
V
∣
x
(
n
)
]
=
0.
Hence from (i), (ii), and (iii), we have(18)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
By using the stochastic version of LaSalle’s Theorem, we have(19)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (19) indicates that the nonlinear gossip algorithms (14) can converge w.p.1.
Consider(20)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
+
1
)
+
x
j
(
n
+
1
)
]
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
)
+
f
(
x
j
(
n
)
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
-
f
(
x
i
(
n
)
)
+
x
j
(
n
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
+
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Hence we have
(21)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (21) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear gossip rule (14).


### 3.3. Nonlinear Multigossip Algorithms

In aforementioned gossip algorithms, each sensor is allowed to gossip with at most one of its neighbors in a fixed time slot, which leads to a low average convergence rate. For example when sensori and sensor j are gossiping, another sensor k
≠
i
,
j cannot gossip with others. This gossip algorithm is single gossip algorithm. In fact, multiple pairs of sensors can gossip at the same time slot, provided each of two pairs has no common sensor, which are multigossip algorithms [4]. For example, when sensor p and sensor q are gossiping, sensor i and sensor j are also gossiping; then (
i
,
j
) and (
p
,
q
) should satisfy i
≠
p
,
q and j
≠
p
,
q. Obviously, the convergence rate of multigossip algorithms is faster than one of single gossip algorithms.It is similar to nonlinear single gossip algorithm that we present two types of nonlinear multigossip algorithms.Assume in discrete time slot(
n
,
n
+
1
] that there are r pairs of sensors, 1
<
r
<
N, (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) that can gossip, and if the gossip rules conform to type-1, then we have
(22)
x
p
i
(
n
+
1
)
=
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
,
x
q
i
(
n
+
1
)
=
x
q
i
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
p
1
,
…
,
p
r
,
q
1
,
…
,
q
r
}
.Theorem 3.
In multigossip algorithm, if nonlinear functionf
(
·
) in gossip rule (22) can be any C
1 continuous function which satisfies that (i)   f
(
·
) is odd; (ii)   0
<
f
′
(
·
)
<
1, then all gossip variables converge to the average of their initial values w.p.1.Proof.
In(
n
,
n
+
1
], we randomly choose r pairwise nodes (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) for gossiping. By defining a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
), we have
(23)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
i
=
1
r
‍
[
x
p
i
2
(
n
+
1
)
+
x
q
i
2
(
n
+
1
)
-
x
p
i
2
(
n
)
-
x
q
i
2
(
n
)
]
∣
x
(
n
)
∑
i
=
1
r
‍
]
=
E
[
∑
i
=
1
r
‍
[
2
x
p
i
(
n
)
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
f
2
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
2
x
q
i
(
n
)
f
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
+
f
2
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
]
∑
i
=
1
r
‍
]
.
Similar to the proof of Theorem1, if x
q
i
(
n
)
-
x
p
i
(
n
)
≠
0, then E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
<
0; if x
q
i
(
n
)
-
x
p
i
(
n
)
=
0, then E
[
Δ
V
∣
x
(
n
)
]
=
0.
Therefore we have(24)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
Hence, we get(25)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (25) indicates that the nonlinear gossip algorithms (14) can converge w.p.1.
Consider(26)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
r
∑
i
=
1
r
‍
[
x
p
i
(
n
+
1
)
+
x
q
j
(
n
+
1
)
]
+
1
N
∑
m
=
r
+
1
N
‍
x
m
(
n
)
=
1
r
∑
i
=
1
r
‍
[
x
q
j
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
j
(
n
)
)
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
x
q
j
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
j
(
n
)
)
]
+
1
N
-
r
∑
m
=
r
+
1
N
‍
x
m
(
n
)
.
Because the gossip function f
(
·
) is an odd function, (26) is simplified as
(27)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
-
r
∑
m
=
r
+
1
N
‍
x
m
(
n
)
+
1
r
∑
i
=
1
r
‍
[
x
p
i
(
n
)
+
x
q
j
(
n
)
]
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Therefore we have
(28)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (28) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear multigossip rule (22).Assume in discrete time slot(
n
,
n
+
1
],  r pairs of sensors, 1
<
r
<
N, (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) that are gossiping, and if the gossip rules conform to type-2, then we have
(29)
x
p
i
(
n
+
1
)
=
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
)
-
f
(
x
p
i
(
n
)
)
,
x
q
i
(
n
+
1
)
=
x
q
i
(
n
)
+
f
(
x
p
i
(
n
)
)
-
f
(
x
q
i
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
p
1
,
…
,
p
r
,
q
1
,
…
,
q
r
}
.Theorem 4.
In multigossip algorithm, if nonlinear functionf
(
·
) in gossip rule (29) can be any C
1 continuous function and satisfies 0
<
f
′
(
·
)
<
1, then all gossip variables converge to the average of their initial values w.p.1.Proof.
The analysis is similar to the proofs of Theorems2 and 3, and it is thus omitted here.


## 3.1. Nonlinear Gossip Algorithms Type-1

In this subsection, we consider the following nonlinear gossip algorithm:(4)
x
i
(
n
+
1
)
=
x
i
(
n
)
+
f
(
x
j
(
n
)
-
x
i
(
n
)
)
,
x
j
(
n
+
1
)
=
x
j
(
n
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
.In (4), we think of the nonlinear function on the increment of gossip variables x
j
(
n
) and x
i
(
n
) as the change introduced by the cooperation of node j to node i.Theorem 1.
Suppose the gossip functionf
(
·
) in gossip rule (4) can be any C
1 continuous function which satisfies (i) f
(
·
) is odd; (ii)   0
<
f
′
(
·
)
<
1; then all the gossip variables converge to the average of their initial values w.p.1.Proof.
First we will prove nonlinear gossip algorithm (4) can converge w.p.1.
Without loss of generality, in(
n
,
n
+
1
], we randomly choose node i and node j for gossiping. Define a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
), and we have
(5)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
j
2
(
n
+
1
)
+
x
i
2
(
n
+
1
)
-
x
j
2
(
n
)
-
x
i
2
(
n
)
+
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
+
1
)
-
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
)
∣
x
(
n
)
]
=
E
[
2
x
i
(
n
)
f
(
x
j
(
n
)
-
x
i
(
n
)
)
+
f
2
(
x
j
(
n
)
-
x
i
(
n
)
)
+
2
x
j
(
n
)
f
(
x
i
(
n
)
-
x
j
(
n
)
)
+
f
2
(
x
i
(
n
)
-
x
j
(
n
)
)
]
.
Since f
(
·
) is odd, that is, f
(
-
x
)
=
-
f
(
x
), hence f
(
0
)
=
0 and (5) can be simplified as
(6)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
2
f
(
x
j
(
n
)
-
x
i
(
n
)
)
×
[
f
(
x
j
(
n
)
-
x
i
(
n
)
)
-
(
x
j
(
n
)
-
x
i
(
n
)
)
]
]
.
According to Lagrange mean value theorem(7)
f
(
x
i
(
n
)
-
x
j
(
n
)
)
-
f
(
0
)
=
f
′
(
ξ
)
[
x
i
(
n
)
-
x
j
(
n
)
]
,
and due to 0
<
f
′
(
·
)
<
1, we can forward our proof by considering all three possible cases in terms of the difference between x
j
(
n
) and x
i
(
n
):(i)
ifx
j
(
n
)
-
x
i
(
n
)
<
0, we have f
(
x
j
(
n
)
-
x
i
(
n
)
)
<
0 and f
(
x
j
(
n
)
-
x
i
(
n
)
)
>
x
j
(
n
)
-
x
i
(
n
); thus,
(8)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
<
0
;
(ii)
ifx
j
(
n
)
-
x
i
(
n
)
>
0, then f
(
x
j
(
n
)
-
x
i
(
n
)
)
>
0 and f
(
x
j
(
n
)
-
x
i
(
n
)
)
<
(
x
j
(
n
)
-
x
i
(
n
)
); therefore, we can also obtain E
[
Δ
V
∣
x
(
n
)
]
<
0;
(iii)
ifx
j
(
n
)
-
x
i
(
n
)
=
0, then E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
0.
Hence, from (i), (ii), and (iii), we have(9)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
Invoking the stochastic version of LaSalle’s Theorem [25, 26], we conclude that
(10)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (10) indicates that the nonlinear gossip algorithms (4) can converge w.p.1.
Now we will prove that all the gossip variables converge to the average of their initial values. Consider(11)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
+
1
)
+
x
i
(
n
+
1
)
+
x
j
(
n
+
1
)
]
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
)
+
f
(
x
j
(
n
)
-
x
i
(
n
)
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
+
x
j
(
n
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
]
.
The gossip function f
(
·
) is an odd function; thus f
(
x
j
(
n
)
-
x
i
(
n
)
)
+
f
(
x
i
(
n
)
-
x
j
(
n
)
)
=
0. Then, (11) can be simplified as
(12)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Therefore, we have
(13)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (13) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear gossip rule (4).


## 3.2. Nonlinear Gossip Algorithms Type-2

We consider the following nonlinear gossip algorithm:(14)
x
i
(
n
+
1
)
=
x
i
(
n
)
+
f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
,
x
j
(
n
+
1
)
=
x
j
(
n
)
+
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
i
,
j
}
.In (14), we think of the increment of the nonlinear function on gossip variables x
j
(
n
) and on gossip variables x
i
(
n
) as the change introduced by the cooperation of node j to node i.Theorem 2.
Suppose the gossip functionf
(
·
) in gossip rule (14) can be any C
1 continuous function and satisfies 0
<
f
′
(
·
)
<
1; then all the gossip variables converge to the average of their initial values w.p.1.Proof.
Similar to the proof of Theorem1, in (
n
,
n
+
1
], we randomly choose node i and node j for gossiping. We define a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
). From (14),
(15)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
j
2
(
n
+
1
)
+
x
i
2
(
n
+
1
)
-
x
j
2
(
n
)
-
x
i
2
(
n
)
+
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
+
1
)
-
∑
m
=
1
,
m
≠
i
,
j
N
‍
x
m
2
(
n
)
∣
x
(
n
)
]
=
E
[
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
2
2
x
i
(
n
)
[
f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
]
+
2
x
j
(
n
)
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
+
2
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
2
]
=
E
[
2
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
×
[
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
-
(
x
i
(
n
)
-
x
j
(
n
)
)
]
]
.
According to Lagrange mean value theorem(16)
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
-
f
(
0
)
=
f
′
(
ξ
)
[
x
i
(
n
)
-
x
j
(
n
)
]
,
and due to 0
<
f
′
(
·
)
<
1, we have that (i)
ifx
j
(
n
)
-
x
i
(
n
)
<
0, we have f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
<
0 and f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
>
x
j
(
n
)
-
x
i
(
n
); thus,
(17)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
(
V
(
n
+
1
)
-
V
(
n
)
)
∣
x
(
n
)
]
<
0
;
(ii)
ifx
j
(
n
)
-
x
i
(
n
)
>
0, then f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
>
0 and f
(
x
j
(
n
)
)
-
f
(
x
i
(
n
)
)
<
x
j
(
n
)
-
x
i
(
n
); therefore, we can also obtain E
[
Δ
V
∣
x
(
n
)
]
<
0;
(iii)
ifx
j
(
n
)
-
x
i
(
n
)
=
0 then E
[
Δ
V
∣
x
(
n
)
]
=
0.
Hence from (i), (ii), and (iii), we have(18)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
By using the stochastic version of LaSalle’s Theorem, we have(19)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (19) indicates that the nonlinear gossip algorithms (14) can converge w.p.1.
Consider(20)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
+
1
)
+
x
j
(
n
+
1
)
]
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
[
x
m
(
n
)
+
x
i
(
n
)
+
f
(
x
j
(
n
)
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
-
f
(
x
i
(
n
)
)
+
x
j
(
n
)
=
1
N
∑
m
=
1
,
m
≠
i
,
j
N
‍
+
f
(
x
i
(
n
)
)
-
f
(
x
j
(
n
)
)
]
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Hence we have
(21)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (21) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear gossip rule (14).


## 3.3. Nonlinear Multigossip Algorithms

In aforementioned gossip algorithms, each sensor is allowed to gossip with at most one of its neighbors in a fixed time slot, which leads to a low average convergence rate. For example when sensori and sensor j are gossiping, another sensor k
≠
i
,
j cannot gossip with others. This gossip algorithm is single gossip algorithm. In fact, multiple pairs of sensors can gossip at the same time slot, provided each of two pairs has no common sensor, which are multigossip algorithms [4]. For example, when sensor p and sensor q are gossiping, sensor i and sensor j are also gossiping; then (
i
,
j
) and (
p
,
q
) should satisfy i
≠
p
,
q and j
≠
p
,
q. Obviously, the convergence rate of multigossip algorithms is faster than one of single gossip algorithms.It is similar to nonlinear single gossip algorithm that we present two types of nonlinear multigossip algorithms.Assume in discrete time slot(
n
,
n
+
1
] that there are r pairs of sensors, 1
<
r
<
N, (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) that can gossip, and if the gossip rules conform to type-1, then we have
(22)
x
p
i
(
n
+
1
)
=
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
,
x
q
i
(
n
+
1
)
=
x
q
i
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
p
1
,
…
,
p
r
,
q
1
,
…
,
q
r
}
.Theorem 3.
In multigossip algorithm, if nonlinear functionf
(
·
) in gossip rule (22) can be any C
1 continuous function which satisfies that (i)   f
(
·
) is odd; (ii)   0
<
f
′
(
·
)
<
1, then all gossip variables converge to the average of their initial values w.p.1.Proof.
In(
n
,
n
+
1
], we randomly choose r pairwise nodes (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) for gossiping. By defining a Lyapunov function V
(
n
)
=
∑
m
=
1
N
x
m
2
(
n
), we have
(23)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
=
E
[
∑
i
=
1
r
‍
[
x
p
i
2
(
n
+
1
)
+
x
q
i
2
(
n
+
1
)
-
x
p
i
2
(
n
)
-
x
q
i
2
(
n
)
]
∣
x
(
n
)
∑
i
=
1
r
‍
]
=
E
[
∑
i
=
1
r
‍
[
2
x
p
i
(
n
)
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
f
2
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
2
x
q
i
(
n
)
f
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
+
f
2
(
x
p
i
(
n
)
-
x
q
i
(
n
)
)
]
∑
i
=
1
r
‍
]
.
Similar to the proof of Theorem1, if x
q
i
(
n
)
-
x
p
i
(
n
)
≠
0, then E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
<
0; if x
q
i
(
n
)
-
x
p
i
(
n
)
=
0, then E
[
Δ
V
∣
x
(
n
)
]
=
0.
Therefore we have(24)
E
[
Δ
V
∣
x
(
n
)
]
=
E
[
V
(
n
+
1
)
-
V
(
n
)
∣
x
(
n
)
]
≤
0
.
Hence, we get(25)
lim
⁡
n
→
∞
x
(
n
)
=
c
1
N
,
w
.
p
.
1
,
where c is a constant. Equation (25) indicates that the nonlinear gossip algorithms (14) can converge w.p.1.
Consider(26)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
r
∑
i
=
1
r
‍
[
x
p
i
(
n
+
1
)
+
x
q
j
(
n
+
1
)
]
+
1
N
∑
m
=
r
+
1
N
‍
x
m
(
n
)
=
1
r
∑
i
=
1
r
‍
[
x
q
j
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
j
(
n
)
)
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
-
x
p
i
(
n
)
)
+
x
q
j
(
n
)
+
f
(
x
p
i
(
n
)
-
x
q
j
(
n
)
)
]
+
1
N
-
r
∑
m
=
r
+
1
N
‍
x
m
(
n
)
.
Because the gossip function f
(
·
) is an odd function, (26) is simplified as
(27)
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
1
N
-
r
∑
m
=
r
+
1
N
‍
x
m
(
n
)
+
1
r
∑
i
=
1
r
‍
[
x
p
i
(
n
)
+
x
q
j
(
n
)
]
=
1
N
∑
m
=
1
N
‍
x
m
(
n
)
.
Therefore we have
(28)
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
+
1
)
=
lim
⁡
n
→
∞
1
N
∑
m
=
1
N
‍
x
m
(
n
)
=
⋯
=
1
N
∑
m
=
1
N
‍
x
m
(
0
)
.
Equation (28) implies that c
=
(
1
/
N
)
∑
m
=
1
N
x
m
(
0
), which in turn implies that all gossip variables converge to the average of their initial values w.p.1 under nonlinear multigossip rule (22).Assume in discrete time slot(
n
,
n
+
1
],  r pairs of sensors, 1
<
r
<
N, (
p
1
,
q
1
)
,
(
p
2
,
q
2
)
,
…
,
(
p
r
,
q
r
) that are gossiping, and if the gossip rules conform to type-2, then we have
(29)
x
p
i
(
n
+
1
)
=
x
p
i
(
n
)
+
f
(
x
q
i
(
n
)
)
-
f
(
x
p
i
(
n
)
)
,
x
q
i
(
n
+
1
)
=
x
q
i
(
n
)
+
f
(
x
p
i
(
n
)
)
-
f
(
x
q
i
(
n
)
)
,
x
k
(
n
+
1
)
=
x
k
(
n
)
,
k
∈
I
N
{
p
1
,
…
,
p
r
,
q
1
,
…
,
q
r
}
.Theorem 4.
In multigossip algorithm, if nonlinear functionf
(
·
) in gossip rule (29) can be any C
1 continuous function and satisfies 0
<
f
′
(
·
)
<
1, then all gossip variables converge to the average of their initial values w.p.1.Proof.
The analysis is similar to the proofs of Theorems2 and 3, and it is thus omitted here.


## 4. Numerical Simulation

In this section, we give several computer simulation examples for the presented nonlinear gossip algorithms. A connected wireless sensor network is considered which is composed ofN
=
5 sensors and whose network is showed as in Figure 1. No matter what the distribution of the sensors’ gossip variables is, the proposed nonlinear algorithms can converge w.p.1. We assume the initial gossip variables of these five sensors are 0.9, 0.1, 0.5, 0.3, and 0.7, respectively. In the proposed nonlinear gossip algorithms, we require that the gossip function in type-1 satisfy two conditions: (i)  f
(
·
) is odd and (ii)  0
<
f
′
(
·
)
<
1; the gossip function in type-2 should only satisfy 0
<
f
′
(
·
)
<
1. We give a function f
(
x
)
=
(
1
/
2
)
arctan
(
x
) which satisfies the above conditions. We simulate two different gossip types of nonlinear single gossip algorithms and nonlinear multigossip algorithms. The simulation results are showed in Figures 2 and 3.Figure 1
The topology of wireless sensor networks.Figure 2
Simulations of the single gossip algorithm for type-1 and type-2.Figure 3
Simulations of the multigossip algorithm for type-1 and type-2.Figure2 is the simulations of nonlinear single gossip algorithms for type-1 and type-2. Figure 3 is the simulations of nonlinear multigossip algorithms for type-1 and type-2. It can be seen from Figures 2 and 3 that the proposed nonlinear gossip algorithms can converge and the convergent value is the sensors’ average of their initial values. Figures 2 and 3 also illustrate that different gossip rules have different convergence rates of nonlinear gossip algorithms.


## 5. Conclusion

Nonlinear gossip algorithms for wireless sensor networks are considered. It is proved that the proposed algorithms can converge to the average of the initial values with probability one. The proposed algorithm is a general approach to the gossip algorithm, while the traditional linear gossip algorithm can be viewed as a special case of the nonlinear gossip algorithm. In the simulation, we find that different gossip functions bring about different convergence rates. How to determine and accelerate the convergence rate of nonlinear gossip algorithms may worth further study.



---

*Source: 170748-2014-09-01.xml*