## 5 Performance Evaluation  
### Performance Metrics  
We evaluate and compare the performance of BSMH with three existing protocols, namely GPSR [23] and LVGR [34] and EDGR [45]. GPSR is a typical perimeter routing protocol, which uses greedy forwarding as the default mode. When a packet encounters the local minimum phenomenon, it switches from greedy to perimeter mode whereby the packet is forwarded along the hole boundary. In LVGR, the packet is forwarded along a hole-bypassing Euclidean path from the source to the destination. This path is determined by using a visibility graph whose vertices are the vertices of the convex hulls of the holes. In EDGR, the source nodes randomly choose an anchor lists from two candidates. The packet then is forwarded towards the chosen anchor lists, gradually. Moreover, the next hop is heuristically chosen based on not only location information but also the residual energy. We focus on three design factors: routing path-length minimization, control overhead minimization and load balance maximization. In this section, we investigate how does our proposed protocol satisfy these design factors by using common evaluation metrics which have been used in many other related works [50; 51; 52; 53; 54]. 1. **Metrics regarding routing path-length minimization** * _Average routing path stretch:_ The routing path stretch of a routing path is defined by the ratio of its hop count to that of the theoretical shortest path. The average routing path stretch of a routing protocol is the average value of routing path stretches of all the routing paths determined by the protocol. Figure 6: When \(\epsilon\) is too large, the trajectory of the Euclidean routing paths may exceed the network boundary [38]. * _Average delay:_ We evaluate the average end-to-end delay of all data packets that successfully arrive at the destinations. 2. **Metrics regarding control overhead minimization** * _Total amount of control packets:_ Control packets are defined as packets that are not data packets. In BSMH and LVGR, control packets consist of packets for exchanging node information (known as HELLO packets), packets for determining hole boundaries (known as HBA packets), and packets for broadcasting hole information (known as HCI packets). In GPSR, the control packet is only HELLO packet. In EDGR, control packets include beacons that periodically broadcast node information (i.e., energy, location,...), and burst packets that determine the anchors. We measure the total amount (in bytes) of all the control packets which has been transmitted from when the simulation starts till the first node dies. 3. **Metrics regarding load balance maximization** * _Maximum packet forwarding ratio:_ This indicates the maximum ratio of the number of packets forwarded by a node to the total number of packets sent. Specifically, let \(p_{i}\) be the number of packets forwarded by the i-th node, and \(p\) be the total number of packet sent by all source nodes, then the maximum forwarding ratio is defined by \(Max\left\{\frac{p_{i}}{p}\right\}\). In general, the smaller maximum packet forwarding ratio reflects the better load balance. * _Network lifetime:_ As described in Section 1, in large-scale wireless sensor networks, the death of even only one node may affect the operation of the whole network. Accordingly, the network lifetime should be defined as the time period until the first node dies. In our experiments, all protocols spend the first 400s for the setup phase, and the first data packet is sent after that. Thus, we define the network lifetime as the time period from the first data packet was sent until the first node dies. Besides the above metrics, the following metrics are also used because they are the common metrics which have been used frequently in evaluating routing protocols in WSNs. 4. **Other metrics** * _Delivery ratio:_ This is defined by the ratio of the number of data packets successfully arriving at the destinations to the total number of data packets sent by the sources.