# A Cross-Layer Optimization QoS Scheme in Wireless Multimedia Sensor Networks
## 3 Problem Formation and Dynamic Algorithm
### Design Dynamic Algorithm via Lyapunov Optimization  
The Lyapunov optimization technique is applied to solve optimization problem \(P1\). \(Q_{n}(\forall n\
eq d_{n})\), \(E_{n}(\forall n\
eq d_{n})\), and \(Y_{n}(\forall m\in M)\) are used in the dynamic algorithm. Let \(\Theta(t)=[Q(t),E(t),Y(t)]\) be the network state vector in time slot \(t\), and the Lyapunov function is defined as:  
\[L(\Theta(t))=\dfrac{1}{2}[\sum\limits_{n=M}\left(Y_{n}(t)/B_{F}\right)^{2}+ \sum\limits_{n=d_{n}}q_{n}\tau_{n}(t)(Q_{n}(t)/B_{F})^{2}+\sum\limits_{n=d_{n }}e_{n}[(\theta_{n}^{E}-E_{n}(t))/\theta_{n}^{E}]^{2}]\,. \tag{21}\]  
Normalization of different types of queues is utilized for a unified dimension in the Lyapunov optimization framework. In addition, in Equation (21), there are three coefficients, \(q_{n}\), \(e_{n}\), and \(\tau_{n}(t)\), that are designed as follows. In order to relay data to the sink node, the energy of the nodes around the sink node will be easily exhausted. When the nodes around the sink node die out, there is no packet that can be received by the sink node, which means the wireless sensor network is out of action. Therefore, the maximal lifetime of the nodes around the sink node decide the network lifetime. To prolong the network lifetime, nodes around the sink node should reduce transmission power, which may result in the increase of relay hops to the sink node and the end-to-end delay. In this paper, \(e_{n}\), which is the distance coefficient of the energy queue in node \(n\), is used as the weight of queue \(E_{n}\) in the Lyapunov function. The design principle of \(e_{n}\) is that the nearer node \(n\) is to the sink node, the higher the weight of \(E_{n}\) will be. \(e_{n}\) is defined as:\[e_{n}=e^{mn(0,R-D_{n})/R}\,, \tag{22}\]  
where \(Dis_{n}\) denotes the distance between node \(n\) and the sink node, \(R\) represents the threshold distance, and \(e\) is the Euler number. Obviously, (22) fits the design principle of \(e_{n}\). In the wireless sensor networks, the nodes far from the sink node should be dedicated to increasing the average transmission rates to reduce the end-to-end delay of the packets buffered in them, with little consideration of energy consumption in data transmission. \(q_{n}\) is used to indicate the weight of queue \(Q_{n}\) of node \(n\) in the Lyapunov function. \(q_{n}\) is defined as:  
\[q_{n}=e^{mn(0,D_{n}-R)/(D_{n}-R)}\,, \tag{23}\]  
where \(Dis_{mn}\) denotes the maximal distance between the sink node and any other node in the network. The design principle of \(q_{n}\) is that, when the distance between node \(n\) and the sink node is longer than the threshold distance, then the farther node \(n\) is to the sink node, the higher the weight of \(Q_{n}\). \(\tau_{n}(t)\) is the delay coefficient of \(Q_{n}\) in time slot \(t\). The design principle of \(\tau_{n}(t)\) is that, the lower the total remaining lifetime of packets in \(Q_{n}(t)\) is, the higher the scheduling priority of \(Q_{n}\). \(\tau_{n}(t)\) is calculated as:  
\[\tau_{n}(t)=e^{-\frac{\tau_{n}(t)-\tau_{n}(t)}{\tau_{n}(t)}}\cdot 1/e\,, \tag{24}\]  
where \(K_{n}\) is the set of data packets in node \(n\). \(D_{k}\) is defined as the maximum allowable end-to-end delay of packet \(k\). \(T_{k}(t)\) denotes the remaining lifetime of packet \(k\) in time slot \(t\). The conditional Lyapunov drift in time slot \(t\) is:  
\[\Delta(\Theta(t))=E\left\{L(\Theta(t+1))-L(\Theta(t))\,|\,\Theta(t)\right\}\,. \tag{25}\]  
To maximize a lower bound of \(1/B_{F}^{2}\cdot\sum_{m=M}\mathrm{U}_{m}(\overline{q_{m}})\), the drift-plus-penalty function can be defined as:  
\[\Delta_{F}\left(\Theta(t)\right)=\Delta\Theta(t)-V\cdot E\left\{1/B_{F}^{2} \cdot\sum_{m=M}\mathrm{U}_{m}(\eta_{m}(t))\,|\,\Theta(t)\right\}\,, \tag{26}\]  
where \(V\) is the weight of the utility defined by the user. The following inequality can be derived:  
\[