Wireless sensor networks have attracted more and more peoples attention
lately, because it has a wide range of potential applications including military
applications (Akyildiz et al., 2002; Wang
et al., 2011), environmental monitoring (Mainwaring
et al., 2002; Liu et al., 2010a),
target surveillance (Hai et al., 2005) and disaster
prevention (Goldsmith and Wicker, 2002).
Wireless sensor networks will consist of large numbers of distributed nodes that organize themselves into a multi-hop wireless network. In a multi-hop wireless network, a packet may need to be sent over several consecutive wireless links to reach its destination. Multi-hop networks have the advantage of saving power; as the distance increases, the transmission power required to maintain the same signal-to-noise level increases as a quadratic function of the distance. In addition, multi-hop networks can overcome obstacles and enhance spatial reuse. The question is how should the nodes be distributed to achieve good network performance? To evaluate performance of a wireless network, some of the suggested metrics are: energy efficiency, throughput, packet loss rate, throughput and transmission latency. In this study, each of these metrics is studied from a topology structure viewpoint.
In this study, the impact of topology (including topology complexity and topology
structure) on network performance is analyzed. In order to obtain more energy-efficient
performance, we adopt the adaptive sleeping MAC protocol-SMAC (Ye
et al., 2004). Firstly, we researched the impact of topology complexity
on network performance and the impact of three typical kinds of topology structure
on network performance theoretically. Then test the network performance of sensor
networks based on three kinds of topology structure (linear topology, hybrid
topology and star topology). The simulation results verify the rules we have
obtained in this study.
In networks where the nodes operate on limited battery power, it is important
to minimize power consumption to prolong the networks life time (Dai
et al., 2009; Guo et al., 2010). To
minimize power, we should exclude long edges and include short edges whenever
possible while optimizing the hop-diameter and maintaining network connectivity/biconnectivity.
This led to approaches using the Voronoi diagram and nearest neighbor graphs
with directional information (Hu, 1993; Wattenhofer
et al., 2001). It has also been shown that one can optimize the maximum
power used by performing power adjustments while guaranteeing network connectivity
and biconnectivity (Ramanathan and Rosales-Hain, 2000).
The first combined study on coverage and connectivity, due to Xing
et al. (2005), proved that if the radius of the transmission range
of the sensors is at least double the radius of their sensing range, a WSN is
connected provided that sensing coverage is guaranteed. Ammari
and Das (2006) proposed measures of connectivity for WSNs based on k-coverage.
Ai and Abouzeid (2006) proposed a directional sensors-based
approach for WSN coverage where the coverage region of a directional sensor
depends on their locations and their orientations. Adlakha
and Srivastava (2003) used an exposure-based model to determine the required
number of sensors to achieve full coverage of a desired region. Cortes
et al. (2004) proposed adaptive, distributed and asynchronous coverage
algorithms for mobile WSNs. Du and Lin (2005) proposed
a differentiated coverage algorithm for heterogeneous WSNs, where different
network areas may have different degrees of sensing coverage. Huang
and Tseng (2003) presented polynomial-time algorithms, in terms of the number
of sensors, for the k-coverage problem formulated as a decision problem. Lazos
and Poovendran (2006) also formulated the coverage problem in heterogeneous
planar WSNs as a set intersection problem and derived analytical expressions
which quantify the coverage achieved by stochastic coverage. Li
et al. (2003) proposed efficient distributed algorithms to optimally
solve the best coverage problem with the least energy consumption. Liu
et al. (2010b) proposed a new method called ATISA for constructing
Connected Dominating Set and ATISA constructs the Connected Dominating Set with
the smallest size.
In previous studies above, most do not consider different kinds of topology structure, especially the impact of topology structure on network performance of sensor networks. Sensor nodes in these approaches are assumed in changeless distribution and network performance is researched in the same topology. In this paper, based on the adaptive sleep MAC protocol-SMAC, we study the impact of topology on network performance of WSNs.
PERIODIC LISTEN AND SLEEP
In many sensor network applications, nodes are idle for long time if no sensing
event happens. Given the fact that the data rate is very low during this period,
it is not necessary to keep nodes listening all the time. SMAC (Ye
et al., 2004) reduces the listen time by putting nodes into periodic
sleep state. Each node sleeps for some time and then wakes up and listens to
see if any other node wants to talk to it. During sleeping, the node turns off
its radio and sets a timer to awake itself later. We call a complete cycle of
listen and sleep a frame. The listen interval is normally fixed according to
physical-layer and MAC-layer parameters, e.g., the radio bandwidth and the contention
window size. The duty cycle is defined as the ratio of the listen interval to
the frame length. The sleep interval can be changed according to different application
requirements which actually changes the duty cycle. For simplicity, these values
are the same for all nodes.
All nodes are free to choose their own listen/sleep schedules. However, to
reduce control overhead, we prefer neighboring nodes to synchronize together.
That is, they listen at the same time and go to sleep at the same time. It should
be noticed that not all neighboring nodes can synchronize together in a multi-hop
network. Two neighboring nodes A and B may have different schedules if they
must synchronize with different nodes C and D, respectively, as shown in Fig.
Nodes exchange their schedules by periodically broadcasting a SYNC packet to their immediate neighbors. A node talks to its neighbors at their scheduled listen time. In Fig. 1, for example, if node A wants to talk to node B, it waits until B is listening. The period for a node to send a SYNC packet is called the synchronization period.
One characteristic of SMAC is that it forms nodes into a flat, peer-to-peer topology. Unlike clustering protocols, SMAC does not require coordination through cluster heads. Instead, nodes form virtual clusters around common schedules but communicate directly with peers. One advantage of this loose coordination is that it can be more robust to topology change than cluster-based approaches.
The downside of the scheme is the increased latency due to the periodic sleeping. Furthermore, the delay can accumulate on each hop. The average latency of SMAC without adaptive listen over N hops is:
where, E[L(N)] means the average latency, Tf means the length of
a frame, ts,n means the sleep delay at the nth hop, tc,N
means the carrier sense delay at hop n, tc means the mean value of
the carrier sense delay, the transmission delay is denoted by tt.
||Neighboring nodes A and B synchronize with nodes C and D,
According to Eq. 1, the average latency of SMAC with adaptive listen over N hops is:
If we want to save more energy, we should reduce idle listening to a deeper extent, so, SMAC-like protocols adopts a bigger Tf to increase the proportion of sleep time. But Eq. 2 indicates E[L(N)]∝Tf, i.e., the transmission latency increases once Tf increases. That is the conflict between transmission latency and energy savings.
Since analyzing the impact of topology structure on network performance exclusively is not energy-efficient, we adopt the adaptive sleeping MAC protocol in sensor networks in this paper, we also changes the duty cycle for studying the impact of topology structure on network performance. Combing the topology control and adaptive sleeping MAC protocol, we find the general rules of obtaining better network performance for wireless sensor networks.
The relationship between network performance and number of sensor nodes: The number of sensor nodes in WSNs can denote the complexity of a wireless sensor networks topology in a simple case. In this subsection, we analyze the relationship between network performance and the number of nodes. We assume that only one-hop neighbors can hear each other, but two-hop neighbors cant hear each other and messages are transmitted one by one, as shown in Fig. 2.
||Energy consumption: If the distance between source
node and sink node is very long, a network needs relay nodes to transmit
packets, so the number of nodes increases and the energy consumption will
||Packet loss rate: If a node want to send a packet to another node
successfully, the two nodes should be awake at the same time, but in MAC
with adaptive sleeping, most of the time in a frame is sleeping time, so
the two nodes cant transmit packets successfully every time. Even
though there is synchronization mechanism, but the range of nodes synchronized
is limited, only the nodes in virtual cluster can be synchronized, so the
packet loss rate increases with the number of the relaying nodes
||Average throughput: Because in MAC with adaptive sleeping, nodes
are formed into a flat, peer-to-peer topology, so if the topology of a wireless
sensor network is a linear topology (Fig. 2), the throughput
is stable as the route selection is unnecessary
||Average transmission latency: In the process that packets transmitted
from source node to sink node, the transmission time increases with the
relay nodes because each relay node needs time to process a packet received
before sending the packet to the next node
||Different number of sensor nodes in linear topology
|| Linear topology
|| Hybrid topology
The relationship between network performance and topology structure: In this study, we analyze the network performance based on three kinds of topology structure: linear topology, hybrid topology and star topology, as shown in Fig. 3-5.
We make the following assumptions:
||Networks for the three kinds of topology structure have the
same number of nodes
||Networks for the three kinds of topology structure need to transmit the
same number of packets from source node to sink node
||All nodes have the same initial energy
|| Star topology
Now we analyze the network performance from the following aspects:
||Energy consumption: Because the energy consumption
increases with the number of relay nodes and the network with linear topology
has the most relay nodes on assumption a), so the rank of energy consumption
is linear topology>hybrid topology>star topology
||Packet loss rate: Because in MAC with adaptive sleeping, most of
the time is sleeping time in a frame and synchronization mechanism only
can synchronize limited nodes at the same time. In order to simply the analysis,
we assume that a node only can synchronize its nearest neighboring node
in the same virtual cluster, that means A only can synchronize node C and
B only can synchronize node D (Fig. 1) and we assume node
A, node B, node C and node D as relay nodes. The probability of the two
different virtual cluster can transmit a packet successfully is denoted
by p. Then the probability of transmitting a packet successfully by node
A, node B, node C and node D is:
where, pAC is the probability of transmitting a packet successfully between A and C, pBD is the probability of transmitting a packet successfully between B and D and pAB is the probability of transmitting a packet successfully between the two virtual cluster.
Then we have the overall probability of transmitting a packet successfully over n hops as:
where, pi means the probability of successful transmission from ith node to i+tth node (0<pi<1), K means the networks duty cycle and pi increases with K increasing. From Eq. 4, we can see that the probability of successful transmission decreases with relay nodes increasing.
On the other hand, to hybrid topology in Fig. 4, there are two branches road and one trunk road, if packets are sent from two branches to the trunk road at the same time, packet collision will happen and packets will be lost heavily. This is the main factor of high packet loss rate.
Based on the analysis above, the rank of the packet loss rate of the three kinds of topology structure is hybrid topology>linear topology>star topology;
||Average throughput: In this study, if the packet interval
is 5 sec, it means that a message is generated every 5 sec by each source
node. Throughput means the packets received per unit time in sink node,
it is obvious that the average throughput decreases with the packet interval
increasing. Because if the packet interval is big, that means the frequency
of the packets generated by the source node is slow. Comparing to linear
topology, there are two source nodes in hybrid topology (Fig.
4) and three source nodes in star topology (Fig. 5).
If the packet interval is the same, for example, the packet interval is
5 sec, then the packet interval in linear topology is 5 sec, in hybrid topology
is 2.5 sec and in star topology is 5/3 sec. So, the rank of average throughput
for the three topology is star topology>hybrid topology>linear topology
||Average transmission latency: For hybrid topology in Fig.
4, there are two branches road and one trunk road, if packets are sent
by two branches to the trunk road at the same time, packet collision will
happen, packets will be lost and the network needs to retransmit packets
and this process will increase the average transmission latency. This instance
impossibly occurs in linear topology and star topology as there isnt
the problem of route merger
Simulation experiments and related parameters: We implemented a simulator using ns-2 to evaluate the performance of networks for different kinds of topology structure. In our simulations, the communication distance is 100 m and the node topological space is 80 m. This means that only one-hop neighbors can hear each other, but two-hop neighbors cant hear each other and messages are transmitted one by one.
In present study, source nodes generate 60 packets all together, packet length
is 50 bytes. We set the number of sensor nodes as 10 (n = 9), we set k = 3,
m = 6 in Fig. 4, 5. For the network with
linear topology in Fig. 3, node 0 (source node) needs to generate
60 packets. In the network with hybrid topology (Fig. 4),
node 0 (source node) and node 3 (source node) needs to generate 30 packets respectively.
In the network with star topology (Fig. 5), node 0 (source
node), node 3 (source node) and node 6 (source node) each needs to generate
We change the traffic load by varying the packet interval and packet interval is set from 1-19 sec. For the highest rate with a 1 sec packet interval time, the wireless channel is nearly fully utilized due to its low bandwidth.
We employed the energy consumption model described by Lu
et al. (2007) where, the power consumption for transmit, receive,
idle and sleep modes was 0.386 J, 0.3682 J, 0.3442 J and 5.0e-5 J, respectively.
Each sensor node has an initial energy of 1000 J. Some important parameters
are listed in Table 1.
The relationship between network performance and the number of sensor nodes: In our simulation platform using ns-2, we test the network performance of WSNs with different number of sensor nodes and the topology complexity can be denoted by the number of sensor nodes in a simple case. As shown in Fig. 6, we set the number of sensor nodes from 2 to 10 and the hop count is from 1-9.
In this study, we set the packet interval as 5 sec and the duty cycle as 30%.
The simulation results are showed in Table 2, if the hop count
is smaller (<=5), the average throughput is about 10 byte/sec, the packet
loss rate is less than 10%.
|| Network simulation parameters
When the hop count is more than 7, the average throughput is 0, because sink
node cant receive any packets and the packet loss rate is 100%. The total
energy consumption and average transmission latency increases with the hop count
increasing. In Table 2, N means there is no packets
received by sink node and the transmission latency is meaningless.
The relationship between network performance and topology structure
energy consumption: Figure 7 shows the total energy consumption
of networks based on three kinds of different topologies. In multi-hop networks
with adaptive sleeping, if the duty cycle is not big enough, the packet loss
rate will be too high (as in Table 2, the packet loss rate
is 100% when the hop count is more than 7), so, we separately set the duty cycle
as 40 and 50% for comparing more conveniently. The simulation results show that
the network with higher duty cycle will consume more energy, because there is
more time for listening in higher duty cycle in a frame. If the duty cycle is
the same, the network with star topology consumes the least energy and the network
with linear topology consumes the most energy.
|| Network with multi-hop nodes
||Total energy consumption of networks based on three kinds
|| Network performance of networks with different number of
|N: No packets received by sink node
|| Packet loss rate comparing (30% duty cycle)
|| Packet loss rate comparing (40% duty cycle)
Packet loss rate: In wireless sensor networks adopting adaptive sleeping
MAC protocol, if the duty cycle is not big enough, the packet loss rate will
be very high, especially in multi-hop networks. For example, if the duty cycle
is 30%, we can see that the packet loss rate of networks with linear topology
or hybrid topology is 100%. From Fig. 8-10,
we can see that the packet loss rate decreases with the duty cycle increasing.
If traffic load is heavy, more packets are transmitted because data collision happens more frequently, so, packet loss rate is higher. In condition of the same traffic load, the network with star topology has the smallest packet loss rate.
Average throughput: From Fig. 11, we can see that
the average throughput decreased with the traffic load reducing.
|| Packet loss rate comparing (50% duty cycle)
|| Average throughput in sink node
Because if the traffic load is light, it means that the packet interval is
big, so, the data received in sink node per second is small.
The network with star topology has the highest throughput than others as fewer data collision happens. The average throughput decreases with duty cycle decreasing.
Average transmission latency: In Fig. 12, the average
transmission latency is all very high as collision happens frequently when network
is in heavy traffic load (packet interval<5 sec) and the network with hybrid
topology structure has the highest average transmission latency. In condition
of mid-level traffic load (5 sec = <packet interval<9 sec), the average
transmission latency of networks with the three kinds of topology structure
have nearly the same average transmission latency.
|| Average transmission latency
When the traffic load is light (packet interval> = 9 sec), the rank of
average transmission latency is hybrid topology >linear topology>star
In this study, we have studied the network performance of wireless sensor networks from a topology structure viewpoint. Especially we studied the network performance of networks based on three kinds of topology structure (linear topology, hybrid topology and star topology). The main contribution of this paper is that we obtain the relationship between network performance and topology structure based on adaptive sleeping MAC protocol. This is valuable when we distribute sensor nodes in practical applications.
This study is supported by three grants from the National Natural Science Foundation of China (No.60802002, No.60773190 and No.61100076), the Fundamental Research Funds for the Central Universities (No. 2011TS140) and Youth Foundation of Hubei Normal University (Grant No. 2010C41).