## 3 Node Clustering for WMSNs
### Cluster Formation and Cluster Membership  
Now, let us consider the set S = {S\({}_{1}\),S\({}_{2}\),...,S\({}_{\mathrm{N}}\)} of wireless multimedia nodes belonging to the same tier of a network randomly deployed. The cluster formation algorithm is executed in a centralized manner by the sink after deploying the network. The main reasons in choosing a central architecture are the following: (i) for a distributed architecture, each node should notify to the rest of the nodes about its location A\({}_{i}\) and its orientation \(\alpha_{i}\) (i = 1,...,N). In a centralized architecture the nodes should notify to the sink their location and orientation. Note that this notification can be done using any energy efficient sensor routing protocol and only is necessary at bootstrap phase. All phases of the clustering algorithm are executed only one time, right after node deployment. (ii) In many WSN applications, the sink has ample resources (storage, power supply, communication and computation) availability and capacity which make it suitable to play such a role. (iii) Collecting information by a sink node is more power efficient compared to spreading this information to each and every other node within the network. (iv) Having the global view of the network at the sink node facilitates provision algorithms for closer-to-optimal cluster determination; the global knowledge can be updated at the sink when new nodes are added or some nodes die. Such maintenance tasks can be regarded as a normal routine for the sink. (v) Finally, using a centralized scheme can relieve processing load from the sensors in the field and help in extending the overall network lifetime by reducing energy consumption at individual nodes. The following phases are performed to establish and form clusters:  
* _Bootstrap_: At node bootstrap, each sensor {S\({}_{i}\), i = 1,...,N} transmits its position (x\({}_{i}\),y\({}_{i}\)) and orientation \(\alpha_{i}\) to the sink. To accomplish this step any efficient sensor routing algorithm can be used. Thus, the clustering algorithm is not bound to how the sink receives this information. If there is an un-connected node in the network, it cannot announce itself and thus will not be considered in the algorithm. * _Cluster Formation_: (i) Initially, the sink creates an empty cluster associated with an un-clustered multimedia node of S. Thus, that node will be clustered as the first member (_i.e._, cluster-head) of the established cluster. (ii) Then, the sink finds the qualified un-clustered nodes for joining to that first member by computing the area of overlapped polygons of their FoV. From position and orientation of nodes, the sink computes the overlapped polygon area (Dij) between each un-clustered multimedia node and the first member of the established cluster as discussed in Section 3.1. If the computed overlapped area is equal or greater than the area determined by the overlapping scale (\(\gamma\)), the un-clustered node will be clustered as a member of the established cluster. (iii) When no more nodes can be added to the cluster, the sink takes a new un-clustered node, begins a new cluster and goes to step (ii). Table 1 indicates the formation procedure. * _Membership notification_: we assume that the sink uses any energy-efficient sensor routing algorithm to notify to each first-member of every cluster about its cluster-ID and what are the members of the cluster. Then, each first-member sends a packet to the members of his cluster notifying them about the cluster which they belong to.